回溯算法

回溯算法(back tracking)是一种选优搜索法, 又称试探法, 按选优条件向前搜索, 以达到目标。当探索到某一步时, 发现原先选择并不优或达不到目标, 就退回一步重新选择, 这种走不通就退回再走的技术为回溯法, 而满足回溯条件的某个点称为回溯点

八皇后问题

八皇后问题是一个古老的问题。该问题是十九世纪著名的数学家高斯1850年提出: 在8*8格的国际象棋上摆放8个皇后, 使其不能互相攻击, 即任意两个皇后都不能处于同一行, 同一列或同一斜线上。

八皇后问题解题思路:

问题简化: 将八皇后问题转化为四皇后问题, 并用回溯法来找到它的解

目的: 在4*4棋盘上, 使得4个皇后不能在同行同列以及同斜线上。

Step 1

在棋盘第一个位置放好第一个皇后, 被涂黑的地方不能放皇后

Q1

Step 2 第二行的皇后只能放在第三格或第四格, 比如我们放第三格

Q1
		Q2

Step 3

可以看到再难放下第三个皇后, 此时就要用回溯算法了。我们把第二个皇后更改位置, 此时能放下第三个皇后了

Q1
			Q2

Step 4

虽然是能放置第三个皇后, 但是第四个皇后又无路可走了。返回上层调用(3号皇后), 而3号也别无可去, 继续回溯上层调用(2号), 2号已无路可去, 继续回溯上层(1号), 于是1号皇后改变位置, 继续回溯

	Q1

重点看下面这段代码, 这段代码虽短, 但是确是整个算法的核心和灵魂

第一次进来, row=0, 意思是要在第一行摆皇后, 只要传进来的row参数不是8, 表明还没有出结果, 就都不会走if里面的return, 那么就进入到for循环里面, column从0开始, 即第一列。此时第一行第一列肯定符合要求(即check方法肯定通过), 能放下皇后, 因为还没有其他皇后来干扰。

关键是check方法通过了之后, 在if里面又会调用自己, row加了1, 表示摆第二行的皇后。第二行的皇后在走for循环的时候, 分两种情况, 第一种情况: for循环没有走到头就通过check方法了, 这样就继续调用自己, row再加1。第二种情况: for 循环走到头了都没有通过check方法的, 说明第二行根本一个皇后都摆不了, 也触发不了递归, 此时控制第一行皇后位置的for循环column加1, 即第一行的皇后往后移一格, 即摆在第一行第二列的位置上, 然后再往下走, 重复上述逻辑

注意: 一定要添加清零的代码, 它只有在皇后摆不下去的时候会执行清0的动作, 如果皇后摆放很顺利的话是不会走这个清0的动作, 因为已经提前走if里面的return方法结束了。

八个位置太多, 还是按照之前4*4的棋盘, 放4个皇后

第一种放法: 在之前已经聊过, 就不写了, 直接上第二种放法

Step1: 在第一行第二个位置放置第一个皇后

	Q1

Step2: 在第二行第四列放第二个皇后

	Q1
			Q2

Step3: 在第三行第一列放置第三个皇后

	Q1
			Q2
Q3

Step 4:

	Q1
			Q2
Q3
		Q4

一不小心, 就完成了4*4的棋盘上放置4个皇后

下面是8皇后算法的java版本

public static int[][] arry=new int[8][8];//棋盘，放皇后
public static int map=0;//存储方案结果数量

public static void main(String[] args) {
    // TODO Auto-generated method stub

    System.out.println("八皇后问题");
    findQueen(0);
    System.out.println("八皇后问题共有："+map+"种可能");
}

public static void findQueen(int i){//寻找皇后节点
    if(i>7){//八皇后的解  
        map++;
        print();//打印八皇后的解
        return;
    }
    
    for(int m=0;m<8;m++){//深度回溯,递归算法
        if(check(i,m)){//检查皇后摆放是否合适
            arry[i][m]=1;
            findQueen(i+1);
            arry[i][m]=0;//清零，以免回溯的时候出现脏数据
            }
    }   
}

public static boolean check(int k,int j){//判断节点是否合适
    for(int i=0;i<8;i++){//检查行列冲突
         if(arry[i][j]==1){
                return false;
         }
    }
    for(int i=k-1,m=j-1; i>=0 && m>=0; i--,m--){//检查左对角线
        if(arry[i][m]==1){
                return false;
        }
    }
    for(int i=k-1,m=j+1; i>=0 && m<=7; i--,m++){//检查右对角线
        if(arry[i][m]==1){
                return false;
        }
    }
    return true;
}

public static void print(){//打印结果
    System.out.print("方案"+map+":"+"\n");
    for(int i=0;i<8;i++){
        for(int m=0;m<8;m++){
            if(arry[i][m]==1){  
                //System.out.print("皇后"+(i+1)+"在第"+i+"行，第"+m+"列\t");
                System.out.print("o ");
            }
            else{
                    System.out.print("+ ");
            }
        }
        System.out.println();
    }
    System.out.println();
}