回溯法(traceback)

八皇后问题(EightQueen)

/**
 * 算法：回溯法
 * 问题：八皇后 
 * @author win
 */
public class EightQueen {
    public static int num = 0;//累计方案
    public static final int MAXQUEEN = 8;
    public static int[] cols = new int[MAXQUEEN];//定义cols数组，表示八列棋子摆放的位置
    /***
     * @param n 填第n列的皇后
     */
    public void getCount(int n){
        boolean [] rows = new boolean[MAXQUEEN];//记录每列每个方格是否可以放皇后。为true表示不能放
        for(int m =0;m<n;m++){
            rows[cols[m]] = true;
            int d = n - m;//斜对角
            //正斜方向
            if(cols[m] - d>=0){
                rows[cols[m] - d] = true;
            }
            //反斜方向
            if((cols[m]+d)<=MAXQUEEN-1){
                rows[cols[m] + d] = true;
            }
        }
        //到此知道了哪些位置不能放皇后
        for(int i = 0;i<MAXQUEEN;i++){
            if(rows[i]){
                //不能放
                continue;
            }
            cols[n] = i;
            if(n<MAXQUEEN-1){
                getCount(n+1);
            }else{
                //如果n = MAXQUEEN-1;表示找到了一套完整的方案
                num++;
                printQueen();
            }
            //下面可能仍有合法位置
        }
    }
    private void printQueen() {
        System.out.println("第"+num+"种方案");
        for(int i = 0;i<MAXQUEEN;i++){
            for(int j=0;j<MAXQUEEN;j++){
                if(i == cols[j]){
                    System.out.print("0 ");
                }else{
                    System.out.print("+ ");
                }
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        EightQueen eightQueen = new EightQueen();
        eightQueen.getCount(0);
    }
}