具有O（n）時間複雜度的N皇后的解釋？

Question

我已經運行在可用的執行：http://www.apl.jhu.edu/~hall/java/NQueens.java，這解決了N皇后問題的O（n）時間複雜性。它速度驚人，有助於找出一種解決方案而無需搜索。但是，我並不清楚背後的邏輯。 爲什麼他們將問題分爲3：奇數，偶數（但不是6k形式），甚至（但不是6k + 2形式）。 任何人都可以檢查代碼併爲我更詳細地解釋（僅適用於邏輯）嗎？

Answer 1

他們分裂了這個問題，因爲這兩個建築都沒有涵蓋所有的情況。可能如果你試圖證明他們在壞的情況下工作，你會發現某個數字不是unit模n。構建約束組合對象時，這是一個非常典型的事件狀態。例如，存在階數6k + 1和6k + 3的Steiner triple systems，但是兩個殘基mod 6需要不同的構造。