n x n 大小的国际象棋棋盘,找出所以放下n个互相不能吃掉的皇后的方法,N-Queens II是找出有几种这样方法。
一般找出所有的可能性的题目,都是DFS。这题算法不难,就是一行一行来,先放一个皇后在某一行的一个格子里,然后检查这个能不能被这行上面已经放了的皇后吃掉。如果可以被吃掉,那么这个格子就不能放了。如果这行后面还有格子,就重复以上步骤。如果找到一个可能的格子,记录下这行放了在哪一个格子,对下一行进行同样的操作。如果有幸能在最后一行找到一个可能的格子,那么就找到一种解法。I就记录这种解法,II就对可能解法数加一。
Debug了挺久的,主要是DFS没想清楚,在主函数里面还用了循环call递归的placeQueue,以后对DFS要注意检查这种错误。检查新放的皇后是否和已放的皇后们冲突的函数也容易写错,尤其是斜的。检查(i,j)和(i1,j2)是否冲突要看 j==j2, i-i1 = j-j2 || i-i1 == -(j-j2)。检查列好理解,斜的话,(i,j)和(i+k, j+k)或者(i+k, j-k)在同斜线上。
N-Queens
public class Solution {
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> ret = new ArrayList<String[]>(n);
if (n==0) return ret;
ArrayList<Integer> cols = new ArrayList<Integer>(n);
for (int i=0; i<n; i++) {
cols.add(0);
}
ArrayList<Integer[]> sln = new ArrayList<Integer[]>();
placeQueue(0, cols, n, sln);
// solutions
for (int p=0; p<sln.size(); p++) {
Integer[] curSolution = sln.get(p);
String[] map = new String[n];
for (int i=0; i<n; i++) {
String oneRow = new String();
for (int j=0; j<n; j++) {
if (j!=curSolution[i]) {
oneRow += ".";
} else {
oneRow += "Q";
}
}
map[i] = oneRow;
}
ret.add(map);
}
return ret;
}
public void placeQueue(int row, ArrayList<Integer> cols,
int n, ArrayList<Integer[]> ret) {
if (row == n) {
Integer[] copyCols = new Integer[n];
for (int i=0; i<n; i++) {
copyCols[i] = cols.get(i);
}
ret.add(copyCols);
return;
}
for (int i=0; i<n; i++) {
cols.set(row, i);
if (checkValid(row, i, cols)) {
placeQueue(row+1, cols, n, ret);
}
}
}
public boolean checkValid(int row, int col, ArrayList<Integer> cols) {
//check columns
for (int i=0; i<row; i++) {
if (col == cols.get(i)) {
return false;
}
}
//check diagonal
for (int i=0; i<row; i++) {
if (row-i == col-cols.get(i)
|| row-i == cols.get(i)-col) {
return false;
}
}
return true;
}
}
N-Queens II
public class Solution {
public int totalNQueens(int n) {
if (n==0) return 0;
ArrayList<Integer> cols = new ArrayList<Integer>(n);
for (int i=0; i<n; i++) {
cols.add(0);
}
int[] ret = new int[1];
placeQueue(0, cols, n, ret);
return ret[0];
}
public void placeQueue(int row, ArrayList<Integer> cols,
int n, int[] ret) {
if (row == n) {
ret[0]++;
return;
}
for (int i=0; i<n; i++) {
cols.set(row, i);
if (checkValid(row, i, cols)) {
placeQueue(row+1, cols, n, ret);
}
}
}
public boolean checkValid(int row, int col, ArrayList<Integer> cols) {
//check columns
for (int i=0; i<row; i++) {
if (col == cols.get(i)) {
return false;
}
}
//check diagonal
for (int i=0; i<row; i++) {
if (row-i == col-cols.get(i)
|| row-i == cols.get(i)-col) {
return false;
}
}
return true;
}
}