经典递归问题，八皇后

• 此问题解法转自 Alex Yu 博客园
  未经询问，抱歉。如若不妥马上删除

• 先创建个皇后类，保存这一个皇后在一行中的具体位置，而该皇后的行数，有主程序的皇后数组保存。

public class Queen {
    private int position;
    public Queen(){
        
    }
    public int getPosition() {
        return position;
    }
    public void setPosition(int position) {
        this.position = position;
    }
}

• 棋盘类,设置0可以摆放皇后，1不可。下面程序里，设置无效位置即为将数组相应位置+1；

public class Bord {
    
    private int size;  
    private int[][] a;
    
    public Bord(int bsize){
        this.size=bsize;
        a=new int[size][size];//初始化每个都为0，都可以摆放
        for(int i=0;i<size;i++)
            for(int j=0;j<size;j++)
                a[i][j]=0;
    }

• 主程序

public class QueenSolve {
    int queensize;   //皇后的数量
    ArrayList<Queen> queens;  //皇后数组，数组中的索引值表示是第几行的皇后
    Bord bord;  //新建个棋盘
    int numSolutions;  //总共解法的次数
    
    public QueenSolve(int size) {  //解法初始化的类
        queensize=size;
        queens=new ArrayList<>();
        for(int i=0;i<queensize;i++)   //新建皇后，并放进去
            queens.add(new Queen());
        bord=new Bord(queensize);  //棋盘
        numSolutions=0;  //初始化次数
        
    }
    /*主类*/
    public static void main(String[] args) {  
        // TODO Auto-generated method stub
        
        QueenSolve queenSolve=new QueenSolve(8);  //初始化，然后调用解法
        queenSolve.solve();
        
        
    }
    public void solve(){
        System.out.println("Start solve....");  //解题在下面方法完成，所以只会输出一次
        putQueen(0); //开始，调用
    }
    
    private void putQueen(int index){
        int row=index;
        for(int col=0;col<queensize;col++){ //从当前行的第一个位置开始
            /*如果位置为0，则有效，把该行的皇后放进去*/
            if(bord.getA()[row][col]==0){  
                queens.get(row).setPosition(col);  //设置该行皇后位置
                /*下面是把本次循环无效位置设置为0，因为不会再在上面摆了，所以只要把下面的设置为1就行了
                  这不影响我们打印因为，每个皇后的位置已经保存过了*/
                for (int i = row + 1; i < bord.getSize(); i++) {
                    bord.getA()[i][col] ++;   //皇后位置所在的那一列，一个循环往下设置一个，直到结束全部设置完成
                    if (row + col - i >= 0) {  //如果往左的对角线元素存在，把他设置为1
                        bord.getA()[i][row + col - i] ++; 
                    }
                    if (i + col - row < bord.getSize()) {//如果往右的对角线元素存在，把他设置为1
                        bord.getA()[i][i + col - row] ++;
                    }
                }
                
                if (row == bord.getSize()-1) { //如果已经是最后一行了，就说明解题结束，次数加1在打印
                    numSolutions++;
                    printSolution(numSolutions);
                }else {
                    putQueen(row+1);//执行到这里，就是这一行已经摆好位置了，换下一行去处理
                }
                //上面一句执行，如果下一行每一行都为1，说明这一行走错了，把这一行的操作退回去，这个col是错误的，
                //执行完退回操作，回到上面继续下一个col
                for (int i = row + 1; i < bord.getSize(); i++) { 
                    bord.getA()[i][col] --;
                    if (row + col - i >= 0) {
                        bord.getA()[i][row + col - i] --;
                    }
                    if (i + col - row < bord.getSize()) {
                        bord.getA()[i][i + col - row] --;
                    }
                }
            }
        }
    }
    
    private void printSolution(int i){
        System.out.println("The "+i+ " solution is:");
        for (int j = 0; j < bord.getSize(); j++) {
            for (int k = 0; k < bord.getSize(); k++) {
                //是那个位置的话输出*，不是输出-
                System.out.print(queens.get(j).getPosition() == k ? " * ":" - ");
            }
            System.out.println();
        }
        System.out.println();
    }
}