八皇後問題（回溯的算法）

八皇後問題是經典的回溯算法案例，但是對初學者有點難以了解...

基本思路是，從第一個皇後開始放置，同時設定列和左斜和右斜放置标志（如果是從列開始的就設定行的标志）

第i行周遊，如果沒有能夠放的位置，直接退出函數（也就是不用管），如果沒有放到8個，就調用下一個函數，但是仍然在這一級函數之内，是以後續需要回溯以便進行下一個點的搜尋。

這樣是按照第一行從第一個字開始的輸出，如果按列的話，轉置矩陣2333333，代碼如下：

/*
經典回溯
八皇後問題
按照每一行開始搜尋
by Dr.ls
*/
#include<iostream>
using namespace std;
const int size = 9;
int num = 0;
int q[9];//記錄每個行的皇後占用的列号
bool line[9];//所在列
bool zuo[17];//所在左斜線i+j
bool you[17];//右斜線
void set(int i)
{
	int j, k, m;
	for (j = 1; j <= 8; j++)
	{
		if ((line[j] == true) && (you[i - j + 9] == true) && (zuo[i + j] == true))
		{
			q[i] = j;//占用ij位置
			line[j] = false;
			you[i - j + 9] = false;
			zuo[i + j] = false;//所在列，斜線均被占用
			if (i < 8)//未到最後一行就調用下一行的函數放置
			{
				set(i + 1);
			}
			else			              // 如果已經放完8個皇後
			{
				num++;		             // 方案數加1
				cout << num << endl;   // 輸出方案号
				char zz[17][17];
				for (m = 1; m <= 8; m++)
				{
					for (k = 1; k <= 8; k++)
					{
						if (k == q[m])
						{
							zz[m][k] = '*';
						}
						else if (k != q[m])
						{
							zz[m][k] = '.';
						}
					}
				}//畫棋盤
				for (k = 1; k <= 8; k++)
				{
					for (m = 1; m <= 8; m++)
					{
						cout << ' ' << zz[k][m];
					}
					cout << endl;//輸出結果
				}
			}
			line[j] = true;
			you[i - j + 9] = true;
			zuo[i + j] = true;//回溯算法，裝作無事發生
		}
	}
}
int main()
{
	int i;
	num = 0;
	for (i = 1; i <= 8; i++)
	{
		line[i] = true;
	}
	for (i = 1; i <= 16; i++)
	{
		zuo[i] = true;
		you[i] = true;
	}
	set(1);//從第一行開始放
	return 0;
}