八皇后

问题描述：

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路：

先申请一个二维数组board，行用level表示，列用line表示，遍历二维数组的每一行中的每一个元素，如果这个位置的上方，左上方，右上方有其他的皇后，那么这一行中皇后可能所在的位置将往后移动（board[level][line+1]）,如果这一行可以找到皇后的位置，那么继续遍历下一行。如果这一行没有皇后所在的位置，那么就会回溯到上一行(board[level-1][i]), 将上一行皇后可能所在的位置继续往后移动（重复执行蓝色字体部分），level表示行的下标，因此当level等于8的时候表示最后一行也执行完毕，所以这就是一个解。

此图为一个解：

代码：

class EigthQueen{
    public static int count=0;//表示八皇后的个数
    public static int n=8;//棋盘的长宽度
    public static void main(String[] args){
        int [][]board=new int[n][n];
        EigthQueen(board,0);
        System.out.println("一共有"+count+"个解");
    }
    public static void EigthQueen(int [][]board,int level){
        //如果行数的下标是从0到7，因此如果行数已经达到了8的话就意味着这是一个解
        if(level==8){
            count++;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    System.out.print(" "+board[i][j]);
                }
                System.out.println();
            }
            System.out.println("这是第"+count+"个");

        }else{
/*如果行数没有达到8那么先将棋盘先拷贝一份，如果直接在原棋盘上进行操作的话，下次再调用这个棋盘的时候必须清除上次所进行的操作*/
            int [][]newboard=new int[n][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    newboard[i][j]=board[i][j];
                }
            }
            for(int line=0;line<8;line++){
                //判断每一行的每一个位置是否与其他皇后冲突
                if(isNoDanger(newboard,level,line)){
                    //如果这个位置不冲突的话先将这一行清零，
                    for(int i=0;i<n;i++){
                        newboard[level][i]=0;
                    }
                    newboard[level][line]=1;
                    EigthQueen(newboard,level+1);
                }     
            }
        }
    }
    public static boolean isNoDanger(int [][]board,int level,int line){
        //此行的下方没有下过棋子所以只用考虑上方，左上，右上三个方向。
        //上方
        for(int i=level-1;i>=0;i--){
            if(board[i][line]==1){
                return false;
            }
        }
        //左上
        for(int i=level-1,j=line-1;i>=0&&j>=0;i--,j--){
            if(board[i][j]==1){
                return false;
            }   
        }
        //右上
        for(int i=level-1,j=line+1;i>=0&&j<n;i--,j++){
            if(board[i][j]==1){
                return false;
            } 
        }
        return true;
    } 
}