问题

Place eight chess queens on an 8x8 chessboard so that
no two queens threaten each other. Thus, a solution
requires that no two queens share the same row,
column, or diagonal.

说明

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

代码实现

import java.util.Arrays;


public class EightQueens {
    // 存放queen的位置
    int[] queens = {0, 0, 0, 0, 0, 0, 0, 0};
    int max = 8;
    int seq=1;

    // i 代表横坐标 n 代表纵坐标
    public void put(int n) {

        for (int i = 0; i < max; i++) {
            queens[n] = i;
            if (!check(n)) {
                if (n == max - 1) {
                    printQueensPosition();
                } else {
                    put(n + 1);
                }
            }

        }
    }

    public boolean check(int n) {
        for (int i = 0; i < n; i++) {
            // 判断横线 和 斜线上是否queens
            if (queens[i] == queens[n]||Math.abs(queens[i]-queens[n])==(n-i)) {
                return true;
            }
        }
        return false;
    }


    private void printQueensPosition() {
        System.out.printf("第 %d 种放置方法\n",seq);
        System.out.println(Arrays.toString(queens));
//        String tmp="";
//        int pos=0;
//        for (int i = 0; i < queen.length ; i++) {
//            pos = queen[i];
//            for (int j = 0; j <queen.length ; j++) {
//                if(pos==j){
//                    tmp+=" Q ";
//                }else{
//                    tmp+=" . ";
//                }
//            }
//            System.out.println(tmp);
//            tmp="";
//        }
        seq++;
    }

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        eightQueens.put(0);
    }
}

说明

该题使用数组记录皇后位置，并制作虚拟棋盘（i 代表行，n代表列）放置皇后。 通过放置-检查-放置的递归来完成八皇后问题。