我的 N-Queens 解决方案有什么问题？
What's wrong in my N-Queens solution?
class Solution:
def solveNQueens(self, n):
def n_queens_solver(row, visited_cols, unique_y_intercepts, res):
if row == n:
results.append(res)
return
for col in range(n):
if col not in visited_cols and (row + col) not in unique_y_intercepts and (col - row) not in unique_y_intercepts:
visited_cols_dup = visited_cols.copy()
unique_y_intercepts_dup = unique_y_intercepts.copy()
res_dup = res.copy()
visited_cols_dup.add(col)
unique_y_intercepts_dup.add(row + col)
unique_y_intercepts_dup.add(col - row)
this_row = '.' * col + 'Q' + '.' * (n - col - 1)
res_dup.append(this_row)
n_queens_solver(row + 1, visited_cols_dup, unique_y_intercepts_dup, res_dup)
results = []
n_queens_solver(0, set(), set(), [])
return results
我还没有研究过这个问题的实际解决方案，我想我的解决方案非常低效，但我不知道我做错了什么。
示例输入：
n = 4
正确输出：
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
我的输出：
[]
为了考虑独特的对角线，我计算出对于每个插入皇后的有效位置，我们需要考虑所有具有斜率 +1 和斜率 -1 的线。每条线都有一个独特的 y 截距。使用 y=x+b 和 y=-x+b，每个插入皇后的潜在点必须没有 (y-x == b) 或 (y+x == b)。
我的理由有什么明显不正确的地方吗？
注意 - 我不是在要求不同的或更优化的解决方案。我只是想弄清楚我的思维过程哪里不正确。
算法错误如下。看看当您尝试将对角线标记为已访问时会发生什么。
让我们绘制 4x4 板并为每个单元格分配它所在的正斜率对角线的数量（将 i + j 放在第 i 行的正方形上和 col j):
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
假设你把第一个皇后放在(1,3)的位置上。我知道您的算法从第 0 行开始，但在这种情况下无关紧要。现在棋盘如下所示：
0 1 2 3
1 2 3 Q
2 3 4 5
3 4 5 6
然后将 3 添加到 visited_cols，将 3 + 1 = 4 添加到 y_intercepts，将 3 - 1 = 2 添加到 y_intercepts。我们有 cols = {3} 和 y_intercepts = {2,4}。让我们在棋盘上用 X 标记对应于 y_intercept 的值 2 的对角线：
0 1 X 3
1 X 3 Q
X 3 4 5
3 4 5 6
现在假设我们继续算法到第 2 行，我们尝试将第二个皇后放在方格 (2,0) 上。这是一个有效的位置，因为第一个皇后不攻击这个广场。但是你的算法会拒绝这个位置，因为 row + col = 2 + 0 = 2 在 y_intercepts 集合中。发生了什么？我们对正方形 (2, 0) 进行了正斜率测试，但失败了，因为 y_intercepts 集中有 2 个。但请注意，这个 2 是在检查负斜率对角线后添加的（还记得 3 - 1 = 2 吗？）。因此，对正斜率和负斜率对角线的测试混合在一起，导致错误地拒绝了平方 (2, 0)。这就是为什么你的程序输出空的 results 向量的原因 - 在算法的某个点有一行使得它的所有方块都被拒绝（一些被正确拒绝，另一些被错误拒绝，类似于我们刚刚观察到的).
解决它的一种方法是为正斜率对角线和负斜率对角线创建两个单独的集合，并检查 row + col 正斜率和 col - row 负斜率。
class Solution:
def solveNQueens(self, n):
def n_queens_solver(row, visited_cols, unique_y_intercepts, res):
if row == n:
results.append(res)
return
for col in range(n):
if col not in visited_cols and (row + col) not in unique_y_intercepts and (col - row) not in unique_y_intercepts:
visited_cols_dup = visited_cols.copy()
unique_y_intercepts_dup = unique_y_intercepts.copy()
res_dup = res.copy()
visited_cols_dup.add(col)
unique_y_intercepts_dup.add(row + col)
unique_y_intercepts_dup.add(col - row)
this_row = '.' * col + 'Q' + '.' * (n - col - 1)
res_dup.append(this_row)
n_queens_solver(row + 1, visited_cols_dup, unique_y_intercepts_dup, res_dup)
results = []
n_queens_solver(0, set(), set(), [])
return results
我还没有研究过这个问题的实际解决方案，我想我的解决方案非常低效，但我不知道我做错了什么。
示例输入：
n = 4
正确输出：
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
我的输出：
[]
为了考虑独特的对角线，我计算出对于每个插入皇后的有效位置，我们需要考虑所有具有斜率 +1 和斜率 -1 的线。每条线都有一个独特的 y 截距。使用 y=x+b 和 y=-x+b，每个插入皇后的潜在点必须没有 (y-x == b) 或 (y+x == b)。
我的理由有什么明显不正确的地方吗？
注意 - 我不是在要求不同的或更优化的解决方案。我只是想弄清楚我的思维过程哪里不正确。
算法错误如下。看看当您尝试将对角线标记为已访问时会发生什么。
让我们绘制 4x4 板并为每个单元格分配它所在的正斜率对角线的数量（将 i + j 放在第 i 行的正方形上和 col j):
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6
假设你把第一个皇后放在(1,3)的位置上。我知道您的算法从第 0 行开始，但在这种情况下无关紧要。现在棋盘如下所示：
0 1 2 3
1 2 3 Q
2 3 4 5
3 4 5 6
然后将 3 添加到 visited_cols，将 3 + 1 = 4 添加到 y_intercepts，将 3 - 1 = 2 添加到 y_intercepts。我们有 cols = {3} 和 y_intercepts = {2,4}。让我们在棋盘上用 X 标记对应于 y_intercept 的值 2 的对角线：
0 1 X 3
1 X 3 Q
X 3 4 5
3 4 5 6
现在假设我们继续算法到第 2 行，我们尝试将第二个皇后放在方格 (2,0) 上。这是一个有效的位置，因为第一个皇后不攻击这个广场。但是你的算法会拒绝这个位置，因为 row + col = 2 + 0 = 2 在 y_intercepts 集合中。发生了什么？我们对正方形 (2, 0) 进行了正斜率测试，但失败了，因为 y_intercepts 集中有 2 个。但请注意，这个 2 是在检查负斜率对角线后添加的（还记得 3 - 1 = 2 吗？）。因此，对正斜率和负斜率对角线的测试混合在一起，导致错误地拒绝了平方 (2, 0)。这就是为什么你的程序输出空的 results 向量的原因 - 在算法的某个点有一行使得它的所有方块都被拒绝（一些被正确拒绝，另一些被错误拒绝，类似于我们刚刚观察到的).
解决它的一种方法是为正斜率对角线和负斜率对角线创建两个单独的集合，并检查 row + col 正斜率和 col - row 负斜率。