题解 | #N皇后问题#
N皇后问题
http://www.nowcoder.com/practice/c76408782512486d91eea181107293b6
import java.util.*;
public class Solution {
int[][] chessboard;
int sum = 0;
/**
*
* @param n int整型 the n
* @return int整型
*/
public int Nqueen (int n) {
// write code here
if (n == 1) {
return 1;
}
chessboard = new int[n][n];
goNext(0, n);
return sum;
}
private void goNext(int row, int n) {
//终止条件
if (row == n) {
//说明已经走通
sum++;
} else {
for (int i = 0; i < n; i++) {
if (check(n, row, i)) {
//如果这个可以放，那就走下一步
chessboard[row][i] = 1;
goNext(row + 1, n);
//回溯
chessboard[row][i] = 0;
}
}
}
}
public boolean check(int n, int x, int y) {
//1.判断左上方向有无棋子
for (int i = x, j = y; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 1) {
return false;
}
}
//2.判断右上方向有无棋子
for (int i = x, j = y; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 1) {
return false;
}
}
//3.判断上方有无棋子
for (int i = x; i >= 0; i--) {
if (chessboard[i][y] == 1) {
return false;
}
}
return true;
}
}
