2

我必须提到这是我第一次在这个网站上发帖，如果我不遵守这个网站的发球指南，请原谅我。

我的问题可能很简单，但我无法理解。我的骑士之旅算法递归地找到骑士的路径。它适用于索引 [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()
4

2 回答 2

1

您的代码没有明显的问题。而且，事实上，用chessBoarda listof替换list并适当地更改代码的其余部分，它适用于所有合法输入。

请参阅此 pastebin以获取修改后的代码。有关仅循环所有有效输入的修改版本，请参见此版本。如果你运行它，它会打印出 36 个完整的电路板。

因此，如果出现问题，或者您没有运行您在此处发布的相同代码，或者您的Array2D实现中存在错误。

您的代码有一些奇怪的地方。

首先，您几乎从不想检查== None. 如果您确实需要检查某物是否为None，请使用is运算符，而不是==。如果您所有的“真实”值都是真实的，只需将值本身用作布尔值（因为None是虚假的）。有关详细信息，请参阅PEP 8 中的编程建议。

接下来，您将全局设置拆分为main函数和全局模块范围。通常你想在同一个地方做这一切。

最后，拥有一个改变全局变量的递归函数是一件奇怪的事情。并不是说它在您的情况下不起作用（只是因为您在退出之前只能运行一个测试），但通常在递归函数中，您希望将值作为“累加器”参数向下传递，或者做所有事情一成不变（通过向下传递和备份副本）。

于 2013-04-08T22:54:30.957 回答
0

abarnert 的代码起作用的原因是他的函数在重写时使用负索引访问数组。因此，如果您查看结果，它们是不正确的（骑士从棋盘的顶部跳到底部）。

于 2013-04-12T16:40:06.770 回答