回溯法：N皇后问题(Java)

题目描述：

思路：首先要创建一个二维数组初始化棋盘，根据题意，可以先在第一行第一列放一个皇后，由于皇后会攻击处在同一行、同一列或同一斜线上的棋子，就需要再定义一维数组来分别判断它的列冲突、左斜线上的冲突和右斜线上的冲突，因为已经找到第一行的位置了，显然该行其它列已经放不了皇后，就递归调用下一行，然后通过循环列进行第二行的列处理，以此往复。

上面用递归的原因是：在第一行第一列放皇后不一定是最后能放下最多皇后的方法，因此就采用递归-回溯的办法，如果发现这个放法行不通(某一次递归调用的次数没有n次，说明有行放不了皇后，不是最优的放法)就回溯到最开始的状态，再在第一行的第二列放皇后。能完整放满所有行的放法就是最优的，将其打印，当处理完第一行所有列的皇后放法后，就相当于找完了所有的放法。

完整代码：

public class NQueen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入边长n:");
        int n = scanner.nextInt();
        boolean[] y = new boolean[n];   // 记录列冲突
        //根据规律发现在 n*n 的棋盘上一共有 2 * n - 1 左/右斜线
        boolean[] left = new boolean[2 * n - 1];  // 左斜线上冲突
        boolean[] right = new boolean[2 * n - 1];  // 右斜线冲突
        char[][] table = new char[n][n];  //二维数组表示棋盘
        init(table);  //初始化
        dfs(0, n, table, y, left, right);  //初始递归调用
    }
 
    static void init(char[][] table){
        for (char[] t : table) {
            Arrays.fill(t, '.');  //将棋盘初始化成"."
        }
    }
 
    static void dfs(int i, int n, char[][] table, boolean[] y, boolean[] left, boolean[] right) {  //递归方法，用来处理每一行皇后的放置
        if (i == n) {   // 处理完所有行，找到一个解了，可以结束递归
            System.out.println("-------------------");
            for (char[] t : table) {  //重新遍历棋盘，打印皇后的位置
                System.out.println(new String(t));
            }
            return;
        }
        for (int j = 0; j < n; j++) {  //列的循环
            if (y[j] || left[i + j] || right[n - 1 - (i - j)]) {  //如果列，左斜线，右斜线上有冲突应该跳过这次递归进入下次循环
                continue;
            }
            table[i][j] = 'Q';  //在当前行的当前列放入皇后
            y[j] = left[i + j] = right[n - 1 - (i - j)] = true;  //更新，ca[j]:此列  cb[i + j]:左斜线  cc[n - 1 - (i - j)]:右斜线 均有冲突(true)
            dfs(i + 1, n, table, y, left, right);  //继续递归，开始在第 i+1 行(下一行)放入元素
            //回溯，若递归没有成功，能恢复到递归前的状态
            table[i][j] = '.';
            y[j] = left[i + j] = right[n - 1 - (i - j)] = false;
        }
    }
}