51. N-Queens

Given an integer n, return all distinct solutions to the n-queens puzzle.

recursion, backtrack

• No two queens in the same column, row, diagonal, and reverse diagonal

• Let $x$ be index of column, $y$ as index of row, $n$ is the input represents number of queens

• mark index of columns which are forbidden

• mark diagonal which have been occupied: $x-y=const$

• mark diagonal which have been occupied: $x+y=const$

class Solution {
    // true means occupied
    boolean[] column;
    
    // diagonal
    // x-y == constant;
    boolean[] diag1;
    // reverse diagonal
    // x+y == constant
    boolean[] diag2;
    
    // constant been used globally
    int n;
    
    // 
    char[][] board;
    
    public List<List<String>> solveNQueens(int n) {
        column = new boolean[n];
        // for n*n square, there are in total of 2*n-1 diagonals
        // and reverse diagonals
        diag1 = new boolean[2*n-1];
        diag2 = new boolean[2*n-1];
        board = new char[n][n];
        for(int i=0;i<n; i++){
            for(int j =0;j<n; j++){
                board[i][j]='.';
            }
        }
        
        this.n = n;
        
        List<List<String>> result = new ArrayList<>();
        recursion(0, result);
        
        return result;
    }
    
    private void recursion(int row, List<List<String>> result){
        if (row == n){
            result.add(convertBoardToResultEntry());
            return;
        }
        
        for (int i = 0; i<n; i++){
            if (isAvailablePosition(i, row)){ 
                updateOccupancy(i, row, true);
                recursion(row+1, result);
                updateOccupancy(i, row, false);
            }
        }     
    }
    
    // check if x, y position is available
    // x is cloumn, y is row
    private boolean isAvailablePosition(int x, int y){        
        return !column[x] && !diag1[x-y+n-1] && !diag2[x+y];
    }
    
    private List<String> convertBoardToResultEntry(){
        List<String> result = new ArrayList<>();
        for (int i=0; i<n; i++){
            result.add(new String(board[i]));
        }  
        return result;
    }
    
    private void updateOccupancy(int x, int y, boolean state){ 
        column[x] = state;
        diag1[x-y+n-1] = state;
        diag2[x+y] = state;
        board[y][x] = state ? 'Q' : '.';
    } 
}