[アルゴリズム]遡及

1.バックトラッキングとは、

2. General Algorithm

void checknode(node v)
{
	node u;

	if(promising(v))
		if(Solution exist at v)
			Write the solution
		else
			for(each child u of v)
				checknode(u)
}

3.深度優先ナビゲーション（DFS）

4.例-N-Queens Problem

Why Backtracking?

1)すべての状況をツリー形式で計算します.
2)節気がなければ、子供の節気を見ずに親の節気に戻る.
3)次の言葉を見る.

#include <iostream>
using namespace std;

int N;
int cnt = 0;
int board[15] = { 0 };

bool IsPromising(int row_check)
{
	for (int row_QueenExist = 0; row_QueenExist < row_check; ++row_QueenExist)
	{
		int col_check = board[row_check];
		int col_QueenExist = board[row_QueenExist];

		if (col_QueenExist == col_check) return false; // 같은 열에 있는 경우
		else if (row_QueenExist - row_check == col_QueenExist - col_check || row_QueenExist - row_check == col_check - col_QueenExist) return false; // 같은 대각선에 있는 경우
	}
	return true;
}

/* 같은 행에 있는 경우를 따져보지 않는 이유*/
// dfs함수에서 주어진 row가 promising하다면 dfs(row + 1)을 탐색하고 있다.
// 이 코드에서 같은 행에 퀸을 두는 경우는 없으므로 같은 행에 있는 경우를 따져보지 않아도 된다.

void dfs(int row)
{
	/*모든 행에 하나씩, 총 N개의 Queen을 두는 방법 찾은 경우*/
	if (row == N)
	{
		cnt++;
	}
	else
	{
		for (int col = 0; col < N; ++col)
		{
			board[row] = col; // (row, col)에 퀸을 둔다.
			if (IsPromising(row)) dfs(row + 1); // (row, col)에 퀸을 둘 수 있다면 다음 행을 살펴본다.
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);

	cnt = 0;
	cin >> N;

	dfs(0);

	cout << cnt << '\n';
	return 0;
}