Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number ofdistinct solutions.

HideTags

 Backtracking

#pragma once
#include<iostream>
using namespace std;

//判断当钱index中存储的局面是否合规,index中前col列有皇后（0至col-1）
int isOK(int * index, int col)
{
	for (int i = 0; i < col; i++)
		for (int j = 0; j < i; j++)
			if (index[i] == index[j] || abs(i - j) == abs(index[i] - index[j]))
				return false;
	return true;
}

//返回n皇后问题中，前col列的皇后按照index就位之后的可能性数目
int go(int* index, int n, int col)
{
	if (col == n)//前n列就位，到头了
		return 1;//注意！！！此处应为1！！！
	int count = 0;//记录可能数
	for (int row = 0; row < n; row++)//试着在col列的0至n-1行放置皇后
	{
		index[col] = row;
		if (isOK(index, col + 1))
			count += go(index, n, col + 1);
	}
	return count;
}

int totalNQueens(int n) {
	int *index = new int[n];
	return go(index, n, 0);//当钱有0个皇后就位之后的可能，按列来
}

void main()
{
	//int a[] = { 1, 3, 5, 7, 2, 0, 6, 4 };
	//cout << isOK(a, 8) << endl;
	cout << totalNQueens(9) << endl;
	system("pause");
}

52.N-Queens II （n皇后问题，返回可能数，回溯，递归实现）