Super FAST Java solution


  • 0

    There are 5 solutions HERE, if you are interested in digging deeper in N-Queens problem. Step by step, one solution by one solution, digging deeper and deeper and finally comes to the fastest one - the solution using bit array.

    I listed 2 solutions below, one is normal, and another is quite fast. I guess, the fastest.

    Below is a normal one, 8ms

    public class Solution {
        private boolean[] pie, na, shu;
        private int[] sol;
        // pie = row + col;
        // na = n - 1 + col - row;
        public List<List<String>> solveNQueens(int n) {
            shu = new boolean[n];
            pie = new boolean[2 * n - 1];
            na = new boolean[2 * n - 1];
            sol = new int[n];
            List<List<String>> res = new ArrayList();
            DFS(res, 0, n);
            return res;
        }
        private void DFS(List<List<String>> res, int row, int N) {
            for (int col = 0; col < N; col++) {
                int j = row + col, k = N - 1 + col - row;
                if (shu[col] || pie[j] || na[k]) continue;
                sol[row] = col;
                if (row == N - 1) {
                    List<String> list = new ArrayList();
                    for (int i = 0; i < N; i++) {
                        String s = "";
                        for (int c = 0; c < N; c++) {
                            if (c != sol[i]) s += ".";
                            else s += "Q";
                        }
                        list.add(s);
                    }
                    res.add(list);
                } else {
                    shu[col] = pie[j] = na[k] = true;
                    DFS(res, row + 1, N);
                    shu[col] = pie[j] = na[k] = false;
                }
            }
        }
    }
    

    The solution below is 4ms, beats 99%:

    public class Solution {
        // pie = row + col;
        // na = n - 1 + col - row;
        int[] sol;
        public List<List<String>> solveNQueens(int n) {
            sol = new int[n];
            List<List<String>> res = new ArrayList();
            DFS(res, n, 0, 0, 0, 0);
            return res;
        }
        private void DFS(List<List<String>> res, int N, int row, int shu, int pie, int na) {
            int ok = ((1 << N) - 1) & ~(shu | pie | na);
            while (ok != 0) {
                int p = ok & -ok;
                ok ^= p;
                sol[row] = p;
                if (row == N - 1) {
                    List<String> list = new ArrayList();
                    for (int i = 0; i < N; i++) {
                        StringBuilder sb = new StringBuilder();
                        for (int c = 0; c < N; c++) {
                            if ((1 << c) == sol[i]) sb.append("Q");
                            else sb.append(".");
                        }
                        list.add(sb.toString());
                    }
                    res.add(list);
                } else {
                    DFS(res, N, row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
                }
            }
        }
    }
    

Log in to reply
 

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