编辑代码

# coding:utf-8
#JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。 
def knights_tour(width, height):
        # Initialize board
            board = [[-1 for _ in range(width)] for _ in range(height)]
                # Possible moves for the knight
                    moves = [(1, 2), (2, 1), (2, -1), (1, -2),
                                 (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
                                     
                                         # Start at (0, 0)
                                             start_x, start_y = 0, 0
                                                 board[start_x][start_y] = 0  # First move
                                                     
                                                         # Recursive backtracking
                                                             def solve(x, y, move_count):
                                                                     if move_count == width * height:
                                                                                 return True
                                                                                         # Try all possible moves
                                                                                                 next_moves = []
                                                                                                         for dx, dy in moves:
                                                                                                                     nx, ny = x + dx, y + dy
                                                                                                                                 if 0 <= nx < width and 0 <= ny < height and board[nx][ny] == -1:
                                                                                                                                                 # Count possible moves from (nx, ny)
                                                                                                                                                                 count = 0
                                                                                                                                                                                 for ndx, ndy in moves:
                                                                                                                                                                                                     nnx, nny = nx + ndx, ny + ndy
                                                                                                                                                                                                                         if 0 <= nnx < width and 0 <= nny < height and board[nnx][nny] == -1:
                                                                                                                                                                                                                                                 count += 1
                                                                                                                                                                                                                                                                 next_moves.append((count, nx, ny))
                                                                                                                                                                                                                                                                         # Sort by the number of next moves (Warnsdorff's rule)
                                                                                                                                                                                                                                                                                 next_moves.sort()
                                                                                                                                                                                                                                                                                         for _, nx, ny in next_moves:
                                                                                                                                                                                                                                                                                                     board[nx][ny] = move_count
                                                                                                                                                                                                                                                                                                                 if solve(nx, ny, move_count + 1):
                                                                                                                                                                                                                                                                                                                                 return True
                                                                                                                                                                                                                                                                                                                                             board[nx][ny] = -1  # Backtrack
                                                                                                                                                                                                                                                                                                                                                     return False
                                                                                                                                                                                                                                                                                                                                                         
                                                                                                                                                                                                                                                                                                                                                             if solve(start_x, start_y, 1):
                                                                                                                                                                                                                                                                                                                                                                     return board
                                                                                                                                                                                                                                                                                                                                                                         else:
                                                                                                                                                                                                                                                                                                                                                                                 return None