Sharing my code... JAVA


  • 0
    D
    public class Solution {
        public List<List<String>> solveNQueens(int n) {
            List<List<String>> result = new ArrayList<List<String>>();
            if (n==0) return result;
            int[] positions = new int[n];  //position in each row
            Arrays.fill(positions, -1);
            int row = 0;
            while (row>=0) {
                if (row==n) {
                    result.add(genSolution(positions,n));
                    row--;
                    continue;
                }
                boolean forward = false;
                for (int i=positions[row]+1; i<n; i++) {
                    if (isValid(positions, i, row)) {
                        positions[row] = i;
                        forward = true;
                        break;
                    }
                }
                if (forward) row++;
                else {
                    positions[row]=-1;
                    row--;
                }
            }
            return result;
        }
        private List<String> genSolution(int[] positions, int n) {
            List<String> solution = new ArrayList<String>(n);
            char[] a = new char[n];
            Arrays.fill(a, '.');
            for (int position: positions) {
                a[position] = 'Q';
                solution.add(new String(a));
                a[position] = '.';
            }
            return solution;
        }
        private boolean isValid(int[] positions, int x, int y){
            for (int row = 0; row < y; row++) {
                int position = positions[row];
                if (position == x) return false;
                if (y-row == Math.abs(x-position)) return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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