八皇后问题

如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任两个皇后都不能处于同一条横行、纵行或斜线上。

先从第一列开始放， 并构造一个专门存放皇后位置的一维数组，该数组的下标代表棋盘（二维数组）的列，数组的值代表皇后在棋盘中每一列的行号，以此来记录皇后的位置。
当一列一列往下放皇后的时候，通过刚才的数组来判断当前要放皇后的列哪些行可以放那些行不可以放，这就需要在构造一个boolean类型的数组，这个数组与当前的列形成映射。
在不断的往后面的列放皇后的时候，到了某一列发现这一列的所有行都没法放皇后，这时就重新去放上一列的皇后，再继续往下放，如果还没有，继续回到上一列...一直重复这个过程，直到找到一个可行放法。

public class Queen {

    // 方案数量
    private static int num = 0;
    // 皇后的数量
    private final static int MAX_QUEEN = 8;
    // 数组中存放皇后在每一列中的第几行的索引值，目的是记录已放好的皇后位置，
    // 后面以此来确定准备放皇后的列有哪些位置可以放那些位置不可以放
    public static int[] queenIndexArray = new int[MAX_QUEEN];

    /**
     * 
     * @param colIndex
     *            从第几列放皇后
     */
    public void solution(int colIndex) {
        // 记录要放皇后的列的哪些行不能放哪些行能放
        boolean[] queenPlaceOfRow = new boolean[MAX_QUEEN];
        // 找出能放皇后的位置
        for (int curColIndex = 0; curColIndex < colIndex; curColIndex++) {
            // 行方向上不能放的位置记录在queenPlaceOfRow数组中
            queenPlaceOfRow[queenIndexArray[curColIndex]] = true;
            // 找出当前正在遍历的列与要放皇后的列之间的差值，
            // 以此来确定斜对角方向那些位置可以放哪些位置不能放
            int colGap = colIndex - curColIndex;
            // 正斜方向   -->  /
            // 如果正在遍历的列中皇后所在行的行索引大于等于colGap则该行不能放
            if (queenIndexArray[curColIndex] - colGap >= 0) {
                queenPlaceOfRow[queenIndexArray[curColIndex] - colGap] = true;
            }

            // 反斜方向   -->  \
            // 如果正在遍历的列中皇后所在行的行索引加上colGap小于等于最大的列索引则该行不能放
            if (queenIndexArray[curColIndex] + colGap <= MAX_QUEEN - 1) {
                queenPlaceOfRow[queenIndexArray[curColIndex] + colGap] = true;
            }
        }
        
        // 开始放皇后， 遍历queenPalce数组，里面记录着这一列中那些行能放那些不能放
        for(int i = 0; i < MAX_QUEEN; i++){
            // 不能放
            if(queenPlaceOfRow[i]){
                continue;
            }
            // 如果能放就把该列的行索引值放到queenIndexArray中
            queenIndexArray[colIndex] = i; 
            
            // 如果没放到最后一列，用回溯法继续寻找可放位置
            if(colIndex < MAX_QUEEN - 1){
                solution(colIndex + 1); 
            } else {
                // 找到一种方法
                num++;
                
                printResult();
            }
        }
    }

    // 打印结果
    private void printResult() {
        
        System.out.println("第"+num+"中放法：");
        // 遍历行
        for(int i = 0; i < MAX_QUEEN; i++){
            // 遍历列
            for(int j = 0; j < MAX_QUEEN; j++){
                // queenIndexArry存放着
                // 二维数组每一列的皇后所在的行索引，即为queenIndexArray[j]
                if(queenIndexArray[j] == i){
                    System.out.print("♟    ");
                } else {
                    System.out.print("♢     ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args){
        Queen queen = new Queen();
        queen.solution(0);
    }
}

结果：

第92中放法：
♢     ♢     ♟    ♢     ♢     ♢     ♢     ♢     
♢     ♢     ♢     ♢     ♢     ♟    ♢     ♢     
♢     ♢     ♢     ♟    ♢     ♢     ♢     ♢     
♢     ♟    ♢     ♢     ♢     ♢     ♢     ♢     
♢     ♢     ♢     ♢     ♢     ♢     ♢     ♟    
♢     ♢     ♢     ♢     ♟    ♢     ♢     ♢     
♢     ♢     ♢     ♢     ♢     ♢     ♟    ♢     
♟    ♢     ♢     ♢     ♢     ♢     ♢     ♢