回溯算法
回溯法又称试探法，回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
八皇后问题
问题描述：
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
算法描述：
八皇后问题
算法描述
a.定义数组 col[8]:统计放过皇后的列
left[15]:统计左斜线是否已经放过皇后
right[15]:统计右斜线是否已经放过皇后
Q[8]:栈（需要回溯，则需要知道前一个皇后的位置），统计放皇后的位置（所在行i,所在列Q[i]）
b.判断第i行j列能否放皇后
若j<8,则放皇后
若j==8, 则不能放，则回到上一行（回溯）
c.判断是是否求出全部解
如果第一行的八列都已经放过皇后了，又要重新从Q[0] = 0开始放皇后时，则全部解已求出。
代码
#include<stdio.h>
#include<stdlib.h>
int Q[8];//统计放皇后的位置（所在行i,所在列Q[i]）
int cut =0;
/*输出函数*/
void print(){
printf("\n\n");
printf("第%d个解：\n",++cut);
for(int i=0; i<8; ++i){
for(int j=0; j<8; ++j){
if(Q[i] == j)
printf(" Q");
else
printf(" X");
}
printf("\n");
}
}
/*求解八皇后问题函数*/
void Queen(){
/*初始化*/
int left[15] = {0};//统计左斜线是否已经放过皇后
int right[15] = {0};//统计右斜线是否已经放过皇后
int col[8] = {0};//统计列是否已经放过皇后
int top, i, j;
top = -1;
i = j = 0;//保证第一次循环是从0行开始
/*开始求解*/
while(1){
/*放皇后*/
for( ; j<8; ++j){
if(!col[j]&&!left[i+j]&&!right[7+i-j]){
Q[++top] = j;
col[j] = left[i+j] = right[7+i-j] = 1;
i++;
j = 0;
break;
}
}
/*输出*/
if(top == 7)
print();
/*不能放，回溯，并在回溯时，判断是否求出已全部解*/
if(j == 8 || top ==7){ //第i行不能放（j==8）或者是已经得到了一个解(top==7)
if(Q[0] == 7 && i==1)//如果第一行的八列都已经放过皇后，又要再从Q[0] = 0开始放皇后时。则全部解已求出。退出while循环
break;
i--;//回到前一行
j = Q[top--]; //出栈
col[j] = left[i+j] = right[7+i-j] = 0;
j++;
}
}
}
int main(void){
/*求解八皇后*/
Queen();
}
注意第64行以及81行的 left[i+j]、right[7+i-j]。如下图所示
image
我们用left和right两个数组将所有的斜线全部进行了标识。
数组left表示左斜线，right表示右斜线。
左斜线： left = i-j ( 0 <= i, j <= 7).
右斜线： right = i+j ( 0 <= i, j <= 7).
列如图中Q（2， 2）点
left[i+j] = 4, 对应第标号 4 的那条左斜线
right[7+i-j] = 7, 对应第标号 7 的那条右斜线
用递归实现
#include<stdio.h>
#include<stdlib.h>
// 注意，以下都是全局变量
int col[8] = {0};
int left[15] = {0};
int right[15] = {0};
int Q[8];
int cut = 0;
/*输出*/
void print(){
printf("\n\n");
printf("第%d组\n",++cut);
for(int i=0; i<8; ++i){
for(int j=0; j<8; ++j){
if(Q[i]==j)
printf(" Q");
else
printf(" X");
}
printf("\n");
}
}
/*求八皇后解*/
void Queen(int i){
int j;
for(j=0; j<8; ++j){
if(!col[j]&&!left[i+j]&&!right[7+i-j]){
Q[i] = j;
col[j] = left[i+j] = right[7+i-j] = 1;
if(i<7)
Queen(i+1); // 跳到下一行
else{
print();
}
//此时递归回来了，代表该位置的Q不满足。故抹掉当前所在行的放好的皇后Q。继续向后移动（列）
col[j] = left[i+j] = right[7+i-j] = 0;
}
}
}
//主函数
int main(void){
int i;
Queen(0);
}
以上是我在学习过程中对于回朔算法问题的总结，若有不足之处，欢迎评论。
