93% concise, fast, and clear java solution


  • 9
    O

    The code has comment.

    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            boolean[] 
                //ocp0 = new boolean[n], //whether there's a queen ocupying nth row, I don't need it
                ocp90 = new boolean[n], //whether there's a queen ocupying nth column
                ocp45 = new boolean[2 * n - 1], // mark 45 degree occupation
                ocp135 = new boolean[2 * n - 1]; // mark 135 degree occupation
            List<List<String>> ans = new ArrayList<List<String>>();
            char[][] map = new char[n][n];
            for (char[] tmp : map) Arrays.fill(tmp, '.'); //init
            
            solve(0, n, map, ans, ocp45, ocp90, ocp135);
            return ans;
        }
        
        private void solve(int depth, int n, char[][] map, List<List<String>> ans, 
        boolean[] ocp45, boolean[] ocp90, boolean[] ocp135) {
            if (depth == n) {
                addSolution(ans, map);
                return;
            }
            
            for (int j = 0; j < n; j++)
                if (!ocp90[j] && !ocp45[depth + j] && !ocp135[j - depth + n - 1]) {
                    ocp90[j] = true;
                    ocp45[depth + j] = true;
                    ocp135[j - depth + n - 1] = true;
                    map[depth][j] = 'Q';
                    solve(depth + 1, n, map, ans, ocp45, ocp90, ocp135);
                    ocp90[j] = false;
                    ocp45[depth + j] = false;
                    ocp135[j - depth + n - 1] = false;
                    map[depth][j] = '.';
                }
        }
        
        private void addSolution(List<List<String>> ans, char[][] map) {
            List<String> cur = new ArrayList<String>();
            for (char[] i : map) cur.add(String.valueOf(i));
            ans.add(cur);
        }
    }

  • 2
    A

    @ofLucas Could you please explain how you are using these two arrays :

    ocp45 = new boolean[2 * n - 1], // mark 45 degree occupation
    ocp135 = new boolean[2 * n - 1]; // mark 135 degree occupation

    What is the logic behind assigning the [j - depth + n - 1] position as true ?


  • 0

    @aritra90tnp

    Well. It is a late response. For instance, a 3 * 3 board. There are 2 * 3 - 1 = 5 main diagonals and also 5 minor diagonals. You can draw a matrix and see it. And for the main diagonals, you can find all the cells are on the (i+j) main diagonal. And for the minor diagonal, that is ocp135 in this code, let us see [1,0] and [2,1]. They are on the same minor diagonal. Put [1,0] in [j-dpeth + n - 1] = [0 - 1 + 3 - 1] = [1], and [2,1] is [1-2+3 - 1] = [1].


Log in to reply
 

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