import random


class Solver:
    def __init__(self, n: int, possibleMoves: list):
        self.__n = n
        self.__nSquared = n * n
        self.__possibleMoves = possibleMoves
        self.__orderTable = None

    def Solve(self, startPosition: tuple = (-1, -1), pickMoveCandidatesInRandomOrder: bool = True) -> bool:
        self.__orderTable = [[0 for x in range(self.__n)] for y in range(self.__n)]

        x, y = startPosition
        if x == y == -1:
            x, y = random.randrange(self.__n), random.randrange(self.__n)
        self.__orderTable[y][x] = 1

        for alreadyOrdered in range(1, self.__nSquared):
            nx, ny = self.__NextFrom(x, y, pickMoveCandidatesInRandomOrder)
            if nx == ny == -1:
                return False
            self.__orderTable[ny][nx] = alreadyOrdered + 1
            x, y = nx, ny
        return True

    def PrintSolution(self):
        maxDigits = len(str(self.__nSquared))
        for row in self.__orderTable:
            print(' '.join((f'{value:{maxDigits}}' for value in row)))

    def __NextFrom(self, x, y, pickMoveCandidatesInRandomOrder: bool):
        nx, ny = -1, -1
        minDegree = len(self.__possibleMoves) + 1

        validDestinations = self.__ValidDestinationsFrom(x, y)
        if pickMoveCandidatesInRandomOrder:
            validDestinations = self.__ValidDestinationsInRandomOrderFrom(x, y)

        for dstX, dstY in validDestinations:
            dstDegree = self.__CalculateDegreeOf(dstX, dstY)
            if dstDegree < minDegree:
                minDegree = dstDegree
                nx, ny = dstX, dstY
        return nx, ny

    def __InBounds(self, x, y):
        return 0 <= x < self.__n and 0 <= y < self.__n

    def __ValidDestinationsFrom(self, x, y):
        for dx, dy in self.__possibleMoves:
            nx, ny = x + dx, y + dy
            if self.__InBounds(nx, ny) and self.__orderTable[ny][nx] == 0:
                yield nx, ny

    def __ValidDestinationsInRandomOrderFrom(self, x, y):
        validDestinations = list(self.__ValidDestinationsFrom(x, y))
        random.shuffle(validDestinations)
        return validDestinations

    def __CalculateDegreeOf(self, x, y):
        return sum(1 for dst in self.__ValidDestinationsFrom(x, y))


if __name__ == '__main__':
    n = 10
    moves = [(3, 0), (2, 2), (0, 3), (-2, 2), (-3, 0), (-2, -2), (0, -3), (2, -2)]
    # moves = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    solver = Solver(n, moves)

    while True:
        if solver.Solve(startPosition=(0, 0), pickMoveCandidatesInRandomOrder=False):
            solver.PrintSolution()
            break

    iterationsCount = 1000
    successCount = sum(int(solver.Solve(pickMoveCandidatesInRandomOrder=False)) for i in range(iterationsCount))
    print(f'Success in {successCount} of {iterationsCount} iterations without random candidates ordering.')
    successCount = sum(int(solver.Solve(pickMoveCandidatesInRandomOrder=True)) for i in range(iterationsCount))
    print(f'Success in {successCount} of {iterationsCount} iterations with random candidates ordering.')