/*  Name: n皇后問題  Copyright:   Author: 巧若拙   Date: 07-03-17 09:09  Description: 一、問題描述：在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于再n×n的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。輸入：    給定棋盤的大小n (n ≤ 13)輸出：    輸出有多少種放置方法。二、解題思路：要解決N皇后問題，其實就是要解決好怎么放置這n個皇后，每一個皇后與前面的所有皇后不能在同一行、同一列、同一對角線，在這里我們可以以行優先，就是說皇后的行號按順序遞增，只考慮第i個皇后放置在第i行的哪一列，所以在放置第i個皇后的時候，可以從第1列判斷起，如果可以放置在第1個位置，則跳到下一行放置下一個皇后。如果不能，則跳到下一列...直到最后一列，如果最后一列也不能放置，則說明此時放置方法出錯，則回到上一個皇后向之前放置的下一列重新放置。此即是回溯法的精髓所在。當第n個皇后放置成功后，即得到一個可行解，此時再回到上一個皇后重新放置尋找下一個可行解...如此后，即可找出一個n皇后問題的所有可行解。三、復雜度分析：每一行都有n個位置可以放置，一共有n^n中可能性。因而最壞情況下時間復雜度為O(n^n)。似乎比窮舉法要高，但是由于回溯法不測試死結點的分支，它的平均時間復雜度要低于窮舉法。 */#include<iostream>#include<cmath>using namespace std;const int N = 4; //皇后的個數int c[N];//記錄n個皇后的列坐標 int sum = 0;//保存可以放置的方案數bool OK(int t);//檢查當前皇后的列坐標是否合法 void Backtrace(int t); //遞歸回溯 void Backtrace_2(); //非遞歸回溯 int main() {   Backtrace(0);  // Backtrace_2();      system("pause");   return 0;}bool OK(int t)//檢查當前皇后的列坐標是否合法 {    for(int i=0; i<t; i++)    {        if(c[i] == c[t] || t-i == abs(c[t]-c[i]))      			return false;           }    return true;}void Backtrace(int t) //遞歸回溯 {    if(t == N)    {        sum++;        cout << "方案" << sum << ": ";        for(int i=0; i<N; i++)        {            cout << c[i] << " ";        }        cout << endl;    }    else    {        for(int i=1; i<=N; i++)        {			c[t] = i;            if(OK(t))				Backtrace(t+1);        }      //  c[t] = 0;   //列坐標還原并回溯（由于c[t]每次都從0開始取值，故列坐標無需還原）    }}void Backtrace_2() //非遞歸回溯 {	int t = 0; //第一個頂點入棧		while(t >= 0)	{		while(c[t]++ < N)//c[t]默認初始化為0 		{			if (OK(t)) //c[t]可行才進入下一步 			{				if(t == N-1)				{					sum++;					cout << "方案" << sum << ": ";					for(int i=0; i<N; i++)					{						cout << c[i] << " ";					}					cout << endl;				}				else				{					t++;				}			}		}		c[t--] = 0; //列坐標還原并回溯	}}