Объяснение для N-королевы с O (n) сложностью по времени?

Question

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

Answer 1

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