Massive Algorithms: LeetCode 51

LeetCode 51 - N-Queens

LeetCode - N-Queens | Darren's Blog
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.."]
]

Recursive Version:

private void solve(char[][] curr, int idx, int n, List<List<String>> ret, boolean[] col, boolean[] diag1, boolean[] diag2) { if (idx == n) { List<String> toAdd = new ArrayList<>(); for (int i = 0; i < n; i ++) { toAdd.add(String.valueOf(curr[i])); } ret.add(toAdd); return; } for (int j = 0; j < n; j ++) { if (col[j] || diag1[idx + n - j - 1] || diag2[idx + j]) { continue; } col[j] = true; diag1[idx + n - j - 1] = true; diag2[idx + j] = true; curr[idx][j] = 'Q'; solve(curr, idx + 1, n, ret, col, diag1, diag2); curr[idx][j] = '.'; col[j] = false; diag1[idx + n - j - 1] = false; diag2[idx + j] = false; } } public List<List<String>> solveNQueens(int n) { List<List<String>> ret = new ArrayList<>(); char[][] curr = new char[n][n]; for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { curr[i][j] = '.'; } } boolean[] col = new boolean[n]; boolean[] diag1 = new boolean[2 * n - 1]; boolean[] diag2 = new boolean[2 * n - 1]; solve(curr, 0, n, ret, col, diag1, diag2); return ret; }

https://segmentfault.com/a/1190000003762668
时间 O(N^2) 空间 O(N)

该方法的思路和暴力法一样，区别在于，之前我们判断一个皇后是否冲突，是遍历一遍当前皇后排列的列表，看每一个皇后是否冲突。这里，我们用三个集合来保存之前皇后的信息，就可以O(1)时间判断出皇后是否冲突。三个集合分别是行集合，用于存放有哪些行被占了，主对角线集合，用于存放哪个右上到左下的对角线被占了，副对角线集合，用于存放哪个左上到右下的对角线被占了。如何唯一的判断某个点所在的主对角线和副对角线呢？我们发现，两个点的行号加列号的和相同，则两个点在同一条主对角线上。两个点的行号减列号的差相同，则两个点再同一条副对角线上。

主对角线row + col，副对角线row - col

    List<List<String>> res = new LinkedList<List<String>>();;
    Set<Integer> rowSet = new HashSet<Integer>();
    Set<Integer> diag1Set = new HashSet<Integer>();
    Set<Integer> diag2Set = new HashSet<Integer>();
    
    public List<List<String>> solveNQueens(int n) {
        helper(new LinkedList<Integer>(), n, 0);
        return res;
    }
    
    public void helper(LinkedList<Integer> tmp, int n, int col){
        if(col == n){
            List<String> one = new LinkedList<String>();
            for(Integer num : tmp){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append('.');
                }
                sb.append('Q');
                for(int j = num + 1; j < n; j++){
                    sb.append('.');
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            // 对于列col，看皇后应该放在第几行
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                // 如果三条线上已经有占据的皇后了，则跳过该种摆法
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                // 用回溯法递归求解
                tmp.add(row);
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(tmp, n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
                tmp.removeLast();
            }
        }
    }

https://discuss.leetcode.com/topic/24329/share-my-java-dfs-solution-very-easy-to-understand

However, I suggest that let's use 3 boolean arrays instead. Let's compare the run time:

HashSet: 15ms, beats 17.85%
Boolean Array: 5ms, beats 91.44%

More Efficient? - Seems so. - List<String>

    private Set<Integer> col = new HashSet<Integer>();
    private Set<Integer> diag1 = new HashSet<Integer>();
    private Set<Integer> diag2 = new HashSet<Integer>();
    
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        dfs(res,new ArrayList<String>(), 0, n);
        return res;
    }
    private void dfs(List<List<String>> res, List<String> list, int row, int n){
        if (row == n){
            res.add(new ArrayList<String>(list));
            return;
        }
        for (int i = 0; i < n; i++){
            if (col.contains(i) || diag1.contains(row + i) || diag2.contains(row - i)) continue;
            
            char[] charArray = new char[n];
            Arrays.fill(charArray, '.');
            charArray[i] = 'Q';
            String rowString = new String(charArray);
            
            list.add(rowString);
            col.add(i);
            diag1.add(row + i);
            diag2.add(row - i);
            
            dfs(res, list, row + 1, n);
            
            list.remove(list.size() - 1);
            col.remove(i);
            diag1.remove(row + i);
            diag2.remove(row - i);
        }
    }

https://leetcode.com/discuss/59793/clean-back-tracking-java-solution-with-simple-explaination

https://leetcode.com/discuss/24717/comparably-concise-java-code

    private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, 
                        String[] board, List<String[]> res) {
        if (r == board.length) res.add(board.clone());
        else {
            for (int c = 0; c < board.length; c++) {
                int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;
                if (!cols[c] && !d1[id1] && !d2[id2]) {
                    char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    }
    
    public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], 
            new String[n], res);
        return res;
    }

I use three boolean[] array to keep tracking of the position the Queen take in the helper method.

boolean[] cols is for check if the certain column is taken.
I use two boolean[2*n] array to keep tracking of two diagonals.
for the diagonal in the \ direction (from left up corner to right down corner) the col - row will always be same e.g. (0,1), (1,2), (2,3) are on the same diagonal, the range of col - row can be (0-(n-1)) ~ ((n-1)-0), to make sure we can store the value in one array, we will add n to this, it will become to keep tracking of (col - row + n).
for the diagonal in the / direction (from right up corner to left down corner) the col + row will always be same e.g. (0,4), (1,3), (2,2), (3,1), (4,0) are on the same diagonal, the range of row + col can be 0 ~ (2*n-2)

public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<List<String>>(); helper(result, new ArrayList<String>(), 0, new boolean[n], new boolean[2*n], new boolean[2*n], n); return result; } private void helper(List<List<String>> result, List<String> board, int row, boolean[] cols,

boolean[] d1, boolean[] d2, int n){ if (row == n) { result.add(new ArrayList<String>(board)); } for (int col=0; col<n; col++){ int id1 = col - row + n; int id2 = col + row; if (!cols[col] && !d1[id1] && !d2[id2]){ char[] r = new char[n]; Arrays.fill(r, '.'); r[col] = 'Q'; board.add(new String(r)); cols[col] = true; d1[id1] = true; d2[id2] = true; helper(result, board, row+1, cols, d1, d2, n); board.remove(board.size()-1); cols[col] = false; d1[id1] = false; d2[id2] = false; } } }

时间 O(N^3) 空间 O(N)

因为n皇后问题中，同一列不可能有两个皇后，所以我们可以用一个一维数组来表示二维棋盘上皇后的位置。一维数组中每一个值的下标代表着对应棋盘的列，每一个值则是那一列中皇后所在的行。这样我们可以只对一个一维数组进行深度优先搜索，来找出对于每一列，我们的皇后应该放在哪一行。在下一轮搜索之前，我们先检查一下新构成的数组是否是有效的，这样可以剪掉不必要的分支。检查的方法则是看之前排好的每一个皇后是否冲突。

    List<List<String>> res;
    
    public List<List<String>> solveNQueens(int n) {
        res = new LinkedList<List<String>>();
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return res;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            List<String> one = new LinkedList<String>();
            // 构成表示整个棋盘的字符串
            for(int num : nqueens){
                // 构成一个形如....Q....的字符串
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append('.');
                }
                sb.append('Q');
                for(int j = num + 1; j < n; j++){
                    sb.append('.');
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            //选择下一列的数字
            // 比如之前已经选了13xxxxxx，下一列可以选6，形成136xxxxx
            for(int num = 0; num < n; num++){
                nqueens[i] = num;//
                // 如果是有效的，继续搜索
                if(isValid(nqueens, i)){//more readable: put here: nqueens[i] = num;
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            // 检查对角线只要判断他们差的绝对值和坐标的差是否相等就行了
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }

https://leetcode.com/discuss/67227/concise-java-solution-based-on-dfs
// Good variable name:

public ArrayList<String[]> solveNQueens(int n) {

        ArrayList<String[]> result = new ArrayList<String[]>();

        recursiveNQueens(n, 0, new int[n], result);

        return result;

}

    // If "currentRow" is n, we have reached a solution based on "queenInColumn",

    // and put it into "result"; Otherwise, we put a queen at each valid column

    // in Row "currentRow", and recursively work on the next row.

    private void recursiveNQueens(int n, int currentRow, int[] queenInColumn,

                                  ArrayList<String[]> result) {

        if (currentRow == n) {      // We have placed n queens

            // Construct a solution based on "queenInColumn"

            String[] solution = new String[n];

            for (int i = 0; i < n; i++) {

                StringBuilder row = new StringBuilder();

                for (int j = 0; j < n; j++) {

                    if (queenInColumn[i] == j)  // There is a queen at Row i and Column j

                        row.append('Q');

                    else

                        row.append('.');

}

                solution[i] = row.toString();

}

            // Add the solution to "result"

            result.add(solution);

        } else {

            // Put a queen at each valid column in the current row, and recursively

            // work on the next row

            for (int j = 0; j < n; j++) {

                if (isValid(j, currentRow, queenInColumn)) {

                    // A queen at Column j in the currentRow is valid

                    queenInColumn[currentRow] = j;

                    recursiveNQueens(n, currentRow+1, queenInColumn, result);

}

}

}

}

    // Indicate whether a queen can be put at (workingRow, attemptedColumn)

    // without violating the rules

    private boolean isValid(int attemptedColumn, int workingRow, int[] queenInColumn) {

        // Verify all the rules

        // No row conflict automatically since we put only one queen in each row

        for (int i = 0; i < workingRow; i++) {

            if (attemptedColumn == queenInColumn[i] ||      // No column conflict

                    (workingRow-i == Math.abs(attemptedColumn-queenInColumn[i])))   // No diagnal conflict

                return false;

}

        return true;

}

1. 逐行放置皇后：排除在同一行的可能。

2. 记录之前所放皇后的列坐标：col[i]=j表示第i行的皇后在第j列。这样在放置第i+1行时，只要保证col[i+1] != col[k], k=0...i 即可。

3. 对角线判断：对于任意(i1, col[i1])和(i2, col[i2])，只有当abs(i1-i2) = abs(col[i1]-col[i2])时，两皇后才在同一对角线

在放置的时候，要保持当前的状态为合法，即当前放置位置的同一行、同一列、两条对角线上都不存在皇后。
http://www.cnblogs.com/springfor/p/3870944.html

难点大概就是用1个一维数组存皇后所在的坐标值。对于一个棋盘来说，每个点都有横纵坐标，用横纵坐标可以表示一个点。
而这道题巧就巧在，每一行只能有一个皇后，也就是说，对于一行只能有一个纵坐标值，所以用1维数组能提前帮助解决皇后不能在同一行的问题。
那么用一维数组表示的话，方法是：一维数组的下标表示横坐标（哪一行），而数组的值表示纵坐标（哪一列）。

例如：对于一个4皇后问题，声明一个长度为4的数组（因为行数为4）。
     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 

这样以来，皇后所在的坐标值就能用一维数组表示了。
而正是这个一维数组，在回溯找结果的时候不需要进行remove重置操作了，因为回溯的话正好就回到上一行了，就可以再重新找下一个合法列坐标了。

http://rleetcode.blogspot.com/2014/02/leetcode-n-queens-puzzle-is-problem-of.html
Eight queens problem

public void solve(int size) {

012.boolean[][] array = new boolean[size][size];

013.solveQueensProblem(array, 0, 0, true, 0);

014.solveQueensProblem(array, 0, 0, false, 0);

015.}

021.* @param set true if the queen should be placed, false otherwise

022.

024.private void solveQueensProblem(boolean[][] array, int x, int y, boolean set, int queensCount) {

025.array[y][x] = set;

026.if (set && !checkConsistency(array, x, y)) {

027.return;

028.}

029.if (set) {

030.queensCount++;

031.}

032. 

033.if (queensCount == array.length) {

034.solutionsCount++;

035.printArray(array);

036.return; //solution found

037.}

038.x = x + 1; //increment x

039.int overflow = x == array[y].length ? 1 : 0;

040.if (overflow == 1) {//if x overflowed

041.x = 0; //set to 0

042.y += 1; //increment y

043.}

044. 

045.if (y >= array.length) {

046.return; //end of the problem, all decisions have been made

047.}

048.//lets make both decisions

049.solveQueensProblem(array, x, y, true, queensCount);

050.solveQueensProblem(array, x, y, false, queensCount);

051. 

052.}

vector<vector<string> > solveNQueens(int n)
{
vector<string> board(n,string(n, '.'));
vector<vector<string> > rs;
solNQueens(rs, board);
return rs;
}
void solNQueens(vector<vector<string> > &rs, vector<string> &board, int row=0)
{
if (row == board.size()) rs.push_back(board);
for (int col = 0; col < board.size(); col++)
{
if (isLegal(board, row, col))
{
board[row][col] = 'Q';
solNQueens(rs, board, row+1);
board[row][col] = '.';
}
}
}

X. BitMap
https://leetcode.com/discuss/75588/a-concise-java-solution-using-bitmap-0-ms

For example, in 4 queens problem, row = "0110" means column 1 and 2 in this row is occupied by queens in above rows. ld means columns occupied by the left diagonal, and rd means columns occupied by the right diagonal.

int sum = 0, upperlimit = 1;

public int totalNQueens(int n) {
    upperlimit = (1 << n) - 1;//"11...11"
    totalNQueens(0, 0, 0);
    return sum;
}

void totalNQueens(int row, int ld, int rd) {
    int placeable = upperlimit & ~(row | ld | rd);//Get all placeable positions in this row

    if (row != upperlimit) {
        while (placeable != 0) {
            int pos = placeable & (~placeable + 1);//Get the right most placeable position
            placeable -= pos;//Remove position from placeable
            totalNQueens(row | pos, (ld | pos) << 1, (rd | pos) >> 1); //Get occupied columns of the next row and go to next
        }
    } else {
        sum++;
    }
}

https://github.com/iamzhaozheng/leetcode/blob/master/src/com/hisrv/leetcode/NQueens.java
private ArrayList<String[]> mRet;
private int mSize;
private int mMask;

public ArrayList<String[]> solveNQueens(int n) {
// Start typing your Java solution below
// DO NOT write main() function
mRet = new ArrayList<String[]>();
mSize = n;
mMask = (1 << mSize) - 1;
queen(0, 0, 0, 0, new int[n]);
return mRet;
}

private void queen(int y, int left, int down, int right, int[] status) {
if (y == mSize) {
out(status);
} else {
int bitmap = mMask & ~(left | down | right);
while (bitmap != 0) {
int bit = -bitmap & bitmap;
status[y] = bit;
bitmap ^= bit;
queen(y + 1, (left | bit) << 1, down | bit, (right | bit) >> 1, status);
}
}
}

private void out(int[] status) {
int n = status.length;
String[] strs = new String[n];
for (int i = 0; i < n; i ++) {
char[] s = new char[n];
for (int j = 0; j < n; j ++) {
s[j] = '.';
}
int p = log2(status[i]);
s[p] = 'Q';
strs[i] = new String(s);
}
mRet.add(strs);
}

private int log2(int a) {
int r = 0;
while (a > 1) {
a = a / 2;
r ++;
}
return r;
}
http://www.cnblogs.com/TenosDoIt/p/3801621.html

算法4（解释在后面）这应该是最高效的算法了

class Solution {

private:

    vector<vector<string> > res;

    int upperlim;

public:

    vector<vector<string> > solveNQueens(int n) {

        upperlim = (1 << n) - 1;//低n位全部置1

        vector<string> cur(n, string(n, '.'));

        helper(0,0,0,cur,0);

        return res;

    }

    void helper(const int row, const int ld, const int rd, vector<string>&cur, const int index)

    {

        int pos, p;

        if ( row != upperlim )

        {

            pos = upperlim & (~(row | ld | rd ));//pos中二进制为1的位，表示可以在当前行的对应列放皇后

            //和upperlim与运算，主要是ld在上一层是通过左移位得到的，它的高位可能有无效的1存在，这样会清除ld高位无效的1

            while ( pos )

            {

                p = pos & (~pos + 1);//获取pos最右边的1,例如pos = 010110，则p = 000010

                pos = pos - p;//pos最右边的1清0

                setQueen(cur, index, p, 'Q');//在当前行，p中1对应的列放置皇后

                helper(row | p, (ld | p) << 1, (rd | p) >> 1, cur, index+1);//设置下一行

                setQueen(cur, index, p, '.');

            }

        }

        else//找到一个解

            res.push_back(cur);

    }

    //第row行，第loc1(p)列的位置放置一个queen或者清空queen，loc1(p)表示p中二进制1的位置

    void setQueen(vector<string>&cur, const int row, int p, char val)

    {

        int col = 0;

        while(!(p & 1))

        {

            p >>= 1;

            col++;

        }

        cur[row][col] = val;

    }

};

这个算法主要参考博客N皇后问题的两个最高效的算法，主要看helper函数，参数row、ld、rd分别表示在列和两个对角线方向的限制条件下，当前行的哪些地方不能放置皇后。如下图

前三行放置了皇后，他们对第3行（行从0开始）的影响如下：本文地址

（1）列限制条件下，第3行的0、2、4列（紫色线和第3行的交点）不能放皇后，因此row = 101010

（2）左对角线限制条件下，第3行的0、3列（蓝色线和第3行的交点）不能放皇后，因此ld = 100100

（3）右对角线限制条件下，第3行的3、4、5列（绿色线和第3行的交点）不能放皇后，因此rd = 000111

~(row | ld | rd) = 010000，即第三行只有第1列能放置皇后。

在3行1列这个位置放上皇后，row，ld，rd对下一行的影响为：

row的第一位置1，变为111010

ld的第一位置1，并且向左移1位（因为左对角线对行的影响是依次向左倾斜的），变为101000

rd的第一位置1，并且向右移1位（因为右对角线对行的影响是依次向右倾斜的），变为001011

第4行状态如下图

Iterative Version from http://blog.csdn.net/kenden23/article/details/18136889
vector<vector<string> > solveNQueens(int n)
{
vector<string> board(n,string(n, '.'));
vector<vector<string> > rs;
int row = 0;
vector<int> backtrackCol(n, -1);
while (row >= 0)
{
int col = 0;
if (backtrackCol[row] != -1)
{
col = backtrackCol[row]+1;
board[row][col-1] = '.';
}
for (; col < n; col++)
{
if (isLegal(board, row, col))
{
board[row][col] = 'Q';
backtrackCol[row] = col;
if (row == n-1)
{
rs.push_back(board);
backtrackCol[row] = -1;
board[row][col] = '.';
row--;
break;
}
row++;
break;
}
}
if (col == n)
{
backtrackCol[row] = -1;
row--;
}
}
return rs;
}
bool isLegal(const vector<string> &board, int row, int col)
{
for (int i = 0; i < row; i++)
{
if (board[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i>=0 && j>=0; i--, j--)
{
if (board[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i>=0 && j<board.size(); i--, j++)
{
if (board[i][j] == 'Q') return false;
}
return true;
}
http://www.cnblogs.com/TenosDoIt/p/3801621.html

http://www.cnblogs.com/TenosDoIt/p/3801621.html

X. Inefficent
https://leetcode.com/discuss/47517/my-easy-understanding-java-solution
public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) board[i][j] = '.'; List<List<String>> res = new ArrayList<List<String>>(); dfs(board, 0, res); return res; } private void dfs(char[][] board, int colIndex, List<List<String>> res) { if(colIndex == board.length) { res.add(construct(board)); return; } for(int i = 0; i < board.length; i++) { if(validate(board, i, colIndex)) { board[i][colIndex] = 'Q'; dfs(board, colIndex + 1, res); board[i][colIndex] = '.'; } } } private boolean validate(char[][] board, int x, int y) { for(int i = 0; i < board.length; i++) { for(int j = 0; j < y; j++) { if(board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i)) return false; } } return true; } private List<String> construct(char[][] board) { List<String> res = new LinkedList<String>(); for(int i = 0; i < board.length; i++) { String s = new String(board[i]); res.add(s); } return res; }

https://leetcode.com/discuss/9977/simple-java-solution

List<String[]> list = new ArrayList<String[]>(); public List<String[]> solveNQueens(int n) { int[][] b = new int[n][n]; dfs(b, 0, n); return list; } public void dfs(int[][] b, int col, int n) { if (col == n) { list.add(printS(b, n)); return; } for (int row = 0; row < n; row ++) { if (isSafe(b, row, col, n)) { b[row][col] = 1; dfs(b, col + 1, n); b[row][col] = 0; } } }

ublic boolean isSafe (int[][]matrix, column, int row, int n){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i==row && matrix[i][j]==1) return false; if(j==column&& matrix[i][j]==1) return false; if((Math.abs(row-i)==Math.abs(column-j))&&(matrix[i][j]==1)) return false; } } return true; }

Read full article from LeetCode - N-Queens | Darren's Blog

LeetCode 51 - N-Queens

Labels

Popular Posts