Sudoku解決/生成算法問題

我正在創建一個程序，它將在vb.net中生成數獨遊戲，並且由於我這樣做的方式，我需要它來解決棋盤位置（以特定的隨機方式訪問單元格順序），然後再以相反的順序解決。我正在使用遞歸求解器。Sudoku解決/生成算法問題

這是我與工作的代碼：

Public Function solve(ByRef board() As Integer) As Boolean 
    For i = 0 To 80 
     If board(order(i)) = 0 Then 
      For j = 1 To 9 
       board(order(i)) = j 
       If check_conflicts(board, order(i)) = False Then 
        If solve(board) = True Then 
         Return True 
        End If 

       End If 
      Next 
      board(order(i)) = 0 
      Return False 
     End If 
    Next 

    Return True 
End Function

其中check_conflicts是確定特定小區分配是否直接與板相沖突的函數（因此板被傳遞和細胞order(i)的索引也通過了）。當order是0到80的列表時，該功能按預期工作，但如果order是一個隨機洗牌列表，則該函數需要非常長的時間（有時會超過一分鐘），但通常會得到正確的答案。當order是從80到0的數字列表時，該函數不會解決任何問題，並且總是返回false。

我嘗試了單步執行代碼，但使用遞歸函數很困難。我想知道是否有人能看到我所做的邏輯錯誤，謝謝！

來源

2014-02-23 maxG795

此功能時的順序爲0〜80的列表如預期，然而如果順序是隨機洗牌列表則函數取（一個微小的有時向上）超長但通常得到正確答案。

原因可能是，當遞歸樹隨遞歸深度呈指數級增長時，當您逐行處理數字（而不是按隨機順序）時，大多數無效排列被提前刪除。你永遠不必處理第一行不一致的第二行。

當order是從80到0的數字列表時，該函數不會解決任何問題並始終返回false。

一對夫婦建議：

1）嘗試用80-i更換order(i)以確保問題不是在order()功能;

2）每次撥打電話check_conflicts(board, order(i))時，也請撥打check_conflicts(inverse(board), 80-order(i))，並在結果不相同的情況下拋出異常。

來源

2014-02-23 22:40:08 Anton

感謝您的回覆，我嘗試了您的建議，並意識到它無法倒退的原因是由於約束集中的錯誤使得難題變得不可能。我懷疑這個算法天生就很慢，我猜想我需要實現一些優化 – maxG795

Sudoku解決/生成算法問題

回答

相關問題