解决 n-queens 时发生奇怪的事情

Question

所以，我正在解决 n 皇后问题并编写了这个回溯解决方案。

def isSafe(row, col, board):
    print board
    for i in range(col):
        if board[row][i] == 'Q':
            print 'faled here'
            return False

    r_row = row-1
    c_col = col-1
    while r_row >= 0 and c_col >=0:
        if board[c_row][c_col] == 'Q':
            return False
        c_row -=1
        c_col -=1

    row = row-1
    col = col-1
    while row < len(board) and col >=0:
        if board[row][col] == 'Q':
            return False
        row+=1
        col-=1
    return True


def solveNQueen(column, board):
    if column == len(board[0]):
        print board
        return True

    for each_row in range(len(board)):
        print each_row,column
        if isSafe(each_row,column,board):
            print board,'before'
            board[each_row][column] = 'Q'
            print board,' after'
            if solveNQueen(column+1,board):
                return True
            else:
                board[each_row][column] = 0
        print 'failed'
    return False

board = [[0]*5]*5

print solveNQueen(0,board)

奇怪的是我在第 34、35 和 36 行写道：

    print board,'before'
    board[each_row][column] = 'Q'
    print board,' after'

此语句将同一列中的所有索引更改为 'Q'，而不是在特定的行和列索引处进行更改。

来自输出：

[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] before
[['Q', 0, 0, 0, 0], ['Q', 0, 0, 0, 0], ['Q', 0, 0, 0, 0], ['Q', 0, 0, 0, 0], ['Q', 0, 0, 0, 0]]  after

这是怎么回事？还是我喝醉了？

Answer 1

问题是board = [[0]*5]*5。这为您提供了五个副本 相同列表 的五个零。

一个可能的修复：

board = [x[:] for x in [[0] * 5] * 5]

解决 n-queens 时发生奇怪的事情

Weird thing while solving n-queens

python

algorithm

backtracking