N-Queens 알고리즘 (N x N 체스판에 N개의 퀸 체스말 놓기)

알고리즘 문제 중에서도 유명한 편에 속하는 N-queens 문제에 도달하게 되었다.
주어진 과제는 '어떻게 하면 n개의 여왕 체스말을 n by n 크기 체스판에서 공격 범위 밖에 놓을 수 있을지를 구현하고, 또 각각의 n에 대하여 몇 가지 방법이 가능한지를 구해라'는 것이었다.

처음 과제를 접했을 땐, 마냥 모든 경우의 수를 구할 수 있도록 n제곱번을 하면 되려나 싶었는데,
n개의 말에 대한 모든 경우를 구해야하니 실제로는 어마어마한 경우의 수를 보아야만 하는 것이었다.

가상의 체스판은 행렬의 형태로서 이중 배열을 가지게 하여 구상할 수 있었다.
퀸은 가로, 세로, 대각선 모두가 공격범위이기 때문에,
n개의 말을 놓으려면 각 행 또는 열 마다 하나의 퀸이 있어야만 한다.
가장 기본적인 크기는 n이 4일때부터였는데,
일단 맨 처음 (0, 0)에 놓는 경우부터 하나씩 그려보았다.

문제는

순서대로 16번을 놓아보더라도 4개의 말을 놓을 수가 없는 경우가 발생하였다!!!

이런 경우가 앞으로의 n의 경우에도 계속해서 발생할 것이므로,
동일한 문제가 반복되지 않도록 개념을 확립하고 나아가야만 했다.

그래서 떠올린 생각은,

1. 행렬의 끝까지 갔는데도 놓여진 말이 n개가 아니라면 재귀한다.
2. 재귀를 할 떄에는 바로 첫번째 말의 위치를 옮기고 경우를 따지는 것이 아니라, 마지막으로 놓였던 말을 기준으로 역순으로 되짚어본다.
3. 한번 말을 놓고 나면, 바로 다음 행 또는 열로 이동한다.

1, 2번의 생각을 한 이유는
끝까지 가서도 n개가 아닐 경우 바로 첫번째 말을 옮겨버리면 위의 그림과 같이 두번째 말을 1행 2, 3열 각각에 놓은 경우 모두를 파악할 수가 없다. 그렇기 때문에 마지막까지 간 후 되돌아오도록 하는 과정이 필요했다.

3번의 생각을 한 이유는,
어차피 말은 한 줄(행 또는 열)에 하나씩 밖에 못 놓으므로,
어떤 한 말을 놓은 시점에서 해당 줄에 대해서는 더 고민할 필요가 없어지게 된다.
바로 다음 줄로 넘어가서 다음 말을 놓을 수 있을지를 보도록 하면, 굳이 보지 않아도 되는 경우를 제외하게 되므
n개를 놓을 수 있는 방법을 찾을 때까지의 시간이 절약될 수 있다.