Comparably concise Java code


  • 34
    S

    Hi guys!

    I didn't invent a wheel here. We just remember the busy columns and diagonals and recursively try to put the queen into the next row. But I think the code below is short enough to be reproduced in the interview.

    Hope it helps!


    public class Solution {
        
        private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, 
                            String[] board, List<String[]> res) {
            if (r == board.length) res.add(board.clone());
            else {
                for (int c = 0; c < board.length; c++) {
                    int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1;
                    if (!cols[c] && !d1[id1] && !d2[id2]) {
                        char[] row = new char[board.length];
                        Arrays.fill(row, '.'); row[c] = 'Q';
                        board[r] = new String(row);
                        cols[c] = true; d1[id1] = true; d2[id2] = true;
                        helper(r+1, cols, d1, d2, board, res);
                        cols[c] = false; d1[id1] = false; d2[id2] = false;
                    }
                }
            }
        }
        
        public List<String[]> solveNQueens(int n) {
            List<String[]> res = new ArrayList<>();
            helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], 
                new String[n], res);
            return res;
        }
    }

  • 1
    K

    Im confused as to how you were able to represent diagonals using 2 size 2n arrays. could you explain? thanks


  • 4

    Nice and clean! We can simplify id2 = r + c


  • 0
    M

    Second above - could you explain how 2n arrays work?


  • 1
    T

    Thanks for the solution :)

    What does id1 and id2 stand for?
    Does r stand for the row number and c for column number?


  • 0
    P

    intersection for x axis and y axis


  • 0
    H

    The use of 2n boolean array is that there are 2n diagonals for a n*n matrix.


  • 5
    F

    Using three boolean[] to replace three hashSet is a great idea.
    And we can use d1=rowCur+j d2=j-rowCur+n-1, it's more easy to understand.

    For every element arr[i][j] in diag line with positive slope,
    i+j is the same,it range from 0 to 2*(n-1).
    And for every element arr[i][j] in diag line with negative slope,
    j-i is the same,
    it range from -(n-1) to n-1,
    we add n-1 to make the range from 0 to 2*(n-1).

    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<List<String>>();
            if(n<1)
                return result;
            solve(result, new ArrayList<String>(), n, 0,new boolean[n], new boolean[2*n], new boolean[2*n]);
            return result;
        }
        public void solve(List<List<String>> result, List<String> cur,
                          int n, int rowCur, boolean[] col, boolean[] diag1, 
                          boolean[] diag2){
            if(rowCur==n){
                result.add(new ArrayList<String>(cur));
                return;
            }
            for(int j = 0; j<n; j++){
                int d1=rowCur+j;
                int d2=j-rowCur+n-1;
                 if(!col[j] && !diag1[d1] && !diag2[d2]){
                        col[j]=true;
                        diag1[d1]=true;
                        diag2[d2]=true;
                        char[] helpChars=new char[n];
                        Arrays.fill(helpChars,'.');
                        helpChars[j]='Q';
                        cur.add(new String(helpChars));
                        
                        solve(result, cur, n, rowCur+1, col, diag1, diag2);
                        
                        col[j]=false;
                        diag1[d1]=false;
                        diag2[d2]=false;
                        cur.remove(cur.size()-1);
                    }
            }
        }
    }
    

  • 0
    F
    This post is deleted!

  • 0
    F
    This post is deleted!

  • 3
        public List<List<String>> solveNQueens(int n) {
               List<List<String>> res = new ArrayList();
               helper(n, res, new ArrayList(), 0);
               return res;
        }
        
        // rowQpos records for each row, which col to put the Queen
        private void helper(int n, List<List<String>> res, List<Integer> rowQpos, int row){
            if(rowQpos.size() == n){
                    List<String> board = new ArrayList();
                    for(Integer rq:rowQpos){
                        char[] bc = new char[n];
                        Arrays.fill(bc,'.');
                        bc[rq] = 'Q';
                        board.add(String.valueOf(bc));
                    }
                    res.add(board);
                    return;
            }
            
            for(int i=0;i<n;i++){
                if(!isValid(rowQpos, row, i)) continue;
                rowQpos.add(i);
                helper(n, res, rowQpos, row + 1);
                rowQpos.remove(rowQpos.size()-1);
            }            
        }
        
        private boolean isValid(List<Integer> rowQpos, int row, int col){
            for(int i=0;i<rowQpos.size();i++){
                if(col == rowQpos.get(i)) return false;
                if(row - col == i - rowQpos.get(i)) return false;
                if(row + col == i + rowQpos.get(i)) return false;
            }
            return true;
        }

  • 0
    Y

    Great solution!

    Improve a little by (1) creating one char array per row: taking the char[] creation and array fill out of the loop. (2) using 2n-1 elements per diagonal.

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        if(n <= 0) return solutions;
        
        boolean[] cols = new boolean[n];
        boolean[] d1   = new boolean[2*n-1]; // diagonal 1, from upper left to lower right. d1idx = cidx - ridx + n - 1
        boolean[] d2   = new boolean[2*n-1]; // diagonal 2, from upper right to lower left  d2idx = (n-cidx) - ridx + n - 2
        solveNQueens(n, 0, cols, d1, d2, new ArrayList<String>(), solutions);
        return solutions;
    }
    
    private void solveNQueens(int n, int rowidx, boolean[] cols, boolean[] d1, boolean[] d2, 
                                        List<String> oneSolution, List<List<String>> solutions){
        if(rowidx == n){
            solutions.add(new ArrayList<String>(oneSolution));
            return;
        }
        
        // in each recursive level, place one Quene in one row.
        char[] row = new char[n];
        Arrays.fill(row, '.');
        for(int colidx = 0; colidx < n; colidx++){
            
            int d1idx = colidx - rowidx + n - 1;
            int d2idx = (n-colidx) - rowidx + n - 2;
            
            if(!cols[colidx] && !d1[d1idx] && !d2[d2idx]){
                row[colidx] = 'Q';
                oneSolution.add(new String(row));
                cols[colidx] = d1[d1idx] = d2[d2idx] = true;
                
                solveNQueens(n, rowidx+1, cols, d1, d2, oneSolution, solutions);
              
                row[colidx] = '.';
                oneSolution.remove(oneSolution.size()-1);
                cols[colidx] = d1[d1idx] = d2[d2idx] = false;
            }
        }
    }

  • 0
    G

    You can skip almost half of the searching on symmetry grounds by evaluating only half of the first row. In the end you should mirror all solutions except those where the first queen is set in the centre.


  • 0
    H

    can anyone tell me what time time complexity is?


  • 1
    G

    The logic behind using a 1D boolean array to represent a diagonal is this:
    Any point in the matrix is part of two diagonals that cut through it. One from its top-left-ish to its bottom-right-ish and another from top-right-ish to its bottom-left-ish.
    For Example , we have the given 2D board:
    (0,0) (0,1) (0,2) (0,3)
    (1,0) (1,1) (1,2) (1,3)
    (2,0) (2,1) (2,2) (2,3)
    (3,0) (3,1) (3,2) (3,3)

    where the (x,y) represents the position in the board.
    Now lets just take a point (1,2). Now the two diagonals that pass through it are :

    1. Through the points (0,1) (1,2) (2,3). These points are considered for d1 boolean array. If we look at any point in this set, x-y is the same. 0-1 == 1-2 == 2-3. Hence i-j + board.length will give the same index in d1 for all its diagonal elements,since i-j will be the same.
    2. Through the points (0,3) (1,2) (2,1) (3,0) . These points are considered for the d2 boolean array. Now if you look at the points , the sum of x and y coordinates is the same for all points. Hence 2board.length -i-j-1 == 2board.length -(i+j) -1 which will be the same for all the points in the diagonal. Hence if the idx in d2 is true already , that would mean some point in the diagonal already had a queen.

    Hope this helps.


Log in to reply
 

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