Really Easy To Understand 6ms Java Solution With Backtracking


  • 0
    G
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> res = new LinkedList<List<String>>();
            char[][] sol = new char[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) sol[i][j] = '.';
            }
            helper(res, sol, n);
            return res;
        }
        
        public void helper(List<List<String>> res, char[][] sol, int n) {
            if (n == 0) {
                List<String> list = new LinkedList<>();
                for (int i = 0; i < sol.length; ++i) list.add(new String(sol[i]));
                res.add(list);
                return;
            }
            for (int i = 0; i < sol.length; ++i) {
                if (sol[sol.length - n][i] == '.' && isValid(sol, sol.length - n, i, sol.length)) {
                    sol[sol.length - n][i] = 'Q';
                    helper(res, sol, n - 1);
                    sol[sol.length - n][i] = '.';
                }
            }
        }
        
        public boolean isValid(char[][] sol, int i, int j, int n) {
            for (int k = 0; k < n; ++k) {
                if (sol[i][k] == 'Q' || sol[k][j] == 'Q') return false;
            }
            int k = 1;
            while (i - k >= 0 && j - k >= 0) {
                if (sol[i - k][j - k] == 'Q') return false;
                k++;
            }
            k = 1;
            while (i - k >= 0 && j + k < n) {
                if (sol[i - k][j + k] == 'Q') return false;
                k++;
            }
            return true;
        }
    }

Log in to reply
 

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