• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
88%
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) {
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)) {
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) {
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) {