사용자 도구

사이트 도구


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

관련 문제

토론

댓글을 입력하세요:
H P I G X
 
ps/n-queens.txt · 마지막으로 수정됨: 2020/12/10 05:22 저자 teferi