N-Queens

lc 51

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

所有的皇后不能在同一行，不能在同一列。也不能在对角线上

这里用了一个数组来记录每一row的index位置，还有个有意思的地方判断对角线，就是 column - 前面几行皇后所在的column的位置，等于行数减去行数

时间复杂度书上说 i s lower bouded by the number of nonattacking placements. no exact form is know tfor this quantity it tend to be n!/c^n

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if (n == 0) return result;
        int[][] index = new int[n][n];
        helper(result, n, new ArrayList<>(), 0, index);
        return result;
    }

    private void helper(
        List<List<String>> result,
        int n,
        List<String> list,
        int start,
        int[][] index
    ) {
        if (list.size() == n) {
            result.add(new ArrayList<>(list));
            return;
        }
        if (start == n) return;
        //every column
        for (int i = 0; i < n; i++) {
            if (!checkValid(index,start, i)) {
                continue;
            }
            index[start][i] = 1;
            list.add(generateQ(n, i));
            helper(result, n , list, start + 1, index);
             index[start][i] = 0;
            list.remove(list.size() - 1);
        }
    }

    private boolean checkValid(int[][] index, int curRow, int curColumn) {
        //checkColumn
        for (int i = 0; i < index.length; i++) {
            if (i == curRow) continue;
            if (index[i][curColumn] == 1) return false;
        }

        //checkDoubleCrossLine
        for (int i = 0; i < index.length; i++) {
            for (int j = 0; j < index.length; j++) {
                if (i == curRow || j == curColumn) continue;
                if (Math.abs(i - curRow) == Math.abs(j - curColumn)) {
                    if (index[i][j] == 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    private String generateQ(int n, int position) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i != position) {
                sb.append('.');
            } else {
                sb.append('Q');
            }
        }
        return sb.toString();
    }
}

lc 52 N-QUEENS ii

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

class Solution {
    public static int sum;
    public int totalNQueens(int n) {
        sum = 0;
        int[][] visited = new int[n][n];
        helper(n, 0, visited);
        return sum;
    }
    public void helper(int n, int curRow, int[][] visited) {
        if (curRow >= n) {
            sum++;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!isValid(n, curRow, i, visited)) continue;
            visited[curRow][i] = 1;
            helper(n, curRow + 1, visited);
            visited[curRow][i] = 0;
        }
    }
    public boolean isValid(int n, int curRow, int curColumn, int[][] visited) {
        //checkColumn
        for (int i = 0; i < n; i++) {
            if (i == curRow) continue;
            if (visited[i][curColumn] == 1) return false;
        }
        //checkCrossline
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == curRow || j == curColumn) continue;
                if (Math.abs(i - curRow) == Math.abs(j - curColumn)) {
                    if (visited[i][j] == 1) return false;
                }
            }

        }
        return true;
    }
}