51. N-Queens

Link

Solution

這題雖說是放在DFS但我覺得更像是backtrace

就是窮舉所有可能性一一找到並加到result中

T: O (n! * n^2)

n! 是針對每一row的每個元素進行validation的次數。

1st row 是 n 次。 2nd row 是 n-1 次，因為不會跟1st row所選的同col 3rd row 是 n-2 次，因為不會跟1st, 2nd row所選的同col n^2 使進行validation的time complexity

 public List<List<String>> solveNQueens(int n) {
        char[][] tempResult = new char[n][n];
        
        for(int row = 0; row < n; row++){
            for(int col = 0; col < n; col++){
                tempResult[row][col] = '.';
            }
        }
        
        List<List<String>> res = new LinkedList<>();
        
        helper(res, tempResult, 0);
        return res;
    }
    
    public void helper(List<List<String>> res, char[][] tempResult, int row){
        if(row == tempResult.length){
            res.add(toString(tempResult));
            return;
        }
        for(int col = 0; col < tempResult.length; col++){
            //choosed
            tempResult[row][col] = 'Q';
            //derivation
            if(isValid(tempResult, row, col)){
                helper(res, tempResult, row+1);
            }
            //unchoosed
            tempResult[row][col] = '.';
        }
        
    }
    
    public boolean isValid(char[][] tempResult, int row, int col){
        for(int i = 0; i < row; i++){
            for(int j = 0; j < tempResult.length; j++){
                if((i == row || j == col || Math.abs(row - i) == Math.abs(col - j)) 
                   && tempResult[i][j] == 'Q'){
                    return false;
                }
            }
        }
        return true;
        
    }
    
    
    public List<String> toString(char[][] tempResult){
        int n = tempResult.length;
        List<String> ret = new LinkedList<>();
        for(int i = 0; i < n; i++){
            String temp = new String(tempResult[i]);
            ret.add(temp);
        }
        return ret;
    }