八皇后问题

在国际象棋的棋盘上，按照国际象棋的规则，摆放8个皇后，使之“和平共处”。如图所示，在3-D上有一个皇后，则绿色区域中都不能再放置皇后了。
最暴力的方法就是使用八个for，但是很明显，这种方法效率太低。

对于放置了皇后的位置，仔细观察棋盘可以发现每一列（行）只能有一个皇后，每一个主（次）对角线上也只能有一个皇后，这样需要标记：行-row，列-col，主对角线-(n+row-col)，次对角线-(row+col)

注意：关于对角线的一点说明：
    这里以次对角线为例：数字相同的表示一条次对角线，所以对于一个8x8的棋盘来说，一共有2x8-1条次对角线。

流程图：

基于流程图，利用递归的思想，c++实现如下，这里的皇后的个数是在主函数中设置的8，个数可以改，但意义不大。。。。。
在递归回溯的过程中清空了标记，是为了继续搜索，找到所有的解。

#include <iostream>
#include <vector>

using namespace std;

class EightQueen {
public:
	EightQueen(int nQueen) {
		this->nQueen = nQueen;
		inColumn.resize(nQueen, false);
		mainDiagonal.resize(2 * nQueen - 1, false);
		minorDiagonal.resize(2 * nQueen - 1, false);
	}
	~EightQueen() {}
	int process() {
		int *path = new int[nQueen];
		calculate(path, 0);
		delete[] path;
		return 0;
	} 
	void calculate(int *path, int row) {
		if (row == nQueen) {
			solution.push_back(vector<int>(path, path + nQueen));
			return;
		}
		for (int col = 0; col < nQueen; col++) {
			if (canLay(row, col)) {//当前位置可放置
				path[row] = col;//标记放置的位置
				inColumn[col] = true;//当前皇后所在列
				minorDiagonal[row+col] = true;//皇后所在位置的横纵坐标之和对应的次对角线
				mainDiagonal[nQueen-1+row-col] = true;//皇后所在位置的横纵坐标之和对应的主对角线
				calculate(path, row + 1);//下一行上的皇后
				//break;//去掉搜索所有的解！
				inColumn[col] = false;
				minorDiagonal[row+col] = false;
				mainDiagonal[nQueen-1+row-col] = false;
			}
		}
	}
	bool canLay(int row, int col) {
		return !inColumn[col] && !minorDiagonal[row + col] && !mainDiagonal[nQueen - 1 + row - col];
	}
	void print() {
		for (int i = 0; i < solution.size(); i++) {
			cout << "solution " << i << " : " << endl;
			for (int row = 0; row < nQueen; row++) {
				for (int col = 0; col < solution[i][row]; col++) {
					cout << "O ";
				}
				cout << "X ";
				for (int col = solution[i][row]+1; col < nQueen; col++) {
					cout << "O ";
				}
				cout << endl;
			}
			cout << endl << endl;
		}
	}
private:
	int nQueen;
	vector<bool> inColumn;
	vector<bool> mainDiagonal;
	vector<bool> minorDiagonal;
	vector<vector<int> > solution;
};

int main()
{
	EightQueen queen(8);
	queen.process();
	queen.print();
	return 0;
}

总体思想为一行一行进行判断，判断某一行时，从该行第一个位置开始判断是否能放棋子，如果不能则继续判断下一个位置，如果可以，则代表该行已经找到，进入下一行即进入下一个递归，重复上述操作。如果该行没有一个位置可以放入，说明之前摆放好的位置有问题，则返回到上一个递归即上一行继续查找新位置，以此类推。如果8行全部找完，则打印输出，打印完成后返回至上一个递归即上一行继续找是否还有合适的位置，直到92种全部找到。

#include<iostream>

//定义棋盘大小8*8
#define ROW 8
#define COL 8

//八皇后问题递归求解
//统计数量
int num = 0;

//判断r行c列位置是否可以放置棋子
bool safe(int r, int c, int** chessboard)
{
	int i, j;
	//判断列方向有无棋子
	for (i = 0; i < ROW; i++)
	{
		if (chessboard[i][c] != 0)
		{
			return false;
		}
	}
	//判断左上方有无棋子
	for (i = r, j = c; i >= 0 && j >= 0; i--, j--)
	{
		if (chessboard[i][j] != 0)
		{
			return false;
		}
	}
	//判断右下方有无棋子
	for (i = r, j = c; i < ROW && j < COL; i++, j++)
	{
		if (chessboard[i][j] != 0)
		{
			return false;
		}
	}
	//判断右上方有无棋子
	for (i = r, j = c; i >= 0 && j < COL; i--, j++)
	{
		if (chessboard[i][j] != 0)
		{
			return false;
		}
	}
	//判断左下方有无棋子
	for (i = r, j = c; i < ROW && j >= 0; i++, j--)
	{
		if (chessboard[i][j] != 0)
		{
			return false;
		}
	}
	return true;
}

//递归部分
void iteration(int row, int** chessinput)
{
	int** arr = new int* [8];
	for (int i = 0; i < ROW; i++)
	{
		arr[i] = new int[8];
	}
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			arr[i][j] = chessinput[i][j];
		}
	}

	if (row == 8)//棋盘装满后打印
	{
		cout << "第" << num + 1 << "种结果：" << endl;
		for (int i = 0; i < ROW; i++)
		{
			for (int j = 0; j < COL; j++)
			{
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
		num++;
	}
	else//棋盘未装满，继续装填
	{
		for (int i = 0; i < COL; i++)
		{
			if (safe(row, i, arr))//判断是否可以放置棋子
			{
				for (int j = 0; j < COL; j++)
				{
					arr[row][j] = 0;//先将该行全部赋值为0
				}
				arr[row][i] = 1;//再将该行安全的那一列赋值为1
				iteration(row + 1, arr);
			}
		}

	}
	for (int i = 0; i < ROW; i++)
	{
		delete[] arr[i];
	}
	delete[] arr;
}



int main()
{
	int** initarr = new int* [8];
	for (int i = 0; i < ROW; i++)
	{
		initarr[i] = new int[8];
	}
	for (int i = 0; i < ROW; i++)
	{
		for (int j = 0; j < COL; j++)
		{
			initarr[i][j] = 0;
		}
	}

	iteration(0, initarr);

	for (int i = 0; i < ROW; i++)
	{
		delete[] initarr[i];
	}
	delete[] initarr;

	return 0;
}