알고리즘 23 Backtracking and Pseudopolynomial - N-Queen

모든 경우 + cut off (이런 경우에는 안보겠다는 규칙)

 

N-Queen

n=8

퀸 : 상하좌우,대각선을 공격할 수 있음

 

1. 다 해본다.

64^8가지의 방법으로 배치 후 테스트 (같은 자리에 퀸이 여러개 놓을 수 있는 경우)

각각의 퀸의 쌍에 대해서 공격하는지에 대해 보는 전체 시간 : 64^8 x 8 x 7  (대충 2^54)

 

2. 겹치는 경우를 뺀다.

64C8 (64개의 자리에 8개를 고른다.)

전체 시간: 64C8 x 8 x 7

 

3. 각 row에 하나씩 배치

8^8 x 8 x 7 (대충 8^10 = 2^30)

 

4. Recursion + cut off

i : 몇번째 row에 퀸을 배치해야 하는지

ex ) 1,3,5

1,3,5를 받으면 놓을 수 있는 자리는 3군데

 

---

4x4 Example

 

(차이 == 거리면 대각선으로 안됨!)

 

재귀적으로 다 돌렸다. 사실 대칭이니까 위에는 반만해도 될듯