回数在数独求解失败

Question

我正在Python中编写一个数独求解器，它需要部分填充棋盘并使用回溯和前向检查来填充其余部分并解决难题。正向检查是每次向空白单元格赋值时检查其行，列和框未赋值“邻居”在赋值后是否仍有非空域的情况。

为了表示我的电路板（尺寸：N x N电路板，带有P x Q框），我使用了一个2D列表，其中每个条目的形式为[value，[domain]]，其中value是分配的单元格的数量（如果未分配，则为0），域是可以保持数独拼图一致的单元格的可能值。

我相信我做错了我的递归，但无法弄清楚什么。该函数总是失败并返回False。下面是我的递归求解器函数的一部分，并带有预处理代码。如有必要，我可以发布整个函数及其辅助函数。

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 

Answer 1

如果你正在做回溯你需要能够对板卡的状态恢复到以前的样子。你目前的代码没有这样做。 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 

我已经改变了它返回解决了板，如果它是成功的。否则，你会得到一个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 

这里唯一真正的变化是，我也懒得返回board，因为我们一直在地方修改它。只有布尔结果是必要的（说如果董事会是否有效）。

（我最初以为还有另外一个问题，在每个块中都有if len(...) == 0检查，但事实证明这并不是问题，只有当你刚才remove从当前的board[x][y][1]列表中获得da值（通过将这些块缩进两级），但这不太可能是一个很大的性能提升。）

Answer 2

基于一瞥，我想你混淆了你的行/列繁殖：

#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