N-Queens I

The n-queens puzzle is the problem of placing n queens on an n×n
chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens
puzzle.

Each solution contains a distinct board configuration of the n-queens'
placement, where 'Q' and '.' both indicate a queen and an empty space
respectively.

For example, There exist two distinct solutions to the 4-queens
puzzle:

[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]

回溯法

思路

还是回溯问题, 对于每一个行的每一个格都测试, 如果合理就继续下一行, 不合理就回溯. 这里用一个长度n的数组来存储每一行的情况.
eg:

A[] = [1,0,2,3]表达含义是：     当前4个皇后所在坐标点为：[[0,1],[1,0],[2,2],[3,3]]     相当于：A[0] = 1, A[1] = 0, A[2] = 2, A[3] = 3 

这样一来回溯时候就不用对数组进行修改了.

复杂度

时间O(n!) 空间O(n)

代码

public int totalNQueens(int n) {    if (n <= 0) {        return 0;    }    int[] visit = new int[n];    int[] res = new int[1];    helper(res, n, visit, 0);    return res[0];}public void helper(int[] res, int n, int[] visit, int pos) {    if (pos == n) {        res[0]++;        return;    }    for(int i = 0; i < n; i++) {        visit[pos] = i;        if(isValid(visit, pos)) {helper(res, n, visit, pos + 1);        }    }}public boolean isValid(int[] visit, int pos) {    for (int i = 0; i < pos; i++) {        if (visit[i] == visit[pos] || pos - i == Math.abs(visit[pos] - visit[i])) {return false;        }    }    return true;}

N-Queens II

Follow up for N-Queens problem.

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

回溯法

思路

与I相同, 只不过不需要返回结果, 而返回结果数量. 所以维护一个数组(不能用int 因为java是按引用传递)

时间O(n!) 空间O(n)

代码

public List<List<String>> solveNQueens(int n) {    List<List<String>> res = new ArrayList<List<String>>();    if (n <= 0) {        return res;    }    int[] visit = new int[n];    helper(res, n, visit, 0);    return res;}public void helper(List<List<String>> res, int n, int[] visit, int pos) {    if (pos == n) {        List<String> tem = new ArrayList<String>();        for (int i = 0; i < n; i++) {StringBuilder sb = new StringBuilder();for (int j = 0; j < n; j++) {    if (visit[i] == j) {        sb.append("Q");    } else {        sb.append(".");    }}tem.add(sb.toString());        }        res.add(tem);        return;    }    for(int i = 0; i < n; i++) {        visit[pos] = i;        if(isValid(visit, pos)) {helper(res, n, visit, pos + 1);        }    }}public boolean isValid(int[] visit, int pos) {    for (int i = 0; i < pos; i++) {        if (visit[i] == visit[pos] || pos - i == Math.abs(visit[pos] - visit[i])) {return false;        }    }    return true;}