數獨多項式算法？

我有一個項目要做複雜性和解決問題的課程，並且我決定將該項目建立在Sudoku上。從我所做的研究中，Sudoku是一個NP-Complete問題（這是項目需要的），並且我發現了幾種創建算法的方法。我打算做一個強力解決方法，我需要做另外兩種方法。我找到了一些方法，比如將它解決爲一個精確的封面問題，並且我找到了一篇將Sudoku描述爲SAT問題的論文。但我的問題是：Sudoku是否有一個經過驗證的多項式解決方案？我的老師似乎認爲大約5年前一位「高級」紳士提出了一個「聰明」的解決方案，但這是他所能記住的。有人知道這個解決方案是什麼，或者其他多項式解決方案是什麼？我會很感激任何信息或提示。數獨多項式算法？

謝謝！

來源

2013-03-28 derekahc

蠻力是關於多項式，因爲它可以得到。（雖然可能會有一些修剪） – wildplasser

NP-Complete表示存在（可能）沒有解決方案，該解決方案隨輸入大小進行多項式縮放。但是，數獨只有一個輸入大小，所以這在這裏意味着什麼呢？ –

啊，好的，數獨類拼圖這個更一般的問題是NP-Complete。從[這裏]（http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Mathematical_context）：*「在n×n個塊的n2×n2個棋盤上解決數獨謎題的一般問題已知爲NP-complete。 n = 3（古典數獨），但是，這個結果幾乎沒有關係：像Dancing Links這樣的算法可以在幾分之一秒內解決難題。「* –

您也可以使用human-like strategy，它可以是多項式，但它不會找到所有sudokus（甚至那些有獨特解決方案）的解決方案。將數獨減少爲圖着色問題也非常容易（每個單元由圖的節點表示，節點根據數獨的規則連接，以便不具有相同的顏色）。預填充節點接地顏色）。

來源

2013-06-07 10:47:34 malejpavouk

查看維基百科上的「rook polynomials」。

對於一個9 * 9網格，它開始完全是空的，這給出了一個9階多項式。

但是，對於部分填充的網格，訂單會縮短到最長的空白範圍。

來源

2016-03-05 19:34:55

由於廣義獨問題（其中n ×Ñ柵極）是NP難解，如果存在用於解決數獨謎題已知的多項式時間算法，這將證明P = NP。這將是一個巨大的成交。

需要記住的是，數獨謎題，因爲我們知道他們都是9 × 9格。因此，當試圖測量解決Sudoku難題的時間複雜度時，使用大O符號實際上並不是一個好主意，因爲big-O符號會談論算法如何在長期和全部範圍內縮放我們關心的是解決一個固定大小的數獨謎題。換句話說，如果你想談論解決Sudoku難題的多項式時間，你必須回答「多項式在哪個變量中？」「如果你總是解決9數獨網格，答案這個問題並不十分清楚。

來源

2016-03-05 19:43:13 templatetypedef

真的嗎？檢查一個數獨是否有效的是O（1）：有9行，9列和9個塊，我們只需要檢查每個數字是否包含[1..9]。然後，在9x9字段（9^81，包括無效字段）上分配密碼的組合總數有限。迭代任何這樣的組合，檢查，如果每個固定位置匹配（再次O（1）），並檢查，如果一個有效的數獨。然後你有最多執行步驟的數量（9^81 *（<步驟來檢查修復數字是否匹配> + <步驟來檢查有效的數獨>），所以只解決9x9數獨就是O（1）.. – Aconcagua

@Aconcagua我完全同意，在我的回答中，我試圖強調，談論解決sudokus的複雜性真的只有在你允許謎題被泛化時纔有意義，否則，正如你所指出的，答案是「O（ 1）「。 – templatetypedef

數獨多項式算法？

回答

相關問題