Title: Solve the knight's tour problem in Python

A knight's tour is a sequence of moves that a knight can make on a chessboard to visit every square without repetition. This example uses recursion to solve the knight's tour problem.

Start with small boards until you know how long the program will take on your system. There are a huge number of possible paths that a knight can take if the board is relatively large, so exhaustively searching them for a tour can take a long time. For example, when I ran this program on an 8×8 board, I got tired of waiting after an hour and gave it the old Ctrl+C.

Also note that there are some board sizes where no knight's tour is possible. For example, there are no knight's tours on 1×1, 2×2, 3×3, or 4×4 boards. Fortunately those boards are small so the program can quickly determine that there are no tours. There are tours on a 3×4 board.

Getting Started

def solve_click(self, event=None): '''Solve the puzzle.''' # Get the number of rows and columns. num_rows = int(self.num_rows_var.get()) num_cols = int(self.num_cols_var.get()) # Draw the board. xmin, ymin, row_hgt, col_wid = self.draw_board(num_rows, num_cols) # Solve the puzzle. moves = solve(num_rows, num_cols) # Draw the solution. self.draw_solution(num_rows, num_cols, moves, xmin, ymin, row_hgt, col_wid)

The program then calls the solve function (described shortly) to actually find the path. It finishes by calling draw_solution to draw the solution.

Finding a Tour

def solve(num_rows, num_cols): '''Solve the puzzle and return the knight's moves.''' start_time = time.time() # Make the two-dimensional moves array. moves = [[0 for c in range(num_cols)] for r in range(num_rows)] # Start by moving to square[0][0]. num_squares = num_rows * num_cols if move_to(num_squares, num_rows, num_cols, 0, 0, moves, 1): end_time = time.time() print(f'{end_time - start_time:.4f} seconds') return moves end_time = time.time() print(f'{end_time - start_time:.4f} seconds') return None

After it sets up the moves list, the code calls the move_to function described next to do the real work. If move_to returns True, the solve function returns the moves list. If move_to returns False, it could not find a tour so the solve function returns None.

Understanding move_to

The move_to function is recursive, which means it calls itself. The basic idea is that the function calls itself to make the knight explore the chess board one move at a time.

The function takes as a parameter the moves list, which holds the moves that the knight has already made. It also takes as parameters the row and column where the knight should move next.

The function marks the new square with the move number to add it to the knight's path. It then examines the possible moves from that position. Some (or all) of those moves may be impossible because they are off the edge of the board or because the knight already visited them. For every possible legal move from the new position, the function calls itself recursively to try to extend the path in that direction.

This continues with move_to calling itself recursively to extend the knight's path one square at a time until one of two things happens.

First, the path may visit every square. In that case, the function has found a knight's tour and it is stored in the moves list. The function returns True to tell the instance of move_to that called it that we have found a tour. That instance sees that and also returns True. The calls to the function unwind with each returning True to the call above until we climb all the way up the call stack to the solve function that started it all. There the solve function returns Moves and everything is hunky-dory.

The second possibility is that the growing path reaches a dead end where there are no more legal moves. In that case, move_to resets its current square to 0 to indicate that the square is no longer visited and future paths can use it. It then returns False to tell the calling function that this path does not lead to a complete tour. The calling function can then explore the next legal move and try to extend its path in a new direction.

This process of moving back up the call tree to the calling function is called backtracking and is an important concept in this and many other recursive algorithms.

The calling function then explores other paths and, if none gives a complete tour, it will also return False and backtrack up another level to an earlier point in the path.

The whole process continues with one call to move_to calling another to move down the call tree and returning True or False to move back up the tree until either we have found a complete tour or the function calls have examined every possible path through the chessboard.

Implementing move_to

Here's the move_to function.

def move_to(num_squares, num_rows, num_cols, row, col, moves, move_number): ''' Move the knight to position [row][col]. Then recursively try to make other moves. Return true if we find a valid solution. Return a success code and the number of attempts. ''' # Build a list of legal moves from this position. offsets = [(-2, -1), (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2)] # Move the knight to this position. moves[row][col] = move_number # If we have visited all of the squares, this is a solution. if move_number == num_squares: return True # Try all legal positions for the next move. move_number += 1 for dr, dc in offsets: r = row + dr c = col + dc if r < 0 or r >= num_rows: continue if c < 0 or c >= num_cols: continue if moves[r][c] != 0: continue # This move is legal and available. Make it recursively. if move_to(num_squares, num_rows, num_cols, r, c, moves, move_number): return True # This move didn't work out. Undo it and backtrack. moves[row][col] = 0 return False

After creating the offsets list, the function makes its move by saving the current move_number in square (row, col) in the moves list.

Next, the code checks whether we have visited all of the board's squares. If move_number equals num_squares, then we have finished a complete tour. For example, on a 6×6 board, if this is move_number 36, then we have just visited the final square in the tour. In that case, the function returns True to indicate that moves contains a complete tour. After that, the other calls to move_to that got us here also return True so moves remains unchanged until control returns to the solve function that started the whole show.

If this is not the final move in a tour, the function tries making every possible move from this point. It loops through the offsets list. For each offset pair, it adds the pair's row and column offset to the current position (row, col) and checks the resulting row and column. If the new row or column is off of the board, or if that square has already been visited, the function uses a continue statement to ski this offset and it considers the next one.

If the new row and column is on the board and not yet visited, the function recursively calls itself to move to that square. If that recursive call returns True, that means it found a complete tour and the moves list holds its moves. In that case, the current call to move_to also returns True, leaving moves unchanged.

If the recursive call to move_to returns False, that means it did not find a complete tour. In that case, the current function call continues examining other offsets to see if one of them will lead to a tour.

If the function examines all of the possible offsets and doesn't find a complete tour, then there is no tour possible starting with the current sequence of moves. In that case, the function resets moves[row][col] = 0 to indicate that this square is not visited so later calls to move_to can try visiting the square. Just because the current path can't use that square doesn't mean some other path cannot.

In fact, because a tour visits every square on the board, some other path must visit this square if there is a tour. For that reason, it's vital that the function unmark moves[row][col] so later paths can use it.

Drawing the Solution

def draw_solution(self, num_rows, num_cols, moves, xmin, ymin, row_hgt, col_wid): '''Draw the solution.''' # Find the center of square[0][0]. x0 = xmin + col_wid / 2 y0 = ymin + row_hgt / 2 # If there is no solution, say so. if moves is None: font = ('Arial', 30) x = x0 + (num_cols - 1) / 2 * col_wid y = y0 + (num_rows - 1) / 2 * row_hgt self.canvas.create_text(x, y, font=font, text='No Solution', fill='red') return # Draw lines connecting the moves. points = [] for move_number in range(1, num_rows * num_cols + 1): r, c, = self.find_row_col(num_rows, num_cols, moves, move_number) points.append((x0 + c * col_wid, y0 + r * row_hgt)) self.canvas.create_line(points, fill='red') # Draw the move numbers. font = ('Arial', 8) y = y0 for r in range(num_rows): x = x0 for c in range(num_cols): self.canvas.create_text(x, y, font=font, text=f'{moves[r][c]}') x += col_wid y += row_hgt

If there is a solution, the code draws lines connecting the moves. To do that, it loops variable move_number from 1 to the number of squares on the board. For each move number, it calls the find_row_col method described shortly to find the square holding that move number. It does a little math to add the center of that square to the points list.

When it has found all of the move numbers, the program simply connects their center points. Because the points list holds the centers of the squares ordered by their move numbers, the lines connect the moves in order.

After drawing the connecting lines, the method loops through the moves list's rows and columns and draws each square's move number in its square.

Implementing find_row_col

def (self, num_rows, num_cols, moves, move_number): '''Return the row and column where this move is.''' for r in range(num_rows): for c in range(num_cols): if moves[r][c] == move_number: return r, c raise LookupError(f'Move number {move_number} not found')

If none of the entries holds the right move number, the method throws a temper tantrum by raising a LookupError. This should never happen, though, because the program only calls find_row_col if it found a tour so the move numbers 1 through the number of squares should all be there somewhere. (You could use move offsets to move from one move to the next, but this is a lot simpler.)

Conclusion