My easy understanding Java Solution


  • 42
    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;
        }
    }
    

  • 10
    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!


  • 0
    C

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


Log in to reply
 

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