(공통문제) n-queens

공통문제로 backtracking의 대표 문제인 n-queens 가 선택되었다.

n-queens 를 예전에 답을 본적이 있지만, 역시나.. 이번에도 답을 봐버렸다.

이참에 확실히 정리하고 넘어가는 것이 좋을 것 같아, 최대한 자세하게 풀이를 적을 것이다. (내가 이해할 수 있도록)

backtracking 이란?

backtracking 이란 어떤 노드의 유망성(promising)을 점검한 뒤, 유망하지 않다면 해당 노드의 부모노드로 돌아가(backtracking) 다음 잣기 노드에 대한 검색을 계속 진행하는 과정의 방법이다.

(출처 - http://emzei.tistory.com/223 )

n-queen 문제가 무엇인지에 대해선.. 다른 곳에 자세히 나와있으니 그걸 보도록 하고, 문제를 풀기위해선 상태공간 트리를 깊이 우선 방식으로 탐색하여 해를 찾는 알고리즘이 일반적으로 쓰인다.