Ss 八皇后問題tips，規定棋盤式（8*8）（回溯算法）讀者諸君看完tips先嘗試自己寫一個，再看答案哈^_^

       規則：兩兩不處于同一行、列、斜線

       1八個皇后肯定分布在八個橫行之中

       2按行遞歸，每行之中按列擴展（列是循環的依據）；

       3每添加一個皇后，將其能吃且尚未擺放皇后的位置設為其行號以作標記（這三個方向分別是左下，正下，右下方），如遇符合條件且已經被打上標記的位置，跳過，不做處理，當程序回溯時，再將該皇后（僅僅是該皇后）改變的標簽在修改為0；

       Ps 回溯法思想：走不通就掉頭；在問題的解空間之中，按深度優先搜索方式搜索，如果根節點包含問題的解，則進入該子樹，否則跳過以該節點為根的子樹

回溯算法的設計過程：

Step1確定問題的解空間

Step2確定節點的擴展規則

Step3搜索解空間

添加約束：排除錯誤的狀態，不進行沒有必要的擴展（分支修剪，是設計過程中對遞歸的優化）在自己設計的八皇后代碼中，按行進行遞歸，所以相當于分支修剪

對每一次擴展的結果進行檢查

枚舉下一狀態叫遞歸，退回上一狀態叫回溯;在前進和后退之時設置標志，以便于正確選擇，標志已經成功或者已然遍歷所有狀態

#include<iostream>using namespace std;int board[8][8] = { 0 };   //chessboardint cnt = 0;              //answers to this puzzlesinline bool valid(int x, int y){    //judge whether the dot is within the borders or not	if (0 <= x && 0 <= y && 8 > x && 8 > y)return true;	else return false;}void set(int row, int col,int setval){ //set tags according to the dot added immadiately	int sgn;  //mainly for dealing with PRiority,	//the tags set before by former dots should not be changed by the dots added latter 	//when backtrack,should only change the tags set just now instead of long before	sgn = (setval == 0) ? row + 1 : 0;	for (int r = row+1; r < 8; r++)//extend properly		if(board[r][col]==sgn)board[r][col] = setval;	/*for (int c = 0; c < 8; c++)		board[row][c] = setval;*///no need to set val horizontally	/*for (int i = row-1, j = col-1; valid(i, j,sgn);)//no need to come back to set val	{		board[i][j] =setval;		i--;		j--;	}*/	for (int i = row + 1, j = col + 1; valid(i, j);){  //extend properly		if(board[i][j]==sgn)board[i][j] = setval;		i++;		j++;	}	for (int i = row + 1, j = col - 1; valid(i, j);){//extend properly		if(board[i][j]==sgn)board[i][j] = setval;		i++;		j--;	}}void print(int last){	printf("No.%d/n", cnt);	for (int i = 0; i < 8; i++){		for (int j = 0; j < 8; j++)		{			if (j != last || i != 7)printf("%d ", (board[i][j]==i+1?i+1:0));			else printf("%d ", 8);		}		printf("/n");	}	}void EQP(int row){//row is the depth of recursion	if (row == 7){		int i = 0;		for (; i < 8; i++)		if (board[7][i] == 0){			cnt++; 			print(i);		}		return;	}	for (int j =0; j < 8; j++){		if (board[row][j] == 0){			board[row][j] = row + 1;			set(row, j, row + 1);			EQP(row + 1);			board[row][j] = 0;			set(row, j, 0);		}	}}int main(){	EQP(0);	printf("/n");	cout <<"in total:"<< cnt << endl;	system("pause");}