N-Queens

add better solutions here

N-Queens I, 维护一个list, list[i]代表了这个queen是在第i行的第list[i]列的，每次在把一个新的queen加进去前判断一下，加入后会不会引起棋盘的invalid。 invalid的条件在这里是有两个queen在同一列，在同一个45度对角线，在同一个135度对角线。 同一45度对角线的两个queen, row1 + col1 == row2 + col2。 在同一135度对角线的两个queen, row1 - col1 = row2 - col2。

这道题我一开始做错了，原因是我维护了一个pos变量，把这题当成一个combination类的变形，其实这题是permutation类的变形，每次for循序的起始index都是0。

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

        List<Integer> list = new ArrayList<Integer>();
        dfs(result, list, n);
        return result;
    }

    private void dfs(List<List<String>> result, List<Integer> list, int n) {
        if (list.size() == n) {
            result.add(build(list, n));  
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!isValid(list, i)) {
                continue;
            }

            list.add(i);
            dfs(result, list, n);
            list.remove(list.size() - 1);
        }
    }

    private List<String> build(List<Integer> list, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            StringBuffer sb = new StringBuffer();
            int col = list.get(i);
            for (int j = 0; j < n; j++) {
                if (j == col) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            board.add(sb.toString());
        }

        return board;
    }

    private boolean isValid(List<Integer> list, int col) {
        int row = list.size();

        for (int i = 0; i < list.size(); i++) {
            int row2 = i, col2 = list.get(i);

            if (col == col2) {
                return false;
            }
            if (row + col == row2 + col2) {
                return false;
            }
            if (row - col == row2 - col2) {
                return false;
            }
        }

        return true;
    }
}

N-Queens II, 这题虽然是返回有多少种可能性，但是其实并不能用dp来解，还是要用dfs去搜。

public class Solution {
    public int totalNQueens(int n) {
        if (n <= 0) {
            return 0;
        }

        List<Integer> list = new ArrayList<Integer>();
        return dfs(list, n);
    }

    private int dfs(List<Integer> list, int n) {
        if (list.size() == n) {
            return 1;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (!isValid(list, i)) {
                continue;
            }

            list.add(i);
            sum += dfs(list, n);
            list.remove(list.size() - 1);
        }

        return sum;
    }

    private boolean isValid(List<Integer> list, int col) {
        int row = list.size();

        for (int i = 0; i < list.size(); i++) {
            int row2 = i, col2 = list.get(i);

            if (col == col2) {
                return false;
            }
            if (row + col == row2 + col2) {
                return false;
            }
            if (row - col == row2 - col2) {
                return false;
            }
        }

        return true;
    }
}