5ms easy understanding backtrack Java solution (beats 93%)


  • 0
    public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<List<String>>();
        char[][] backtrack = new char[n][n];
        for (int i = 0; i < backtrack.length; i++) Arrays.fill(backtrack[i], '.');       
        NQueensHelper(result, backtrack, 0, n); //Start backtracking from row 1 to n
        return result;
    }
    public void NQueensHelper(List<List<String>> result, char[][] backtrack, int row, int n){
        if(row==n) {
            List<String> solution = new ArrayList();
            for(char[] each_row: backtrack) solution.add(String.valueOf(each_row));
            result.add(solution);   //out put this solution
            return;
        }
        for(int col = 0; col<n; col++){//check every col at each row
            if(isValid(backtrack,row,col,n)){//check to see wether Q at (row,col) is applicable
                backtrack[row][col] = 'Q';//try placing Q at (row,col)
                NQueensHelper(result, backtrack,row + 1,n); // go to next row
                backtrack[row][col] = '.';//withdraw Q at (row,col)
            }
        }
    }
    public boolean isValid(char[][] backtrack, int row, int col, int n){
        int cur_goleft = col, cur_goright = col;
        for(int r = row-1; r>=0;r--){
            if((cur_goleft>0&&backtrack[r][--cur_goleft]=='Q')|| //check backwards through diagonal \
                (backtrack[r][col]=='Q')|| //check backwards through the same column
                (cur_goright<n-1&&backtrack[r][++cur_goright]=='Q')) //check backwards through diagonal /
                return false;
        }
        return true;
    }
    }

Log in to reply
 

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