ps:n-queens
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
관련 문제
ps/n-queens.txt · 마지막으로 수정됨: 2020/12/10 05:22 저자 teferi
토론