# Principled Programming / Tim Teitelbaum / Chapter 14.
class Tour:
    """
    Knight’s Tour.
    Find a path for a Knight, from the upper-left square of an 8-by-8 chess board,
    that visits each square exactly once, if possible.

    # Methods.
    main(cls) -> None

    # See also.
    Chapter 14 of Principled Programming

    """

    # Chess board B is an N-by-N int array, for N=8. Unvisited squares
    #   are BLANK, and row and column indices range from lo to hi.
    N: int = 8               # N is the size of chess board.
    BLANK: int = 0           # BLANK signifies a square not on the current path.
    lo: int = 2              # lo is the row and column index of the upper-left square.
    hi: int = lo + N - 1     # hi is the row and column index of the lower-right square.
    B: list[list[int]] = []  # B[][] is the chess board. Initialization to [] is a
                             #   violation of the representation invariant because N is 8
                             #   and B is empty; this is corrected in method initialize.

    # A tour of length move is given by squares of B numbered 1 to move. Squares numbered
    #   consecutively go from ⟨lo,lo⟩ to ⟨r,c⟩, and correspond to legal moves for a Knight.
    r: int = lo              # r is the Knight’s row coordinate.
    c: int = lo              # c is the Knight’s column coordinate.
    move: int = 1            # move is the length of the current tour.
    # B[r][c] = move         # Knight is initially in upper-left square. Initialization of
                             #   B[r][c] to move is  deferred until method initialize
                             #   because B itself is not initialized until then.

    @classmethod
    def main(cls) -> None:
            """Output a (possibly partial) Knight’s Tour."""
        # Initialize: Establish a tour of length 1.
            Tour.initialize()
        # Compute: Extend the tour, if possible.
            Tour.solve()
        # Output: Print tour as numbered cells in N-by-N grid of 0s.
            Tour.display()

    @classmethod
    def initialize(cls) -> None:
                """Initialize: Establish a tour of length 1."""

        # Complete the representations of the board and a tour of length 1 that could not be done within the
        #   declarations of the class variables:
        #   (1) Set B to an N-by-N sub-array of all BLANK embedded in a 2-cell ring of non-BLANK sentinel squares.
        #   (2) Place the Knight in the upper-left square of the board.

            # Set all of B to non-BLANK.
                Tour.B = [[Tour.BLANK + 1 for _ in range(0, Tour.N+4)]
                          for _ in range(0, Tour.N+4)]
            # Overwrite inner N-by-N array with BLANK.
                for r  in range(Tour.lo, Tour.hi + 1):
                    for c in range(Tour.lo, Tour.hi + 1):
                        Tour.B[r][c] = Tour.BLANK
            # Place Knight in the upper-left square of B.
                Tour.B[Tour.r][Tour.c] = Tour.move

    @classmethod
    def solve(cls) -> None:
        """Compute: Extend the tour, if possible."""

        def score(r: int, c: int) -> int:
            """Return the number of unvisited neighbors of ⟨r,c⟩. (Warnsdorff’s Rule)."""
            count = 0       # The number of unvisited neighbors of ⟨r,c⟩ found so far.
            for j in range(0, 8):
                if Tour.B[r + deltaR[j]][c + deltaC[j]] == Tour.BLANK:
                    count += 1
            return count

        # Row and column offsets for eight neighbors.
        deltaR: list[int] = [-1, -2, -2, -1, 1, 2, 2, 1]
        deltaC: list[int] = [2, 1, -1, -2, -2, -1, 1, 2]
        CUL_DE_SAC: int = 8  # Not a neighbor.

        k = 0   # A neighbor number that is not CUL_DE_SAC.
        while k != CUL_DE_SAC:
            # Extend the tour an additional square, if possible.
                # Let k = index of an unvisited neighbor, or CUL_DE_SAC.

                    # Let bestK be a favored unvisited neighbor, or CUL_DE_SAC, if all neighbors are already visited.
                        bestK = CUL_DE_SAC                 # Index of favored neighbor.
                        best_score = CUL_DE_SAC + 1        # Score of favored neighbor.
                        for k in range(0, CUL_DE_SAC):
                            if Tour.B[Tour.r + deltaR[k]][Tour.c + deltaC[k]] == Tour.BLANK:
                                s = score(Tour.r + deltaR[k], Tour.c + deltaC[k])
                                if s < best_score:
                                    bestK = k
                                    best_score = s

                    # Adopt bestK as k.
                        k = bestK

                # Extend the tour to k if not in cul_de_sac.
                        if k != CUL_DE_SAC:
                            # Extend the tour to unvisited neighbor.
                                Tour.r += deltaR[k]
                                Tour.c += deltaC[k]
                                Tour.move += 1
                                Tour.B[Tour.r][Tour.c] = Tour.move

    @classmethod
    def display(cls) -> None:
        """Output: Print Tour as numbered cells in N-by-N grid of 0s."""
        for r in range(Tour.lo, Tour.hi + 1):
            for c in range(Tour.lo, Tour.hi + 1):
                print((str(Tour.B[r][c]) + "  ")[0:3], end='')
            print()

Tour.main()