八皇后问题，Eight Queens Puzzle

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