O (n) 시간 복잡도가있는 N-queen에 대한 설명?

Question

O (n) 시간 복잡도로 N-queen 문제를 해결하는 http://www.apl.jhu.edu/~hall/java/NQueens.java에서 구현을 실행했습니다. 놀랍도록 빠르며 검색하지 않고도 하나의 솔루션을 찾을 수 있습니다. 그러나, 나는 뒤에 논리에 대해 정말로 분명하지 않다. 왜 그들은 3 : 홀수, 짝수 (그러나 6k 형식이 아님), 심지어 짝수 (형식 6k + 2가 아님)로 문제를 나눕니 까? 누구든지 코드를 확인하고 나에게 자세히 설명 할 수 있습니까 (논리 전용)?

Answer 1

두 경우 모두 구성을 다루지 않기 때문에 문제가 두 개로 나뉩니다. 아마도 그들이 나쁜 경우에 작동한다는 것을 증명하려고 시도한다면, 특정 숫자는 모듈로 n이 unit이 아님을 알게 될 것입니다. 이것은 제한된 조합 객체를 구성 할 때 매우 일반적인 상태입니다. 예를 들어, 순서가 6k + 1 및 6k + 3 인 Steiner triple systems이 있지만 두 잔여 mod6은 다른 구조를 필요로합니다.