八皇后问题(递归回溯法)--Java实现-蒲公英云

八皇后问题(递归回溯法)--Java实现

一.题目

经典的八皇后问题是要将八个皇后放在棋盘上,任何两个皇后不能相互攻击(即没有两个皇后是在同一行,同一列或者同意对角线上).编写程序列出所有的解决方案和解决方案的总数.

二.代码及思想

package work22;
public class Test {
    public static int[][] array = new int[8][8];    //初始化棋盘
    public static int map;        //八皇后可能解的个数
    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        System.out.println("八皇后问题 : ");
        search(0);
        //System.out.println();
        System.out.println("八皇后一共有" + map + "个解");
    }
    public static void search(int i){
        if(i > 7){
            map++;
            print();
            return;        //return后会接着指向array[i][j]=0,然后继续for循环,寻找下一个合适的解
        }
        for(int j = 0; j < 8; j++){
            if(check(i, j)){
                array[i][j] = 1;
                search(i+1);
                array[i][j] = 0;        //清零,以免回溯的时候出现脏数据,当这一行都没有合适结点时被调用
            }
        }
    }
    public static boolean check(int i, int j){        //检查该结点是否符合条件
        for(int k = 0; k < i; k++){        //检查与该结点在一列上的元素是否有不为1的结点,且只检查在改结点上方的行,因为下方的行全为0,无需检查
            if(array[k][j] == 1){
                return false;
            }
        }
        for(int m = i-1, n = j-1; m>=0&& n>=0; m--, n--){        //检查左对角线上的元素
            if(array[m][n] == 1){
                return false;
            }
        }
        for(int m = i-1, n = j+1; m>=0&& n<=7; m--, n++){        //检查右对角线上的元素
            if(array[m][n] == 1){
                return false;
            }
        }
        return true;
    }
    public static void print(){        //打印符合条件结点的位置
        for(int i = 0; i < 8; i++){
            for(int j = 0; j < 8; j++){
                if(array[i][j] == 1){
                    System.out.print("[" + i + " ," + j + "]   ");
                }
            }
        }
        System.out.println();
    }
}

核心代码是search方法,该方法有一个参数i表示当前判断到第几行,if(i > 7)这个判断表示已经找到了一种情况(即行数已经超过7),然后调用print方法打印该种情况,并通过return语句返回到上一次递归中的array[i][j] = 0,将这种情况下的最后一个值清为0,并在此基础上接着for循环寻找改行下一个可能的值,若没有,则接着向上回溯.

解决八皇后问题使用的是递归回溯算法.