Straight forward Ans, DFS, Java


  • 0
    A

    Place queen row by row, mark vertical and diagonal lines that can not be used for next row.

    public class Solution {
        public List<String[]> solveNQueens(int n) {
            char[][] board=new char[n][n];
            for(int i=0; i<n; i++)
             Arrays.fill(board[i],'.');
            boolean[] lineUsed=new boolean[5*n];
            List<String[]> rst=new LinkedList<>();
            placeQueen(0,board, lineUsed, rst);
            return rst;
            
        }
        
        public void placeQueen(int row, char[][] board, boolean[] lineUsed,List<String[]> rst){
            int n=board.length;
            if(row==n){
                String[] sol=new String[board.length];
                for(int i=0; i<n; i++)
                    sol[i]=new String(board[i]);
                rst.add(sol);
                return;
            }
            for(int i=0; i<n; i++){
                //i:0~n-1 marks vertical lines that has been used,
                //row-i+2*n: -(n-1)+2n~(n-1)+2n -> n+1~3n-1 marks diagonals leftUp to rightDown
                //row+i+3*n : 3n~5n-2 marks diagonals rightUp to leftDown
                if(lineUsed[i] || lineUsed[row-i+2*n] || lineUsed[row+i+3*n]) continue;
                board[row][i]='Q';
                lineUsed[i]=true;
                lineUsed[row-i+2*n]=true;
                lineUsed[row+i+3*n]=true;
                placeQueen(row+1,board,lineUsed,rst);
                board[row][i]='.';
                lineUsed[i]=false;
                lineUsed[row-i+2*n]=false;
                lineUsed[row+i+3*n]=false;
            }
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.