백트래킹

모든 경우의 수를 조사하는것이 아닌 답이 될 수 없는 경우 즉, 유망하지 않은경우를 제외하면서 완전탐색을 하는것이다.

문제의 경우의 수를 단순히 계산해보면 N^N이다.
(x,y) = (1,1)에 퀸이있고, (2,2)에도 퀸이 있을경우 그 뒤의 경우는 더 이상 조사할 필요가 없다. 여기서 조사를 멈추고 (2,3)의 좌표부터 조사하는것이다.

bool check(int level)
{
	for (int i = 0; i < level; i++)
	{
		if (col[i]==col[level] || abs(col[level]-col[i])==level-i) // x가 같거나 x차y차가 같은경우
		{
			return false;
		}
	}
	return true;
}

void nqueen(int x)
{
	if (x==N){
		total++;
	}
	else {
		for (int i = 0; i < N; i++)
		{
			col[x] = i;
			if (check(x))
			{
				nqueen(x + 1);
			}
		}
	}
}

// nqueen(0)부터 시작

DFS와 차이점

DFS는 N개의 노드를 모두 검사하는것이다. 기본적으로 유사하지만
차이점은 조건에 해당하지 않을경우 더이상 그 자식노드들을 검사하지않고 부모노드로 올라간다는 점이다.

참고
http://sooyoung32.github.io/dev/2016/03/14/n-queen-algorithm.html
https://cryptosalamander.tistory.com/58