数独求解器中的回溯失败
Backtracking in sudoku solver failing
我正在 Python 中编写一个数独解算器，它接受部分填满的棋盘并使用回溯和前向检查来填满其余部分并解决难题。前向检查是指每次您为空白单元格赋值时检查其未分配的行、列和框是否 "neighbors" 在分配后仍然有非空域。
为了表示我的电路板（尺寸：N x N 电路板和 P x Q 框），我使用了一个二维列表，其中每个条目的形式为 [value, [domain]]，其中 value 是分配的单元格编号（如果未分配则为 0）和域是保持数独游戏一致的单元格的可能值。
我认为我的递归做错了，但无法弄清楚是什么。该函数总是失败并且 returns False。下面是我的递归求解器函数的一部分，其中删除了预处理代码。如有必要，我可以 post 整个函数及其辅助函数。
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
###some preprocessing here to check if puzzle is solved and find next empty cell if not
vals = board[row][col][1] #domain/possible values for the empty cell
for num in vals:
#if num doesn't violate the row, col, and box sudoku constraints
if constraintCheck(row, col, num, P, N, Q, board):
#make copy of cell's domain for backtracking
tempDomain = copy.deepcopy(board[row][col][1])
board[row][col][0] = num #assign num to the cell
#remove num from domains of neighbors,
#if an empty domain results after removing num,
#return False and the original board,
#else return True and the updated board
noEmptyDomains, board = propagate_fc(board, N, P, Q, row, col, num)
if noEmptyDomains:
board[row][col][1] = [num] #update domain to be num and then recurse
if fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
return True
#backtrack -- reset value and domain of assigned cell
board[row][col][1] = tempDomain
board[row][col][0] = 0
else:
board[row][col][0] = 0
return False
编辑：更多代码并尝试 Blckknght 的解决方案
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
if time.clock() >= timeout:
return "timeout"
while row < N and board[row][col][0] != 0: #find next blank
if col == N-1:
row = row + 1
col = 0
else:
col = col + 1
if row == N: #solved
return True
for num in vals:
if constraintCheck(row, col, num, P, N, Q, board):
board[row][col][0] = num
noEmptyDomains, new_board = propagate_fc(board, N, P, Q, row, col, num) # new var
if noEmptyDomains:
new_board[row][col][1] = [num] # this doesn't modify board, only new_board
if fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout):
return True
board[row][col][0] = 0 # the only thing that's required to backtrack
return False
def propagate_fc(board, N, P, Q, row, col, num):
origBoard = copy.deepcopy(board)
#row propagate
for x in range(N):
if board[x][col][0] == 0:
if num in board[x][col][1]:
board[x][col][1].remove(num)
if len(board[x][col][1]) == 0:
return False, origBoard #domain is empty; return original board
#col propagate
for y in range(N):
if board[row][y][0] == 0:
if num in board[row][y][1]:
board[row][y][1].remove(num)
if len(board[row][y][1]) == 0:
return False, origBoard #domain is empty
#box propagate
rDiv = row/P
cDiv = col/P
for i in range((rDiv * P), ((rDiv + 1) * P)):
for j in range((cDiv * Q), ((cDiv + 1) * Q)):
if board[i][j][0] == 0:
if num in board[i][j][1]:
board[i][j][1].remove(num)
if len(board[i][j][1]) == 0:
return False, origBoard #domain is empty
return True, board #success; return board with updated domains
如果您进行回溯，您需要能够 return 将您的电路板状态恢复到之前的状态。您当前的代码没有这样做。 propagate_fc 函数以不易撤消的方式修改 board。
因为我没有看到一个简单的方法来反转 propagate_fc 的逻辑，我建议更改求解器的设计，使其复制电路板并仅在传递之前修改副本进一步递归步骤。如果副本没有导致解决方案，则可以将其丢弃，而不是尝试编写回溯代码来修复它。
(我确定 是 可以回溯的，只是不清楚跟踪更改的好方法是什么，弄清楚它的工作量太大了这个答案。）
无论如何，这是我对求解器的修改版本的建议：
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
if time.clock() >= timeout:
return "timeout"
while row < N and board[row][col][0] != 0: #find next blank
if col == N-1:
row = row + 1
col = 0
else:
col = col + 1
if row == N: #solved
return board
for num in vals:
if constraintCheck(row, col, num, P, N, Q, board):
new_board = copy.deepcopy(board)
new_board[row][col][0] = num
if propagate_fc(new_board, N, P, Q, row, col, num):
new_board[row][col][1] = [num]
result = fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout)
if result is not None and result != "timeout":
return result
return None
我已经把它改成return解决的板子了，如果成功的话。否则，您会得到 True 响应，但无法看到结果（因为顶级代码的 board 不会被修改）。
这是 propagate_fc 的更改版本：
def propagate_fc(board, N, P, Q, row, col, num):
# no copying any more here
#row propagate
for x in range(N):
if board[x][col][0] == 0:
if num in board[x][col][1]:
board[x][col][1].remove(num)
if len(board[x][col][1]) == 0:
return False
#col propagate
for y in range(N):
if board[row][y][0] == 0:
if num in board[row][y][1]:
board[row][y][1].remove(num)
if len(board[row][y][1]) == 0:
return False
#box propagate
rDiv = row/P
cDiv = col/P
for i in range((rDiv * P), ((rDiv + 1) * P)):
for j in range((cDiv * Q), ((cDiv + 1) * Q)):
if board[i][j][0] == 0:
if num in board[i][j][1]:
board[i][j][1].remove(num)
if len(board[i][j][1]) == 0:
return False
return board #success; return new board
这里唯一真正的变化是我不打扰 returning board，因为我们总是就地修改它。只需要 bool 结果（表示棋盘是否有效）。
（我最初认为还有另一个问题，在每个块中进行 if len(...) == 0 检查，但事实证明这毕竟不是问题。仅进行这些检查可能会获得更好的性能当您刚刚从当前 board[x][y][1] 列表中 removed 一个值时（通过将这些块缩进两级），但这不太可能带来很大的性能提升。）
基于快速浏览，我认为您混淆了 row/col 传播：
#row propagate
for x in range(row): <== should this be range(col) ?
if board[row][x][0] == 0: <== row is fixed, but cols (x) changes
if num in board[row][x][1]:
board[row][x][1].remove(num)
if len(board[row][x][1]) == 0:
return False, origBoard #domain is empty; return original board
我正在 Python 中编写一个数独解算器，它接受部分填满的棋盘并使用回溯和前向检查来填满其余部分并解决难题。前向检查是指每次您为空白单元格赋值时检查其未分配的行、列和框是否 "neighbors" 在分配后仍然有非空域。
为了表示我的电路板（尺寸：N x N 电路板和 P x Q 框），我使用了一个二维列表，其中每个条目的形式为 [value, [domain]]，其中 value 是分配的单元格编号（如果未分配则为 0）和域是保持数独游戏一致的单元格的可能值。
我认为我的递归做错了，但无法弄清楚是什么。该函数总是失败并且 returns False。下面是我的递归求解器函数的一部分，其中删除了预处理代码。如有必要，我可以 post 整个函数及其辅助函数。
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
###some preprocessing here to check if puzzle is solved and find next empty cell if not
vals = board[row][col][1] #domain/possible values for the empty cell
for num in vals:
#if num doesn't violate the row, col, and box sudoku constraints
if constraintCheck(row, col, num, P, N, Q, board):
#make copy of cell's domain for backtracking
tempDomain = copy.deepcopy(board[row][col][1])
board[row][col][0] = num #assign num to the cell
#remove num from domains of neighbors,
#if an empty domain results after removing num,
#return False and the original board,
#else return True and the updated board
noEmptyDomains, board = propagate_fc(board, N, P, Q, row, col, num)
if noEmptyDomains:
board[row][col][1] = [num] #update domain to be num and then recurse
if fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
return True
#backtrack -- reset value and domain of assigned cell
board[row][col][1] = tempDomain
board[row][col][0] = 0
else:
board[row][col][0] = 0
return False
编辑：更多代码并尝试 Blckknght 的解决方案
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
if time.clock() >= timeout:
return "timeout"
while row < N and board[row][col][0] != 0: #find next blank
if col == N-1:
row = row + 1
col = 0
else:
col = col + 1
if row == N: #solved
return True
for num in vals:
if constraintCheck(row, col, num, P, N, Q, board):
board[row][col][0] = num
noEmptyDomains, new_board = propagate_fc(board, N, P, Q, row, col, num) # new var
if noEmptyDomains:
new_board[row][col][1] = [num] # this doesn't modify board, only new_board
if fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout):
return True
board[row][col][0] = 0 # the only thing that's required to backtrack
return False
def propagate_fc(board, N, P, Q, row, col, num):
origBoard = copy.deepcopy(board)
#row propagate
for x in range(N):
if board[x][col][0] == 0:
if num in board[x][col][1]:
board[x][col][1].remove(num)
if len(board[x][col][1]) == 0:
return False, origBoard #domain is empty; return original board
#col propagate
for y in range(N):
if board[row][y][0] == 0:
if num in board[row][y][1]:
board[row][y][1].remove(num)
if len(board[row][y][1]) == 0:
return False, origBoard #domain is empty
#box propagate
rDiv = row/P
cDiv = col/P
for i in range((rDiv * P), ((rDiv + 1) * P)):
for j in range((cDiv * Q), ((cDiv + 1) * Q)):
if board[i][j][0] == 0:
if num in board[i][j][1]:
board[i][j][1].remove(num)
if len(board[i][j][1]) == 0:
return False, origBoard #domain is empty
return True, board #success; return board with updated domains
如果您进行回溯，您需要能够 return 将您的电路板状态恢复到之前的状态。您当前的代码没有这样做。 propagate_fc 函数以不易撤消的方式修改 board。
因为我没有看到一个简单的方法来反转 propagate_fc 的逻辑，我建议更改求解器的设计，使其复制电路板并仅在传递之前修改副本进一步递归步骤。如果副本没有导致解决方案，则可以将其丢弃，而不是尝试编写回溯代码来修复它。
(我确定 是 可以回溯的，只是不清楚跟踪更改的好方法是什么，弄清楚它的工作量太大了这个答案。）
无论如何，这是我对求解器的修改版本的建议：
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
if time.clock() >= timeout:
return "timeout"
while row < N and board[row][col][0] != 0: #find next blank
if col == N-1:
row = row + 1
col = 0
else:
col = col + 1
if row == N: #solved
return board
for num in vals:
if constraintCheck(row, col, num, P, N, Q, board):
new_board = copy.deepcopy(board)
new_board[row][col][0] = num
if propagate_fc(new_board, N, P, Q, row, col, num):
new_board[row][col][1] = [num]
result = fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout)
if result is not None and result != "timeout":
return result
return None
我已经把它改成return解决的板子了，如果成功的话。否则，您会得到 True 响应，但无法看到结果（因为顶级代码的 board 不会被修改）。
这是 propagate_fc 的更改版本：
def propagate_fc(board, N, P, Q, row, col, num):
# no copying any more here
#row propagate
for x in range(N):
if board[x][col][0] == 0:
if num in board[x][col][1]:
board[x][col][1].remove(num)
if len(board[x][col][1]) == 0:
return False
#col propagate
for y in range(N):
if board[row][y][0] == 0:
if num in board[row][y][1]:
board[row][y][1].remove(num)
if len(board[row][y][1]) == 0:
return False
#box propagate
rDiv = row/P
cDiv = col/P
for i in range((rDiv * P), ((rDiv + 1) * P)):
for j in range((cDiv * Q), ((cDiv + 1) * Q)):
if board[i][j][0] == 0:
if num in board[i][j][1]:
board[i][j][1].remove(num)
if len(board[i][j][1]) == 0:
return False
return board #success; return new board
这里唯一真正的变化是我不打扰 returning board，因为我们总是就地修改它。只需要 bool 结果（表示棋盘是否有效）。
（我最初认为还有另一个问题，在每个块中进行 if len(...) == 0 检查，但事实证明这毕竟不是问题。仅进行这些检查可能会获得更好的性能当您刚刚从当前 board[x][y][1] 列表中 removed 一个值时（通过将这些块缩进两级），但这不太可能带来很大的性能提升。）
基于快速浏览，我认为您混淆了 row/col 传播：
#row propagate
for x in range(row): <== should this be range(col) ?
if board[row][x][0] == 0: <== row is fixed, but cols (x) changes
if num in board[row][x][1]:
board[row][x][1].remove(num)
if len(board[row][x][1]) == 0:
return False, origBoard #domain is empty; return original board