Easiest Java Solution (1ms, 98.22%)


  • 31

    This is a classic backtracking problem.

    Start row by row, and loop through columns. At each decision point, skip unsafe positions by using three boolean arrays.

    Start going back when we reach row n.

    Just FYI, if using HashSet, running time will be at least 3 times slower!

    public class Solution {
        int count = 0;
        public int totalNQueens(int n) {
            boolean[] cols = new boolean[n];     // columns   |
            boolean[] d1 = new boolean[2 * n];   // diagonals \
            boolean[] d2 = new boolean[2 * n];   // diagonals /
            backtracking(0, cols, d1, d2, n);
            return count;
        }
        
        public void backtracking(int row, boolean[] cols, boolean[] d1, boolean []d2, int n) {
            if(row == n) count++;
    
            for(int col = 0; col < n; col++) {
                int id1 = col - row + n;
                int id2 = col + row;
                if(cols[col] || d1[id1] || d2[id2]) continue;
                
                cols[col] = true; d1[id1] = true; d2[id2] = true;
                backtracking(row + 1, cols, d1, d2, n);
                cols[col] = false; d1[id1] = false; d2[id2] = false;
            }
        }
    }

  • 0
    H

    Is this faster by using boolean[][] instead of int[][] ?

    My int[][] is way slower..16%. if it's the reason?


  • 0

    Yeah, boolean is generally faster.


  • 0
    E

    very neat code!


  • 0
    A

    Similar idea

    public class Solution {
    	public int totalNQueens(int n) {
    		NQueens q = new NQueens(n);
    		q.findAllSafeColumns(0);
    		return q.numberOfSolutions;
    	}
    
    	public class NQueens {
    		private int size;
    		private boolean[][] board;
    		private boolean[] colEmpty;
    		private boolean[] upDiagEmpty;
    		private boolean[] downDiagEmpty;
    		private int numberOfSolutions;
    
    		public NQueens(int size) {
    			this.numberOfSolutions = 0;
    			this.size = size;
    			this.board = new boolean[size][size];
    			this.colEmpty = new boolean[size];
    			this.upDiagEmpty = new boolean[2 * size];
    			this.downDiagEmpty = new boolean[2 * size];
    			Arrays.fill(colEmpty, true);
    			Arrays.fill(upDiagEmpty, true);
    			Arrays.fill(downDiagEmpty, true);
    		}
    
    		public void findAllSafeColumns(int row) {
    			if (row == size) {
    				numberOfSolutions++;
    				return;
    			}
    			for (int i = 0; i < size; i++) {
    				if (isSafe(row, i)) {
    					placeQueen(row, i);
    					findAllSafeColumns(row + 1); // row++ or ++row won't work
    					removeQueen(row, i);
    				}
    			}
    		}
    
    		public void placeQueen(int row, int column) {
    			board[row][column] = true;
    			this.colEmpty[column] = false;
    			this.upDiagEmpty[row + column] = false;
    			this.downDiagEmpty[size - 1 + row - column] = false;
    		}
    
    		public void removeQueen(int row, int column) {
    			board[row][column] = false;
    			this.colEmpty[column] = true;
    			this.upDiagEmpty[row + column] = true;
    			this.downDiagEmpty[size - 1 + row - column] = true;
    		}
    
    		public boolean isSafe(int row, int column) {
    			return colEmpty[column] && upDiagEmpty[row + column] && downDiagEmpty[size - 1 + row - column];
    		}
    
    	}
    }
    

  • 1
    S

    Can you please tell what is id1 and id2?


  • 0
    H

    @yavinci I am finding it hard to understand the mapping logic for arrays of 2 diagonals and the formula to find their indices (col - row + n) and (col + row). Can you please explain that?


  • 7
    A

    @hopper19
    45 degree line is y = x + b
    135 degree line is y = -x + b
    in another word, 45 degree y - x is constant, and 135 degree y + x is constant.
    Here b is shifted to [0~2n), so y-x and y+x can be trackable.


  • 0
    H

    @adammama Thanks a lot!


  • 0

    I prefer use bit array instead of boolean array.

    Here is an article, showing how to solve N queens in 5 ways, from slow to fastest.

    public class Solution {
        int count = 0;
        public int totalNQueens(int n) {
            DFS(n, 0, 0, 0, 0);
            return count;
        }
        
        private void DFS(int N, int row, int shu, int pie, int na) {
            int ok = ((1 << N) - 1) & ~(shu | pie | na);
            while (ok != 0) {
                int p = ok & -ok;
                ok ^= p;
                if (row == N - 1) {
                    count++;
                } else {
                    DFS(N, row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
                }
            }
        }
    }
    

  • 0
    Y

    Hi @yavinci I have similar idea as yours. And I think we can avoid using the global variable

    public class Solution {
        public int totalNQueens(int n) {
            boolean[] col = new boolean[n];
            boolean[] tlbr = new boolean[2 * n + 1]; // top left -> bottom right
            boolean[] trbl = new boolean[2 * n + 1]; // top right -> bottom left
            return tryPut(0, n, col, tlbr, trbl);
        }
        private int tryPut(int row, int size, boolean[] col, boolean[] tlbr, boolean[] trbl) {
            int result = 0;
            for (int i = 0; i < size; i++)
                if (!col[i] && !tlbr[size - 1 - row + i] && !trbl[row + i]) {
                    // System.out.println("when row = " + row + ", try col = " + i);
                    if (row == size - 1) {
                        result++;
                    } else {
                        col[i] = true;
                        tlbr[size - 1 - row + i] = true;
                        trbl[row + i] = true;
                        result += tryPut(row + 1, size, col, tlbr, trbl);
                        col[i] = false;
                        tlbr[size - 1 - row + i] = false;
                        trbl[row + i] = false;
                    }
                }
            return result;
        }
    }
    

  • 0
    M

    I wonder if global variables are allowed in real interview. In some cases, like this one, a global variable is very useful.


  • 0
    F

    @MitchellHe I don't think it will be forbidon to use global variables, but it might cause some "point deduction" for your scores by some of the interviewers.


  • 0
    T

    whats the complexity of this one ?, seems like O(n)


Log in to reply
 

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