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

       規(guī)則：兩兩不處于同一行、列、斜線

       1八個(gè)皇后肯定分布在八個(gè)橫行之中

       2按行遞歸，每行之中按列擴(kuò)展（列是循環(huán)的依據(jù)）；

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

       Ps 回溯法思想：走不通就掉頭；在問(wèn)題的解空間之中，按深度優(yōu)先搜索方式搜索，如果根節(jié)點(diǎn)包含問(wèn)題的解，則進(jìn)入該子樹，否則跳過(guò)以該節(jié)點(diǎn)為根的子樹

回溯算法的設(shè)計(jì)過(guò)程：

Step1確定問(wèn)題的解空間

Step2確定節(jié)點(diǎn)的擴(kuò)展規(guī)則

Step3搜索解空間

添加約束：排除錯(cuò)誤的狀態(tài)，不進(jìn)行沒(méi)有必要的擴(kuò)展（分支修剪，是設(shè)計(jì)過(guò)程中對(duì)遞歸的優(yōu)化）在自己設(shè)計(jì)的八皇后代碼中，按行進(jìn)行遞歸，所以相當(dāng)于分支修剪

對(duì)每一次擴(kuò)展的結(jié)果進(jìn)行檢查

枚舉下一狀態(tài)叫遞歸，退回上一狀態(tài)叫回溯;在前進(jìn)和后退之時(shí)設(shè)置標(biāo)志，以便于正確選擇，標(biāo)志已經(jīng)成功或者已然遍歷所有狀態(tài)

#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");}