N-Queens & N-Queens II

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..”]
]

两道题的做法是一样的,都是用recursion和回溯算法,差别在于怎样快速的求isValid和计算board, 最简单的办法是用一个nxn的board,但是那样太慢了。
第一种方法我们用一个数组,因为每一行只能存一个Q, 所以每一个index存的数就是那一行的Q所在的位置,然后用来求isValid就是扫描之前的所有行,如果发现有一样的数(同一列),或者board[i] – i = c – r(左对角线)或者board[i]+i = r+c(右对角线)

public class Solution {
    int [] board;
    ArrayList<String[]> res = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        board = new int[n];
        tryRow(0, n);
        return res;
    }
    
    public void tryRow(int r, int n) {
        if (r == n-1) {// last row
            for(int i = 0; i < n; i++) {
                if (isValid(r, i)) {
                    board[r] = i;
                    res.add(convertToBoard(n));
                }
            }
        }
        else {
            for (int i = 0; i < n; i++) {
                if (isValid(r, i)) {
                    board[r] = i;
                    tryRow(r+1, n);
                }
            }
        }
    }
    
    public boolean isValid(int r, int c) {
        for (int i = 0; i < r; i++) {
            if((board[i] - i == c - r) || (board[i] + i == c + r) || board[i] == c)
                return false;
        }
        return true;
    }
    
    public String[] convertToBoard(int size) {
        String [] res = new String [size];
        char [] init = new char[size];
        Arrays.fill(init, '.');
        for (int i = 0; i < size; i++) {
            StringBuilder s = new StringBuilder();
            s.append(init);
            s.setCharAt(board[i], 'Q');
            res[i] = (new String(s));
        }
        return res;
    }
}

然后是第二个问题,这次不需要所有的solution,只要totalnumber,当然用上一种方法也可以做,但是在网上看到一个更吊的方法。具体办法在这里 http://www.matrix67.com/blog/archives/266
用三个数分别用二进制来表示下一行被占的行和两个对角线,其中取最右边的一个1的办法很巧妙,直接用p = pos & (~pos + 1)就可以得到右边第一个1的位置,然后将pos – p以后继续求,直到pos为0时所有的可能position都试过了。

public class Solution {
    int total;
    public int totalNQueens(int n) {
        int max = 1;
        int row = 0, ld = 0, rd = 0;
        for (int i = 1; i < n; i++) {
            max = (max << 1) + 1;
        }
        tryRow(max, row, ld, rd);
        return total;
    }
    
    public void tryRow(int max, int row, int ld, int rd) {
        if (row == max ) {
            total++;
            return; // no need to continue
        }
        int pos = (~(row | ld | rd)) & max; // find all possible positions, indicated by 1
        while(pos > 0) {
            int p = pos & (~pos + 1); //get the first one form right : pos -> ~pos, all 0s becomes 1, 1 becomes 0, ~pos + 1 -> first 0 from right becomes 1.
            tryRow(max, row | p, (ld << 1 | p << 1) & max, (rd >> 1 | p >> 1) & max);
            pos -= p; // proceed to next 1 in pos
        }
    }
}

Second Submission, N-Queens (Separate each function)

public class Solution {
    ArrayList<String[]> res = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        int [] board = new int [n]; 
        tryLevel(board, 0, n);
        return res;
    }
    
    public void tryLevel(int [] board, int level, int n) {
        for (int i = 0; i < n ; i++) {
            if (isValid(board, level, i)) {
                board[level] = i;
                if (level == n-1) // If it is the last line
                    res.add(generateBoard(board));
                else
                    tryLevel(board, level + 1, n);
            }
        }
    }
    
    public boolean isValid(int [] board, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i] == col || board[i] - i == col - row || board[i] + i == col + row)
                return false;
        }
        return true;
    }
    
    public String [] generateBoard (int [] board) {
        String [] res = new String [board.length];
        for (int i = 0; i < board.length; i++) {
            StringBuilder line = new StringBuilder();
            for (int j = 0; j < board.length; j++) {
                if (j == board[i])
                    line.append('Q');
                else
                    line.append('.');
            }
            res[i] = new String(line);
        }
        return res;
    }
}

N-Queens II, notice the ending condition row == max, no need to pass any other parameter for ending condition.

public class Solution {
    int result = 0;
    public int totalNQueens(int n) {
        int limit =(int) (Math.pow(2, n) - 1);
        tryLevel(limit, 0, 0, 0);
        return result;
    }
    //use row, ld, rd to record the occupied positions in previous lines
    public void tryLevel(int max, int row, int ld, int rd) {
        // find available positions using row, ld and rd binary, occupied bit recorded as 1
        if (row == max)  {//all rows has been filled.
            result++;
            return;
        }
        int occupied = (~(row | ld | rd) & max);
        while(occupied != 0) {
            int available = occupied & (~occupied + 1); //get first 1 from the right
            occupied &= (~available);
            tryLevel(max, row | available, (ld | available) << 1, (rd | available) >> 1);
        }
        return;
    }
}

NQueens, Simple solution, same idea as previous, but pass on the result of previous result as String array. Need to copy a new array when pass to next level.

public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        int [] board = new int [n]; 
        ArrayList<String[]> res = new ArrayList<String[]>();
        String [] tmp = new String[n];
        tryRow(0, board, n, res, tmp);
        return res;
    }
    
    public void tryRow(int row, int[] board, int n, ArrayList<String[]> res, String[] pre) {
        if (row == n-1) {//last line
            for (int c = 0; c < n; c++) {
                if (isValid(board, row, c)) {
                    pre[row] = (getString(n, c));
                    res.add(pre);
                }
            }
            return;
        }
        for (int c = 0; c < n; c++) {
            if (isValid(board, row, c)) {
                board[row] = c;
                //make a copy of previous result
                String [] next = new String [n];
                for (int i = 0; i < row; i++) {
                    next[i] = pre[i];
                }
                next[row] = getString(n, c);
                tryRow(row+1, board, n, res, next);
            }
        }
    }
    
    private boolean isValid(int [] board, int row, int col) {
        int count = 1;
        for (int r = row-1; r >= 0; r--) {
            if (board[r] == col || board[r] == col - count || board[r] == col + count)
                return false;
            count++;
        }
        return true;
    }
    
    private String getString(int n, int col) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < n; i++) {
            res.append((i == col)?'Q' : '.');
        }
        return new String(res);
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s