题解 | #N皇后问题#

import java.util.*;


public class Solution {
    int count = 0;
    boolean[] columns;  // 记录同一列是否已放置皇后
    boolean[] line1;  // 记录从左上到右下的对角线是否已放置皇后
    boolean[] line2; // 记录从左下到右上的对角线是否已放置皇后

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        columns = new boolean[n];
        line1 = new boolean[2 * n];
        line2 = new boolean[2 * n];
	    // 从第一行开始放置皇后
        dfs(n, 0);
        return count;
    }

    private void dfs(int n, int r) {
		// 所有行都放了一个皇后，为其中一个答案，count++
        if (r == n) {
            count++;
            return;
        }

        for (int j = 0; j < n; j++) {
		    // 判断当前行:r, 当前列：c以及对角线是否都不存在皇后
            if (!columns[j] && !line1[r + j] && !line2[r - j + n]) {
			    // 当前行放置好
                columns[j] = line1[r + j] = line2[r - j + n] = true;
			    // 到下一行找合适的列放置
                dfs(n, r + 1);
			    // 回溯
                columns[j] = line1[r + j] = line2[r - j + n] = false;
            }
        }
    }
}