Python 回溯（皇后棋盘）

Question

好吧，经过数小时的头脑斗争，我终于明白了回溯是如何工作的。尽管我仍然认为还有一些秘密有待了解。无论如何，我正在尝试在棋盘上创建 4-queens 问题。实际上，我给了自己一个空白棋盘（实际上是 4x4），我需要找到 4 个皇后不会攻击自己的地方。女王也攻击它所属的行、列和对角线。这是我到目前为止所做的（有效功能尚未完成，但这并不重要。我只需要回溯功能即可）。

def findNextCell(grid,i,j):

    for index in range(i,4):
        for jindex in range(j,4):
            return index, jindex

    for index in range(0,4):
        for jindex in range(0,4):
            if grid[index][jindex] == 0:
                return index, jindex

    return -1,-1


def isValid(grid, index, jindex, queen):

    rowOk = all([queen != grid[index][x] for x in range(4)])
    if rowOk:
        columnOk = all([queen != grid[x][jindex] for x in range(4)])
        if columnOk:
            return True
    return False

def queenSolve(grid, i=0, j=0, num_queens = 0):

    i, j = findNextCell(grid, i, j)
    print grid
    if num_queens == 4:
        return True
    if isValid(grid, i, j, 1):
        grid[i][j]=1
        num_queens += 1
        if (queenSolve(grid, i, j, num_queens)):
            return True
        grid[i][j]=0
    return False

input = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

print queenSolve(input)

Answer 1

我看到的第一个问题是这个例程中的初始嵌套循环：

def findNextCell(grid,i,j):

    for index in range(i,4):
        for jindex in range(j,4):
            return index, jindex

    for index in range(0,4):
        for jindex in range(0,4):
            if grid[index][jindex] == 0:
                return index, jindex

    return -1,-1

这似乎是一些从未被清除的早期测试代码：

    for index in range(i,4):
        for jindex in range(j,4):
            return index, jindex

但不幸的是，它导致 findNextCell() 总是 return i 和 j 它被通过了，仅此而已：

>>> findNextCell(0, 1, 2)
(1, 2)
>>> findNextCell(0, 3, 2)
(3, 2)
>>> findNextCell(0, 1, 1)
(1, 1)
>>>

我看到的下一个问题是这对线：

num_queens += 1
if (queenSolve(grid, i, j, num_queens)):

这是增加皇后的数量，成功或失败！相反，您可能只需要一行：

if (queenSolve(grid, i, j, num_queens + 1)):

即增加递归皇后的数量，但不影响当前数量，以防失败。

我看到的第三个问题是这不是循环：

i, j = findNextCell(grid, i, j)
...
if isValid(grid, i, j, 1):
    grid[i][j]=1
    num_queens += 1
    if (queenSolve(grid, i, j, num_queens)):
        return True
    grid[i][j]=0

您应该尝试将当前皇后放在所有有效空间中，直到您运行超出有效空间，findNextCell() return 为负数，或直到递归成功。您为当前的女王尝试一个位置，然后放弃。此题对当前皇后迭代，对后续皇后递归

Python 回溯（皇后棋盘）

Python Backtracking (queens checkboard)

python

backtracking