Java clean code using back tracking


  • 0
    S
    public class Solution {
        boolean[] columns, lr, rl;
        StringBuilder init_sb = new StringBuilder();
        
        public List<String[]> solveNQueens(int n) {
            columns = new boolean[n];
            lr = new boolean[2*n - 1];
            rl = new boolean[2*n - 1];
            for (int i = 0; i < n; ++i) {
                init_sb.append('.');
            }
            helper(n, 0, new String[n]);
            return ret;
        }
        
        private boolean check(int x, int y, int n) {
            if (columns[y] || lr[n - 1 - x + y] || rl[x + y])
                return false;
            return true;
        }
        
        private void set(int x, int y, int n) {
            int size = columns.length;
            columns[y] = true; lr[n - 1 - x + y] = true; rl[x + y] = true;
        }
        
        private void unset(int x, int y, int n) {
            columns[y] = false; lr[n - 1 - x + y] = false; rl[x + y] = false;
        }
    
        public List<String[]> ret = new ArrayList<String[]>();
        
        public void helper(int n, int idx, String[] ans) {
            if (idx == n) {
                ret.add(ans.clone());
            }
            for (int i = 0; i < n; ++i) {
                if (check(idx, i, n)) {
                    set(idx, i, n);
                    char[] cs = new char[n];
                    Arrays.fill(cs, '.');
                    cs[i] = 'Q';
                    ans[idx] = new String(cs);
                    helper(n, idx + 1, ans);
                    unset(idx, i, n);
                }
            }
        }
    }

Log in to reply
 

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