如何解決一個數獨拼圖網格大小400 * 400使用Java

我正在研究一個java項目來解決一個數獨400 * 400的網格大小。我用回溯遞歸來解決它，但它並沒有給我複雜性的解決方案。我想知道是否有任何其他算法來處理這種類型的數獨網格。請幫忙。如何解決一個數獨拼圖網格大小400 * 400使用Java

來源

2017-04-25 Sudip Banerjee

https://bob-carpenter.github.io/games/sudoku/java_sudoku.html – NBaua

試圖這樣做，「搜索引擎」的事情嗎？喜歡。 http://stackoverflow.com/questions/36037919/heuristic-function-for-applying-a-sudoku或https://en.wikipedia.org/wiki/Sudoku_solving_algorithms – GhostCat

數獨是NP完全的。在合理的時間內，你不可能有絕對確定的解決方案，但你可以嘗試尋找啓發式解決方案。 – RealSkeptic

正如@RealSkeptic在評論中指出的那樣。數獨是NP完成的。這意味着可以在一個多項式範圍內根據輸入大小在時間內檢查一個實例。由於您使用多線程標記了您的問題，因此我提議進行以下分解。

生成相應的候選方案
檢查每個候選

兩個可以快速爲所有意圖和目的來完成。一個是挑戰。

我會嘗試某種形式的[constaint programming] [1]來減少每個單元格可以具有的選項數量。然後散列進程以嘗試每種情況，基本上是平行回溯。

[1] https://en.wikipedia.org/wiki/Constraint_programming

來源

2017-04-25 08:12:39 dvberkel

如何解決一個數獨拼圖網格大小400 * 400使用Java

回答

相關問題