中国有一句古话，叫做“不撞南墙不回头"，生动的说明了一个人的固执，有点贬义，但在软件编程中，这种思路确是一种解决问题最简单的算法，它通过一种类似于蛮干的思路，一步一步地往前走，每走一步都更靠近目标结果一些，直到遇到障碍物，我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法，最终达到目的地。当然整个过程需要很多往返，这样的前进方式，效率比较低下。

适用于那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题。  在8*8国际象棋棋盘上，要求在每一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。国际象棋的棋盘如下图所示：

 基本思路如上面分析一致，我们采用逐步试探的方式，先从一个方向往前走，能进则进，不能进则退，尝试另外的路径。首先我们来分析一下国际象棋的规则，这些规则能够限制我们的前进，也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉

1）x=row(在纵向不能有两个皇后)

2) y=col（横向）

3）col row = y x;（斜向正方向）

4) col - row = y-x;（斜向反方向）

遇到上述问题之一的时候，说明我们已经遇到了障碍，不能继续向前了。我们需要退回来，尝试其他路径。

我们将棋盘看作是一个8*8的数组，这样可以使用一种蛮干的思路去解决这个问题，这样我们就是在8*8=64个格子中取出8个的组合，C(64,80) = 4426165368,显然这个数非常大，在蛮干的基础上我们可以增加回溯，从第0列开始，我们逐列进行，从第0行到第7行找到一个不受任何已经现有皇后攻击的位置，而第五列，我们会发现找不到皇后的安全位置了，前面四列的摆放如下:

(点击切换版式)

 第五列的时候，摆放任何行都会上图所示已经存在的皇后的攻击，这时候我们认为我们撞了南墙了，是回头的时候了，我们后退一列，将原来摆放在第四列的皇后（3，4）拿走，从（3，4）这个位置开始，我们再第四列中寻找下一个安全位置为（7，4），再继续到第五列，发现第五列仍然没有安全位置，回溯到第四列，此时第四列也是一个死胡同了，我们再回溯到第三列，这样前进几步，回退一步，最终直到在第8列上找到一个安全位置（成功）或者第一列已经是死胡同，但是第8列仍然没有找到安全位置为止

总结一下，用回溯的方法解决8皇后问题的步骤为：

1）从第一列开始，为皇后找到安全位置，然后跳到下一列

2）如果在第n列出现死胡同，如果该列为第一列，棋局失败，否则后退到上一列，在进行回溯

3）如果在第8列上找到了安全位置，则棋局成功。

8个皇后都找到了安全位置代表棋局的成功，用一个长度为8的整数数组queenList代表成功摆放的8个皇后，数组索引代表棋盘的col向量，而数组的值为棋盘的row向量，所以(row,col)的皇后可以表示为(queenList[col],col),如上图中的几个皇后可表示为：queenList[0] = 0; queenList[1] = 3; queenList[2] = 1; queenList[3] = 4; queenList [4]= 2;

//8 Queen 递归算法

//如果有一个Q 为 chess[i]=j;

//则不安全的地方是 k行 j位置,j k-i位置,j-k i位置

class Queen8{

static final int QueenMax = 8;

static int oktimes = 0;

static int chess[] = new int[QueenMax];//每一个Queen的放置位置 public static void main(String[] args) {

long time = System.currentTimeMillis();

for (int i=0;i<QueenMax;i )chess[i]=-1;

placequeen(0);

System.out.println("\n\n\n八皇后共有" oktimes "个解法 ");

System.out.println((System.currentTimeMillis() - time) "毫秒");

}

public static void placequeen(int num){ //num 为现在要放置的行数

int i=0;

boolean qsave[] = new boolean[QueenMax];

for(;i<QueenMax;i )

qsave[i]=true;

//下面先把安全位数组完成

i=0;//i 是现在要检查的数组值

while (i<num){

qsave[chess[i]]=false;

int k=num-i;

if ( (chess[i] k >= 0) && (chess[i] k < QueenMax) )

qsave[chess[i] k]=false;

if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) )

qsave[chess[i]-k]=false;

i ; }

//下面历遍安全位

for(i=0;i<QueenMax;i ){

if (qsave[i]==false) continue;

if (num<QueenMax-1){

chess[num]=i;

placequeen(num 1); }

else{ //num is last one

chess[num]=i;

oktimes ;

System.out.println("这是第" oktimes "个解法 如下:");

System.out.println(" 第n行: 1 2 3 4 5 6 7 8 ");

for (i=0;i<QueenMax;i ){

String row="第" (i 1) "行: ";

if (chess[i]==0);

else for(int j=0;j<chess[i];j )

row =" -";

row =" ";

int j = chess[i];

while(j<QueenMax-1){

row =" -";

j ;}

System.out.println(row);

} } }//历遍完成就停止

} }