N-Queens

N-Queens

 

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

Naive Way: 这道题可以直观感受到并不是巧妙的算法的，应该是要brute force遍历所有情况。

对于这种题，类似的还有解数独那道题，我都是想到DFS来解的。

但同样是DFS，解法的复杂性，所用的空间大小，back trace的难度，都是很值得想的。

这是我的解法。使用了一个矩阵做容器，DFS遍历，带回溯，每次放置一个Q，对应覆盖位置+1，

回溯时每一个Q的对应覆盖位置-1。每次都检测是否填完，填完则记录进结果。运行时间在所有用Java

的人中排在后面。 

class Node{
        int x, y;
        Node(int a,int b){x = a;y = b;}
    }
    
    public List<String[]> solveNQueens(int n) {
        List<String[]> rlst = new ArrayList<String[]>();
        Stack<Node> stack = new Stack<Node>();
        char[][] board = new char[n][n];
        for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){board[i][j] = '0';}}
        
        // initialize stack
        for(int i = 0;i < n;i++){
            Node node = new Node(0,i);
            stack.push(node);
        }
        
        // DFS
        while(!stack.isEmpty()){
            Node node = stack.pop();
            board[node.x][node.y] = 'Q';
            boolean hasNext = false;
            
            // set new Q
            addBoard(board, node.x, node.y);
            if(isFinished(board) && node.x==n-1){
                String[] strs = new String[n];
                for(int i = 0;i < n;i++){
                    StringBuilder str = new StringBuilder();
                    for(int j = 0;j < n;j++)
                        str.append(board[i][j]=='Q'?'Q':'.');
                    strs[i] = str.toString();
                }
                rlst.add(strs);
            }
                
            // push next row
            if(node.x+1 < n){
                for(int j = 0;j < n;j++){
                    if(board[node.x+1][j]=='0'){
                        Node next = new Node(node.x+1,j);
                        stack.push(next);
                        hasNext = true;
                    }
                }
            }
                
            if(!hasNext || (isFinished(board) && node.x==n-1)){
                // back trace
                if(!stack.isEmpty()){
                    Node peek = stack.peek();
                    for(int i = node.y;i >= 0;i--)
                        if(board[node.x][i]=='Q')
                            minusBoard(board,node.x,i);
                            
                    for(int i = node.x-1;i >= peek.x;i--)
                        for(int j = n-1;j >= 0;j--)
                            if(board[i][j] =='Q')
                                minusBoard(board,i,j);
                }
            }
            
        }
        
        return rlst;
    }
    
    private boolean isFinished(char[][] b){
        for(int i = 0;i < b.length;i++)
            for(int j = 0;j < b[0].length;j++)
                if(b[i][j]== '0')
                    return false;
        return true;
    }
    
    private void addBoard(char[][] b, int x, int y){
        for(int i = 0;i < b.length;i++)
            b[i][y] = b[i][y]=='Q'?b[i][y]:(char)(b[i][y]+1);
        for(int j = 0;j < b[0].length;j++)
            b[x][j] = b[x][j]=='Q'?b[x][j]:(char)(b[x][j]+1);
        for(int i = 1;i < b.length;i++){
            if(x+i >= 0 && x+i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x+i][y+i] = b[x+i][y+i]=='Q'?b[x+i][y+i]:(char)(b[x+i][y+i]+1);
            if(x+i >= 0 && x+i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x+i][y-i] = b[x+i][y-i]=='Q'?b[x+i][y-i]:(char)(b[x+i][y-i]+1);
            if(x-i >= 0 && x-i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x-i][y+i] = b[x-i][y+i]=='Q'?b[x-i][y+i]:(char)(b[x-i][y+i]+1);
            if(x-i >= 0 && x-i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x-i][y-i] = b[x-i][y-i]=='Q'?b[x-i][y-i]:(char)(b[x-i][y-i]+1);
        }
        return;
    }
    
    private void minusBoard(char[][] b, int x, int y){
     for(int i = 0;i < b.length;i++)
            b[i][y] = b[i][y]=='Q'?b[i][y]:(char)(b[i][y]-1);
        for(int j = 0;j < b[0].length;j++)
            b[x][j] = b[x][j]=='Q'?b[x][j]:(char)(b[x][j]-1);
        for(int i = 1;i < b.length;i++){
            if(x+i >= 0 && x+i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x+i][y+i] = b[x+i][y+i]=='Q'?b[x+i][y+i]:(char)(b[x+i][y+i]-1);
            if(x+i >= 0 && x+i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x+i][y-i] = b[x+i][y-i]=='Q'?b[x+i][y-i]:(char)(b[x+i][y-i]-1);
            if(x-i >= 0 && x-i < b.length && y+i >= 0 && y+i < b[0].length)
             b[x-i][y+i] = b[x-i][y+i]=='Q'?b[x-i][y+i]:(char)(b[x-i][y+i]-1);
            if(x-i >= 0 && x-i < b.length && y-i >= 0 && y-i < b[0].length)
             b[x-i][y-i] = b[x-i][y-i]=='Q'?b[x-i][y-i]:(char)(b[x-i][y-i]-1);
        }
        b[x][y] = '0';
        return;
    }

Improved Way:N Queens II