5ms Java Solution, DFS + dynamic programming


  • 0
    L

    DFS with dynamic programming to keep track of taken columns/diagonals

    public class Solution {
        boolean[] colsTaken;
        boolean[] diag1Taken; // \ diagonals
        boolean[] diag2Taken; // / diagonals
        
        int[] colIdxPerRow;
        String[] rowStringForColIdx;
        int piecesPlaced = 0;
        List<List<String>> ans;
        
        public List<List<String>> solveNQueens(int n) {
            
            ans = new ArrayList();
            colIdxPerRow = new int[n];
            rowStringForColIdx = new String[n];
            StringBuilder sb = new StringBuilder(n);
            for (int i = 0; i < n; i++) {
                sb.append('.');
            }
            for (int i = 0; i < n; i++) {
                sb.setCharAt(i, 'Q');
                rowStringForColIdx[i] = sb.toString();
                sb.setCharAt(i, '.');
            }
            
            colsTaken = new boolean[n];
            diag1Taken = new boolean[2 * n - 1];
            diag2Taken = new boolean[2*n-1];
            
            
            recurse(0, n);
            return ans;
        }
        
        public void recurse(int row, int n) {
            for (int i = 0; i < n; i++) {
                if (colsTaken[i]) {
                    continue;
                } 
                int d1Idx = diag1Index(row, i, n);
                if (diag1Taken[d1Idx]) {
                    continue;
                }
                int d2Idx = diag2Index(row, i, n);
                if (diag2Taken[d2Idx]) {
                    continue;
                }
                
                colsTaken[i] = true;
                diag2Taken[d2Idx] = true;
                diag1Taken[d1Idx] = true;
                colIdxPerRow[row] = i;
                piecesPlaced++;
                
                if (piecesPlaced == n) {
                    ans.add(getBoard());
                } else if (row != n - 1) {
                    recurse(row + 1, n);
                }
                
                colsTaken[i] = false;
                diag2Taken[d2Idx] = false;
                diag1Taken[d1Idx] = false;
                piecesPlaced--;
                
                if (row == n - 1) {
                    break;
                }
            }
        }
        
        public int diag2Index(int row, int col, int n) {
            return row + col;
        }
        
        public int diag1Index(int row, int col, int n) {
            return (n - 1 - row) + col;
        }
        
        public List<String> getBoard() {
            ArrayList<String> board = new ArrayList<String>();
            for (int i = 0; i < colIdxPerRow.length; i++) {
                board.add(rowStringForColIdx[colIdxPerRow[i]]);
            }
            return board;
        } 
    }
    

Log in to reply
 

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