My Java DFS solution


  • 0
    H
    public class Solution {
        public class Board {
            private boolean[] cols;
            private boolean[] diag1;
            private boolean[] diag2;
            private Deque<Integer[]> queens;
            
            public Board(int n) {
                cols = new boolean[n];
                diag1 = new boolean[2*n - 1];
                diag2 = new boolean[2*n - 1];
                queens = new LinkedList<Integer[]>();
            }
        }    
        
        public int totalNQueens(int n) {
            result = 0;
            Board board = new Board(n);
            inner(board, n);
            return result;
        }
        
        private int result;
        
        private void inner(Board board, int n) {
            if(board.queens.size() < n) {
                int row = board.queens.size();
                for(int i = 0; i < n; i++) {
                    if(!board.cols[i] && !board.diag1[i + row] && !board.diag2[i - row + n - 1]) {
                        Integer[] queen = new Integer[2];
                        queen[0] = row;
                        queen[1] = i;
                        board.queens.addLast(queen);
                        
                        board.diag1[i + row] = true;
                        board.diag2[i - row + n - 1] = true;
                        board.cols[i] = true;
                        
                        inner(board, n);
                        
                        board.queens.pollLast();
                        
                        board.diag1[i + row] = false;
                        board.diag2[i - row + n - 1] = false;
                        board.cols[i] = false;
                    }
                }
            } else {
                result++;
            }
        }
    }

Log in to reply
 

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