Question
Formatted question description: https://leetcode.ca/all/52.html
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
Algorithm
In fact, I think the order of the two Queens-question should be reversed. The previous question is a little more complicated than this one. There is no difference in essence between the two. Both have to be solved by backtracking. If you understand the previous question The idea of the question, this question only needs to make a small change, no need to ask for the specific queen’s pendulum, just need to increase the counter by one every time a solution is generated.
Code
Java
public class N_Queens_II {
// just simply return list.size(), seems costly if only count is needed
public class Solution {
List<List<String>> list = new ArrayList<List<String>>();
public int totalNQueens(int n) {
if (n <= 0)
return 0;
// index is row-number, place[index] is position of queen on that
// row
int[] place = new int[n];
dfs(n, 0, place);
return list.size();
}
public void dfs(int n, int currentRow, int[] place) {
if (currentRow == n) {
// save to list
saveToList(place);
return;
}
for (int i = 0; i < n; i++) {
if (isValid(i, currentRow, place)) {
place[currentRow] = i; // 1 meaning place queen
dfs(n, currentRow + 1, place);
place[currentRow] = i; // undo place queen
}
}
}
public boolean isValid(int currentRowPosition, int currentRow,
int[] place) {
// check all previous rows
for (int i = 0; i < currentRow; i++) {
if (place[i] == currentRowPosition
|| currentRow - i == (int) Math.abs(place[i] - currentRowPosition))
return false;
}
return true;
}
public void saveToList(int[] place) {
int len = place.length;
List<String> one = new ArrayList<String>(len);
// construct string of n dots...
String row = "";
for (int i = 0; i < len; i++) {
row += ".";
}
for (int i = 0; i < len; i++) {
int rowPosition = place[i]; // at position place[i] on row i
one.add(row.substring(0, rowPosition) + "Q"
+ row.substring(rowPosition + 1));
}
list.add(one);
}
}
}