回數在數獨求解失敗

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