My easy understanding Java Solution


  • 46
    P
    public class 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;
        }
    }

  • 1

    Can you explain a little bit more about this line?

    if(board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i))
    

  • 3
    V

    @Augustdoker
    I think it means "there is a queen meanwhile this queen is against with the one you want to put".
    In another word,you can not put a queen here because there is another queen which is in different column but in the same row or in the same diagonal line with it.
    May this will help you.


  • 1
    Y

    I like the way you validate. the board can be replaced by an inter array.

    public class Solution {
        public List<List<String>> solveNQueens(int n) {//the rule is no same column, no same row, no same on diagonal. i+j!=level+index
            List<List<String>> result=new ArrayList<List<String>>();
            List<Integer> taken=new ArrayList<Integer>();
            for(int i=0;i<n;i++){
                taken.add(i,-1);
            }
            getNQueens(result,0,n,taken);
            return result;
        }
        public void getNQueens(List<List<String>> result, int level, int n, List<Integer> taken){
            if(level==n){
                List<String> board=new ArrayList<String>();
                for(int i=0;i<n;i++){
                    StringBuilder s=new StringBuilder();
                    for(int j=0;j<n;j++){
                        s.append(".");
                    }
                    s.setCharAt(taken.get(i),'Q');
                    board.add(s.toString());
                }
                result.add(board);
                return;
            }
            for(int i=0;i<n;i++){
                if(isValid(taken,level,n,i)){
                    taken.set(level,i);
                    getNQueens(result,level+1,n,taken);
                    taken.set(level, -1);
                }
            }
        }
        public boolean isValid(List<Integer> taken, int level, int n, int index){
        	for(int i=0;i<level;i++){
        		if(taken.contains(index)||(taken.get(i)+i==level+index)||(taken.get(i)+level==i+index)){
        			return false;
        		}
        	}
        	return true;
        }
    }
    

  • 13
    G

    @Augustdoker The main idea here is to put Q in each column from left to right, and when we put Q in each column we check the validity row by row. Since we are traversing from left to right column, we only need to check whether the current position is in conflict with its left column elements. There are only three possible positions in the left column that might be in conflict with the current Q. Respectively, they are the 135 degree, horizontally left and 45 degree ones. For 135 degree, they are in a line whose slope is -1. So (y-j)/(x-i) = -1 -> y + x = i + j. For the horizontally one, x = i. And for the 45 degree one, the line slope is 1, so (y-j)/(x-i) = 1 -> y + i = x + j. Hope my explanation could be clear to you.


  • 1
    Z

    @pirateutopia Thank you for your sharing! I find the 'validate' process can be adjusted to get higher performance.

    public boolean validate(char[][] board,int x,int y)
    {
    //the same line
    for(int j=0;j<y;j++)
    {
    if(board[x][j]=='Q')
    {
    return false;
    }
    }
    //45
    for(int j=0;j<y;j++)
    {
    if(x+y-j>=0&&x+y-j<board.length&&board[x+y-j][j]=='Q')
    {
    return false;
    }
    }
    //135
    for(int j=0;j<y;j++)
    {
    if(x-y+j>=0&&x-y+j<board.length&&board[x-y+j][j]=='Q')
    {
    return false;
    }
    }
    return true;
    }


  • 0
    S

    where can I find the main part of the program?


  • 0
    P

    @RoyalPen same as if (board[i][j] == 'Q' && (Math.abs(row - i) == Math.abs(col - j) || row == i))


  • 0
    T

    @pirateutopia I replace you's validate() to
    public boolean isValid(char[][]board,int row,int col){
    for(int i=0; i<row; i++)
    for(int j=0; j<board.length; j++){
    if(board[i][j]=='Q' &&(Math.abs(row-i) == Math.abs(col-j) || col == j))
    return false;
    }
    return true;
    }


  • 0
    E

    @pirateutopia Thanks for the nice solution!

    I have a question. In your method of "validate", the condition of if, why don't you have y==j?

    I tested the code with:

    if (board[i][j] == 'Q' && (x + j == y + i || x + y == i + j || x == i || y == j)) return false;
    

    It also got accepted. I think with y ==j, it is complete. Kindly correct me if I am wrong.

    Thank you!


  • 1
    C

    @Eason kindly remind you that in the second loop, j is always less than y.


  • 0
    H

    I know this is a dumb question, but how can I print the results from the LinkedList res?
    Even using an iterator, I'm still only getting Strings like "I@42a57993".


  • 0
    F

    @caolc_0208 why should j be always less than y?


  • 0
    Y

    @hammel I guess you used toString() for printing, which will get the Address of the char array, to print the value of the array, you need to use String.valueOf(char [])


  • 0

    Actually 52. N-Queens II is easier than this problem. Let first solve that one.

    The solution is we solve the puzzle row by row. For each row, we figure out the valid col to place Q. For checking it, we store the status of every column, obliquely up and obliquely down. Because each column or oblique column only can place one Q.

    class Solution {
        int res;
        public int totalNQueens(int n) {
          boolean[] vertical = new boolean[n];
          boolean[] tiltU = new boolean[2 * n - 1];
          boolean[] tiltD = new boolean[2 * n - 1];
          helper(vertical, tiltU, tiltD, n, 0);  
          return res;
        }
        
        void helper(boolean[] v, boolean[] u, boolean[] d,  int n, int row){
          if(row == n){
            res++;
            return;
          }
          
          for(int col = 0; col < n; col++){
            if(v[col] || u[col + row] || d[row - col + n - 1]){
              continue;
            }
            v[col] = true;
            u[col + row] = true;
            d[row - col + n - 1] = true;
            helper(v, u, d, n, row + 1);
            v[col] = false;
            u[col + row] = false;
            d[row - col + n - 1] = false;
          }
        }
    }
    

    After solved this problem it is easy to this problem. We just store the index of each row we placed the Q. Then we construct the String List answer.

    class Solution {
        public List<List<String>> solveNQueens(int n) {
          List<List<String>> res = new ArrayList();
          boolean[] vertical = new boolean[n];
          boolean[] tiltU = new boolean[2 * n - 1];
          boolean[] tiltD = new boolean[2 * n - 1];
          int[] h = new int[n];
          helper(res, h, vertical, tiltU, tiltD, n, 0);   
          return res;
        }
        
        void helper(List<List<String>> res, int[] h, boolean[] v, boolean[] u, boolean[] d,  int n, int row){
          if(row == n){
            List<String> list = new ArrayList();
            for(int i = 0; i < n; i++){
                char[] cs = new char[n];
                Arrays.fill(cs, '.');
                cs[h[i]] = 'Q';
                list.add(new String(cs));       
            }
            res.add(list);
            return;
          }
          
          for(int col = 0; col < n; col++){
            if(v[col] || u[col + row] || d[row - col + n - 1]){
              continue;
            }
            v[col] = true;
            u[col + row] = true;
            d[row - col + n - 1] = true;
            h[row] = col;
            helper(res, h, v, u, d, n, row + 1);
            v[col] = false;
            u[col + row] = false;
            d[row - col + n - 1] = false;
          }
        }
    }
    

Log in to reply
 

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