52. N-Queens II

    /*
     * 52. N-Queens II 
     * 2015.12.16 by Mingyang
     * 1.长度标准：无
     * 2.可选的范围：在row固定的情况下，遍历所有的列
     * 3.往前走一步：如果某一个col可以就检查是否validate，并且存上column的信息
     * 4.后退一步：棋盘上的值改回来
     * 5.特别的case：row走完了
     * 6.关于重复：无
     */
    int res;
    public int totalNQueens(int n) {
        res = 0;
        if (n <= 0)
            return res;
        int[] loc = new int[n];
        dfs(loc, 0, n);
        return res;
    }
    public void dfs(int[] loc, int cur, int n) {
        if (cur == n) {
            res += 1;
            return;
        }
        for (int i = 0; i < n; i++) {
            loc[cur] = i;
            if (isValid(loc, cur))
                dfs(loc, cur + 1, n);
        }
    }
    public boolean isValid(int[] loc, int cur) {
        for (int i = 0; i < cur; i++) {
            if (loc[i] == loc[cur] || Math.abs(loc[i] - loc[cur]) == (cur - i))
                return false;
        }
        return true;
    }