SHARE
TWEET

Untitled

sweet1cris Sep 14th, 2017 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class NQueens {
  2.   // Method 1: validate the queen position in O(n) each time.
  3.   public List<List<Integer>> nqueens(int n) {
  4.     // Assumptions: n > 0.
  5.     List<List<Integer>> result = new ArrayList<List<Integer>>();
  6.     // cur will be a list of size n, and cur[i] is the column number
  7.     // where the queen on row i positioned.
  8.     List<Integer> cur = new ArrayList<Integer>();
  9.     helper(n, cur, result);
  10.     return result;
  11.   }
  12.  
  13.   private void helper(int n, List<Integer> cur, List<List<Integer>> result) {
  14.     // base case: when for all the rows we know where the queen is positioned.
  15.     if (cur.size() == n) {
  16.       result.add(new ArrayList<Integer>(cur));
  17.       return;
  18.     }
  19.     for (int i = 0; i < n; i++) {
  20.       // check if putting a queen at column i at current row is valid.
  21.       if (valid(cur, i)) {
  22.         cur.add(i);
  23.         helper(n, cur, result);
  24.         cur.remove(cur.size() - 1);
  25.       }
  26.     }
  27.   }
  28.  
  29.   private boolean valid(List<Integer> cur, int column) {
  30.     int row = cur.size();
  31.     for (int i = 0; i < row; i++) {
  32.       if (cur.get(i) == column || Math.abs(cur.get(i) - column) == row - i) {
  33.         return false;
  34.       }
  35.     }
  36.     return true;
  37.   }
  38.  
  39.   // Method 2: validate the queen position in O(1) each time.
  40.   public List<List<Integer>> nqueensII(int n) {
  41.     // Assumptions: n > 0.
  42.     List<List<Integer>> result = new ArrayList<List<Integer>>();
  43.     // cur will be a list of size n, and cur[i] is the column number  
  44.     // where the queen on row i positioned.
  45.     int[] cur = new int[n];
  46.     // record on which columns there is already a queen.
  47.     boolean[] usedColumns = new boolean[n];
  48.     // record on which diagonal lines there is already a queen.
  49.     boolean[] usedDiagonals = new boolean[2 * n - 1];
  50.     // record on which reverse diagonal lines there is already a queen.
  51.     boolean[] usedRevDiagonals = new boolean[2 * n - 1];
  52.     helper(n, 0, cur, result, usedColumns, usedDiagonals, usedRevDiagonals);
  53.     return result;
  54.   }
  55.  
  56.   private void helper(int n, int row, int[] cur, List<List<Integer>> result,
  57. boolean[] usedColumns, boolean[] usedDiagonals, boolean[] usedRevDiagonals) {
  58.     // base case: when for all the rows we know where the queen is positioned.
  59.     if (row == n) {
  60.       result.add(toList(cur));
  61.       return;
  62.     }
  63.     for (int i = 0; i < n; i++) {
  64.       if (valid(n, row, i, usedColumns, usedDiagonals, usedRevDiagonals)) {
  65.         mark(n, row, i, usedColumns, usedDiagonals, usedRevDiagonals);
  66.         cur[row] = i;
  67.         helper(n, row + 1, cur, result, usedColumns, usedDiagonals,
  68. usedRevDiagonals);
  69.         unMark(n, row, i, usedColumns, usedDiagonals, usedRevDiagonals);
  70.       }
  71.     }
  72.   }
  73.  
  74.   private boolean valid(int n, int row, int column, boolean[] usedColumns,
  75. boolean[] usedDiagonals, boolean[] usedRevDiagonals) {
  76.     // for the reverse diagonal line, the actual range of column - row is
  77.     // actually [-(n-1), +(n-1)],
  78.     // we add n - 1 to make sure it can fit into the index.
  79.     return !usedColumns[column] && !usedDiagonals[column + row] &&
  80. !usedRevDiagonals[column - row + n - 1];
  81.   }
  82.  
  83.   private void mark(int n, int row, int column, boolean[] usedColumns, boolean[]
  84. usedDiagonals, boolean[] usedRevDiagonals) {
  85.     usedColumns[column] = true;
  86.     usedDiagonals[column + row] = true;
  87.     usedRevDiagonals[column - row + n - 1] = true;
  88.   }
  89.  
  90.   private void unMark(int n, int row, int column, boolean[] usedColumns,
  91. boolean[] usedDiagonals, boolean[] usedRevDiagonals) {  
  92.     usedColumns[column] = false;
  93.     usedDiagonals[column + row] = false;
  94.     usedRevDiagonals[column - row + n - 1] = false;
  95.   }
  96.  
  97.   private List<Integer> toList(int[] array) {
  98.     List<Integer> list = new ArrayList<>();
  99.     for (int num : array) {
  100.       list.add(num);
  101.     }
  102.     return list;
  103.   }
  104. }
RAW Paste Data
Top