八皇后回溯算法

思路来源：动画演示八皇后回溯算法

视频演示的非常清楚，也有详细代码，所以此处不再过多剖析，仅展示代码。

视频中使用vector来储存每次尝试的结果；需要注意的是，vector本质是new开辟的，而下面代码的实现并未使用new开辟空间，而是采用的栈数组，所以撤销操作时，需要深度拷贝，否则函数返回后，数组将失效！

方案一：

#include<iostream>
#include<vector>
using namespace std;
int dir_x[8] = { -1, -1, -1, 1, 1, 1, 0, 0 };//创建两个方向数组
int dir_y[8] = {  0 , 1, -1, 0, 1,-1, 1,-1 };
              //  L  LU  LD  R RU RD  U  D      L左，R右，D下,U上 
void copy_attack(int(*attack)[8], int(*temp)[8]);
void update_attack(int(*attack)[8], int i, int k);
void ini_att_que(int (*attack)[8], char (*queen)[8]);
void backtrack(int n, int(*attack)[8], char(*queen)[8]);
int counts;
int main()
{
 
	int attack[8][8];
	char queen[8][8];
	ini_att_que(attack, queen);
	backtrack(0, attack, queen);
	cout << "八皇后问题一共有" << counts << "种解法。" << endl;
	return 0;
 
}
void ini_att_que(int (*attack)[8], char (*queen)[8])
{
	for (int i = 0; i < 64; i++)
		*(*attack + i) = 0;
	for (int i = 0; i < 64; i++)
		*(*queen + i) = '#';
}
void backtrack(int n, int(*attack)[8], char(*queen)[8])//n为行数
{
	if (n == 8)
	{
		for (int i = 0; i < 8; i++)
		{
			for (int k = 0; k < 8; k++)
				printf("%  c  ", queen[i][k]);
			cout << endl;
		}
		printf("=====================================\n");
		counts++;
		return;
	}
	for (int col = 0; col < 8; col++)//col即column，列数
	{
		if (attack[n][col] == 0)
		{
			int temp[8][8];
			copy_attack(attack,temp);//备份attack数组
			queen[n][col] = 'Q';//放置皇后；
			update_attack(attack, n, col);
			backtrack(n + 1, attack, queen);//检测下一行
			copy_attack(temp, attack);//这里不是备份了！而是撤销之前的update_attack！此处不能直接attack=temp！因为temp是局部变量！函数结束后会被销毁(即需要深拷贝而不是浅拷贝)
			queen[n][col] = '#';     //撤销之前放置的皇后
		}
	}
	
}
void copy_attack(int(*attack)[8],int(*temp)[8])
{
	for (int i = 0; i < 8; i++)
	{
		for (int k = 0; k < 8; k++)
			temp[i][k] = attack[i][k];
	}
}
void update_attack(int(*attack)[8],int i,int k)//i为行，k为列
{
	for (int m = 1; m < 8; m++)
	{
		for (int g = 0; g < 8; g++)
		{
			int nx = i + m * dir_x[g];//nx和ny是被攻击的地方，利用方向数组直接向八个方向辐射！
			int ny = k + m * dir_y[g];
			if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8)
			{
				attack[nx][ny] = 1;
			}
		}
	}
}

方案二：

int n,  x[N], ret = 0;

bool canPut(int m){
	int j;
	for(j=0;j<m;j++) //这里的j是指m层的上方所有层
		if(x[m]==x[j]  //检测[m][i]正上方的[m][j]有没有棋子
		|| abs(j-m)==abs(x[j]-x[m]))//检测[m][i]的左右斜上方有没有棋子：j-m=行距; x[j]-x[m]=列距
			return false;
	return true;
}

void go(int m){
	int i;
	if(m>n-1){ //n-1：我们定义的是8皇后，但数组下标从0开始，也就是说m>7时，就已经满足了条件
		ret++;
		for(i=0;i<n;i++)
			cout<<x[i]<<" ";
		cout<<"    "<<ret<<endl;
		return;
	}
	for(i=0;i<n;i++){//横向扫描
		
		x[m]=i;      //此步非常抽象！八皇后棋盘本应是二维，x数组却是一维，这一步便是用一维数组实现二维效果的关键所在！
					 //m是指层数，而x[m]，即x[m]中的数，是指所在列数！即x[m]=i表示棋盘位置[m][i]；且一旦对x[m]赋值，就代表在[m][i]处放棋
					 //当x[m]重新被赋值为f，则表示在第m行f列重新放棋，之前的x[m]=i所放的棋自然而然的被移到了[m][f]处，所以就避免了上一种方法的撤销操作！
		
		if(canPut(m))//剪枝
			go(m+1);
	}
}

int main()
{
	int i,j;
	n=8;
	go(0);
	cout<<ret;
	return 0;
}

方案一和方案二的差别在于：方案一利用二维数组，具象地模拟了放棋和撤棋的过程（比如使用*号代表棋子）；而方案而则使用一维数组，利用下标+下标中的数据来模拟放棋。第二种更加巧妙，没有额外空间复杂度，但相比方案一更抽象。