O（n）時間の複雑さを持つN-queenについての説明？

Question

私はO（n）時間の複雑さでN-queenの問題を解くhttp://www.apl.jhu.edu/~hall/java/NQueens.javaで実装を実行しました。それは驚くほど速く、検索せずに1つのソリューションを見つけるのに役立ちます。しかし、私はその背後にある論理について本当に明確ではない。 なぜ問題は3：奇数、偶数（フォーム6kではなく）、偶数（フォーム6k + 2ではなく）に分割されますか。 誰かがコードをチェックし、私のためにもっと詳しく説明できますか（ロジックのみ）？

Answer 1

どちらの構成もすべてのケースをカバーしていないため、問題を分割しました。たぶんあなたが悪いケースで働いていることを証明しようとすると、特定の数がunitモジュロnではないことがわかります。これは、制約付きコンビナトリアルオブジェクトを構築するときの非常に典型的な状態です。例えば、次数が6k + 1と6k + 3のSteiner triple systemsが存在しますが、2つの残差mod 6は異なる構成を必要とします。