N-Queens

유명한 Eight Queens Puzzle의 일반화 버전.
백트래킹을 공부할때 흔히 사용되는 예제이기도 하다.
워낙 유명한 문제다 보니 여기저기 자료들도 많으니, 기본적인 것만 요약하면
- N*N칸 중에 N칸을 고르는 방법으로 접근하면 C(N*N, N) 인데 이건 너무 비효율적이고..
- 퀸이 각 row당 한개씩 배치되어야 하니까, N개의 column중 한개를 고르는 것을 N번 반복해서 배치를 만드는 방법, 즉 N^N 가지의 방법중에서 골라나가는 형태로 접근하는게 정석이다
- 새 row에 퀸을 놓을 때는, 놓으려는 column이 이미 놓여진 퀸들과 같은 column, 같은 \ 방향 대각선, 같은 / 방향 대각선에 있는지만 체크하면 된다.
  - 저 세가지를 bool 배열로 갖고서, 퀸을 놓을때마다 갱신해주면 O(1)에 체크 가능하다.
여기에 추가적인 속도 향상 팁으로는 이런것들이 있다.
- 좌우대칭을 이용해서 탐색을 줄이는 것이 가능하다.
  - 첫번째 row에서 i번째 column에 퀸을 놓았을 때의 경우의 수는, N-i+1번째 column에 퀸을 놓았을 때와 좌우만 바뀌고 똑같기 때문에 경우의 수도 같다. 그래서 첫번째 row에 대해서는 전체 컬럼의 절반까지만 탐색해도 된다
- N개의 column중 하나를 고르는 것을 N번 반복하는 대신, N!개의 퍼뮤테이션중 하나를 고르는 식으로 접근할 수도 있다
  - 이것을 구현한 경우에는 결과들이 사전순으로 나오지는 않는다. 사전순으로 나오도록 코드를 수정할수 있으나 많이 느려진다.

Rosetta Code에는 언어별로 코드 예제가 올라와 있다.

아래는 Python 3 기준으로 성능을 측정한 결과
- 구름IDE에서 Python3.9.0 으로 실행했을때 기준
돌아가는 한계는 N=14 정도. N=11부터 초단위로 시간이 걸리고, N=14일때
N=11부터부터 초단위로 시간이 걸린다.
- 이 때부터, 대칭 구조를 이용한 최적화을 적용할 때의 시간 단축이 체감된다.
permutation 최적화의 시간 단축이 체감되는 것은 N=12부터
BOJ의 N-Queens 문제에서는 N의 범위가 15까지 들어온다.
- 그냥 짜면 시간 초과.
- 대칭 구조를 이용하면 27556ms
- 대칭 구조 + permutation은 15486ms

N-Queens

관련 문제