순환의 응용 : n queens problem

- queen이 같은 행이나 열에 있으면 안됌

 

Backtracking

- 진행하다가 막다른 길에 도달할 때 왔던 길을 되돌아가는 방법

 

*상태공간트리

- 상태공간트리란 찾는 해를 포함하는 트리

- 해가 존재한다면 그것은 반드시 이 트리의 어떤 한 노드에 해당함

-> 이 트리를 체계적으로 탐색하면 해를 구할 수 있음

 

 * 상태공간 트리의 모든 노드를 탐색해야 하는 것은 아님

ex) 1번 말이 1,1에 있다면 2번말은 2,1과 2,2에는 갈 수가 없으므로 그 밑은 찾아볼 필요가 없다.

=> backtracking 기법

 

- 꽝인지 확인 -> 밑으로 내려갈 필요 x

- 정답이라면 리턴

- 꽝이 아닌데 정답도 아니라면 -> queen함수를 다시 호출

 

- 성공인지 확인하는 방법 : 매개변수 값이 내가 놓고 싶은 말의 개수와 같아지면 성공

- 꽝이 아니고 성공이 아닐 때

-> 현재 level에 +1을 한 값을 index로 말을 둘 수 있는 값들을 모두 넣는다. -> level+1을 매개변수로 queens함수를 호출한다.

 

꽝인지 확인하는 함수