Пояснение для N-queen с временной сложностью O (n)?

Question

Я запустил реализацию, доступную по адресу: http://www.apl.jhu.edu/~hall/java/NQueens.java, которые решают проблему N-queen с временной сложностью O (n). Это удивительно быстро и помогает найти одно решение без поиска. Тем не менее, я не совсем понимаю логику. Почему они разбивают проблему на 3: нечетные, даже (но не в форме 6k), даже (но не в форме 6k + 2). Может ли кто-нибудь проверить код и объяснить более подробно для меня (только для логики)?

Answer 1

Они делят проблему, потому что ни одна конструкция не охватывает все случаи. Возможно, если вы попытаетесь доказать, что они работают в плохих случаях, вы обнаружите, что определенное число не является unit по модулю n. Это довольно типичное состояние дел при построении ограниченных комбинаторных объектов. Например, существуют Steiner triple systems заказов 6k + 1 и 6k + 3, но два остатка mod 6 требуют разных конструкций.