我必须指出，这是我第一次在此网站上发帖，如果我不完全遵守该网站的指南，请原谅我。
我的问题可能很简单，但我无法理解。我的骑士巡回算法递归地为骑士寻找路径。它在索引 [0,0] 上工作，它完美地遍历数组的空间......但是，在除索引 [0,0] 之外的任何地方，程序挂起似乎是永恒的。这是我的代码:
# knightstour.py
#
# created by: M. Peele
# section: 01
#
# This program implements a brute-force solution for the Knight's tour problem
# using a recursive backtracking algorithm. The Knight's tour is a chessboard
# puzzle in which the objective is to find a sequence of moves by the knight in
# which it visits every square on the board exactly one. It uses a 6x6 array for
# the chessboard where each square is identified by a row and column index, the
# range of which both start at 0. Let the upper-left square of the board be the
# row 0 and column 0 square.
#
# Imports the necessary modules.
from arrays import *
# Initializes the chessboard as a 6x6 array.
chessBoard = Array2D(6, 6)
# Gets the input start position for the knight from the user.
row = int(input("Enter the row: "))
col = int(input("Enter the column: "))
# Main driver function which starts the recursion.
def main():
knightsTour(row, col, 1)
# Recursive function that solves the Knight's Tour problem.
def knightsTour(row, col, move):
# Checks if the given index is in range of the array and is legal.
if _inRange(row, col) and _isLegal(row, col):
chessBoard[row, col] = move # Sets a knight-marker at the given index.
# If the chessBoard is full, returns True and the solved board.
if _isFull(chessBoard):
return True, _draw(chessBoard)
# Checks to see if the knight can make another move. If so, makes that
# move by calling the function again.
possibleOffsets = ((-2, -1), (-2, 1), (-1, 2), (1, 2), \
(2, 1), (2, -1), (1, -2), (-1, -2))
for offset in possibleOffsets:
if knightsTour(row + offset[0], col + offset[1], move + 1):
return True
# If the loop terminates, no possible move can be made. Removes the
# knight-marker at the given index.
chessBoard[row, col] = None
return False
else:
return False
# Determines if the given row, col index is a legal move.
def _isLegal(row, col):
if _inRange(row, col) and chessBoard[row, col] == None:
return True
else:
return False
# Determines if the given row, col index is in range.
def _inRange(row, col):
try:
chessBoard[row, col]
return True
except AssertionError:
return False
# A solution was found if the array is full, meaning that every element in the
# array is filled with a number saying the knight has visited there.
def _isFull(chessBoard):
for row in range(chessBoard.numRows()):
for col in range(chessBoard.numCols()):
if chessBoard[row, col] == None:
return False
return True
# Draws a pictoral representation of the array.
def _draw(chessBoard):
for row in range(chessBoard.numRows()):
for col in range(chessBoard.numCols()):
print("%4s" % chessBoard[row, col], end = " ")
print()
# Calls the main function.
main()
请您参考如下方法:
您的代码没有明显的错误。而且，事实上，将 chessBoard 替换为 list 的 list 并适当更改其余代码，它适用于所有合法输入。
参见 this pastebin为适应的代码。参见 this one对于仅遍历所有有效输入的修改版本。如果您运行它，它会打印出 36 个完整的电路板。
因此，如果出现问题，要么是您运行的代码与您在此处发布的代码不同，要么是您的 Array2D 实现中存在错误。
您的代码有一些奇怪的地方。
首先，您几乎不想检查 == None。如果您确实需要检查某些内容是否为 None，请使用 is 运算符，而不是 ==。如果您所有的“真实”值都是真实的，只需将值本身用作 bool 值(因为 None 是假的)。参见 Programming Recommendations在 PEP 8 中了解详细信息。
接下来，您将全局设置分为 main 函数和全局模块范围。通常您希望在同一个地方完成所有操作。
最后，拥有一个改变全局变量的递归函数是一件奇怪的事情。并不是说它在你的情况下不起作用(但只是因为你只能在退出前运行一个测试)，但通常在递归函数中你想要将值作为“累加器”参数向下传递，或者不可变地做所有事情(通过向下传递副本并备份)。
