八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解[1]。 以上内容摘自*：http://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98
代码如下：
public class Demo {
public static void main(String[] args) {
nextRowPlace(START_ROW);
}
private static final int ROW = 8, COL = 8, START_ROW = 0, START_COL = 0;
private static boolean[][] board = new boolean[8][8];
private static void nextRowPlace(final int row) {
if(row == ROW){
print();
return;
}
for(int j=START_COL; j!=COL; ++j)
if(checkPosValid(row, j)){
board[row][j] = true;
nextRowPlace(row+1);
board[row][j] = false;
}
return;
}
private static boolean checkPosValid(final int row, final int col) {
for(int i=START_ROW; i!=ROW; ++i)
if(board[i][col])
return false;
for(int i=row, j=col; i!=START_ROW-1 && j!=START_COL-1; --i, --j)
if(board[i][j])
return false;
for(int i=row, j=col; i!=START_ROW-1 && j!= COL; --i, ++j)
if(board[i][j])
return false;
return true;
}
private static int count = 0;
private static void print() {
System.out.println("--- --- --- --- --- " + ++count +" --- ---");
for(int i=START_ROW; i!=ROW; ++i){
for(int j=START_COL; j!=COL; ++j)
System.out.print(board[i][j] ? "O " : "X ");
System.out.println();
}
System.out.println();
return;
}
}
运行结果如下：
--- --- --- --- --- 1 --- --- O X X X X X X X X X X X O X X X X X X X X X X O X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X O X X X X --- --- --- --- --- 2 --- --- O X X X X X X X X X X X X O X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X O X X X X X X X X X X O X X X --- --- --- --- --- 3 --- --- O X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X X O X X X X X O X X X X X --- --- --- --- --- 4 --- --- O X X X X X X X X X X X X X O X X X X X O X X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X O X X X X O X X X X X --- --- --- --- --- 5 --- --- X O X X X X X X X X X O X X X X X X X X X O X X X X X X X X X O X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X X --- --- --- --- --- 6 --- --- X O X X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X X X X O X X X X X O X X X X X O X X X X --- --- --- --- --- 7 --- --- X O X X X X X X X X X X O X X X X X X X X X O X X X X O X X X X O X X X X X X X X X X X X X X O X X X X X O X X X X O X X X X X --- --- --- --- --- 8 --- --- X O X X X X X X X X X X X O X X O X X X X X X X X X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X O X X X --- --- --- --- --- 9 --- --- X O X X X X X X X X X X X O X X X X X X X X X O X X O X X X X X O X X X X X X X X X X O X X X X X X X X X X O X X X X X O X X X --- --- --- --- --- 10 --- --- X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X X X X X X X X O X X X X O X X X O X X X X X X X X X X O X X X X --- --- --- --- --- 11 --- --- X O X X X X X X X X X X X X O X X X X X O X X X X X X X X X X O O X X X X X X X X X X O X X X X X X X X X O X X X X O X X X X X --- --- --- --- --- 12 --- --- X O X X X X X X X X X X X X X O X X X X X O X X O X X X X X X X X X O X X X X X X X X X O X X X X X X X X X O X X X X O X X X X --- --- --- --- --- 13 --- --- X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X O X X --- --- --- --- --- 14 --- --- X X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X O O X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X X --- --- --- --- --- 15 --- --- X X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X O X X X X X O X X X X X O X X X X X X X X X X O X O X X X X X X X --- --- --- --- --- 16 --- --- X X O X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X --- --- --- --- --- 17 --- --- X X O X X X X X X X X X O X X X X X X X X X X O X X X O X X X X O X X X X X X X X X X X X X O X X O X X X X X X X X X X X O X X --- --- --- --- --- 18 --- --- X X O X X X X X X X X X X O X X X O X X X X X X X X X X O X X X X X X X X X X O O X X X X X X X X X X X X X O X X X X O X X X X --- --- --- --- --- 19 --- --- X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X O X X X X X X X X X X O X X X X X X X X X X X O X X X X O X X X --- --- --- --- --- 20 --- --- X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X X X X X O X X X O X X X X X X X X X X X X X X O X X X O X X X X --- --- --- --- --- 21 --- --- X X O X X X X X X X X X X O X X X X X O X X X X O X X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X X O X X X X X X --- --- --- --- --- 22 --- --- X X O X X X X X X X X X X O X X X X X O X X X X X O X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X O X X X X X X X --- --- --- --- --- 23 --- --- X X O X X X X X X X X X X O X X X X X X X X X O O X X X X X X X X X X O X X X X X X X X X X O X X X X X O X X X X O X X X X X X --- --- --- --- --- 24 --- --- X X O X X X X X X X X X X O X X X X X X X X X O O X X X X X X X X X X X O X X X X X X X X X O X X O X X X X X X X X X O X X X X --- --- --- --- --- 25 --- --- X X O X X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X O X X X X X O X X X --- --- --- --- --- 26 --- --- X X O X X X X X X X X X X X O X X O X X X X X X X X X X X X X O X X X X O X X X O X X X X X X X X X X O X X X X X X X X X O X X --- --- --- --- --- 27 --- --- X X O X X X X X X X X X X X O X X O X X X X X X X X X X X X X O X X X X X O X X X X X O X X X X O X X X X X X X X X X X O X X X --- --- --- --- --- 28 --- --- X X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X X --- --- --- --- --- 29 --- --- X X X O X X X X O X X X X X X X X X X X O X X X X X X X X X X O X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X --- --- --- --- --- 30 --- --- X X X O X X X X O X X X X X X X X X X X O X X X X X X X X X X O X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X --- --- --- --- --- 31 --- --- X X X O X X X X X O X X X X X X X X X X O X X X X X X X X X X O X X X X X O X X O X X X X X X X X X O X X X X X X X X X X X O X --- --- --- --- --- 32 --- --- X X X O X X X X X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X X X X X X X X O O X X X X X X X X X X X O X X X --- --- --- --- --- 33 --- --- X X X O X X X X X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X X X X X X X X O X X X X O X X X O X X X X X X X --- --- --- --- --- 34 --- --- X X X O X X X X X O X X X X X X X X X X X X O X X X X X O X X X O X X X X X X X X X X X X X X O X X X X X O X X X X O X X X X X --- --- --- --- --- 35 --- --- X X X O X X X X X O X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X X O X X --- --- --- --- --- 36 --- --- X X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X O X X X X X X X X X O X X X X X X X X X O X X X X X X X X X O X --- --- --- --- --- 37 --- --- X X X O X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X X X X X X X X X O X X O X X X X X X X X X X X O X --- --- --- --- --- 38 --- --- X X X O X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X O X X X --- --- --- --- --- 39 --- --- X X X O X X X X X X X X X O X X X X X X X X X O X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X X X O X X X X X X --- --- --- --- --- 40 --- --- X X X O X X X X X X X X X X O X O X X X X X X X X X X X X X X O X X X X O X X X X O X X X X X X X X X X X O X X X X O X X X X X --- --- --- --- --- 41 --- --- X X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X X --- --- --- --- --- 42 --- --- X X X O X X X X X X X X X X O X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X O X X X X X X X X X X X X O --- --- --- --- --- 43 --- --- X X X O X X X X X X X X X X O X X X X X O X X X X X O X X X X X O X X X X X X X X X X X X O X X X X X X X X X O X O X X X X X X --- --- --- --- --- 44 --- --- X X X O X X X X X X X X X X X O O X X X X X X X X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X X X X X O X X X --- --- --- --- --- 45 --- --- X X X O X X X X X X X X X X X O O X X X X X X X X X X X O X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X --- --- --- --- --- 46 --- --- X X X O X X X X X X X X X X X O X X X X O X X X X X O X X X X X O X X X X X X X X X X X X X O X X O X X X X X X X X X X X O X X --- --- --- --- --- 47 --- --- X X X X O X X X O X X X X X X X X X X O X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X X X X O X X X O X X X X X --- --- --- --- --- 48 --- --- X X X X O X X X O X X X X X X X X X X X X X X O X X X O X X X X X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X --- --- --- --- --- 49 --- --- X X X X O X X X O X X X X X X X X X X X X X X O X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X O X X X X --- --- --- --- --- 50 --- --- X X X X O X X X X O X X X X X X X X X O X X X X X X X X X O X X X X X X X X X O X X O X X X X X O X X X X X X X X X X X X X O X --- --- --- --- --- 51 --- --- X X X X O X X X X O X X X X X X X X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X X X X X O X X O X X X X X X X --- --- --- --- --- 52 --- --- X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X --- --- --- --- --- 53 --- --- X X X X O X X X X O X X X X X X X X X X X X X O O X X X X X X X X X X O X X X X X X X X X X O X X X O X X X X X X X X X X O X X --- --- --- --- --- 54 --- --- X X X X O X X X X X O X X X X X O X X X X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X X O X --- --- --- --- --- 55 --- --- X X X X O X X X X X O X X X X X O X X X X X X X X X X X X X O X X O X X X X X X X X X X X X X O X X X X X O X X X X X O X X X X --- --- --- --- --- 56 --- --- X X X X O X X X X X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X O X X X X X X X X X X X X O X X X O X X X X X X --- --- --- --- --- 57 --- --- X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X X X X O X X X X X O X X X X X O X X X X X O X X X X X X --- --- --- --- --- 58 --- --- X X X X O X X X X X X X X X O X O X X X X X X X X X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X X X O X X X X X --- --- --- --- --- 59 --- --- X X X X O X X X X X X X X X O X X O X X X X X X X X X O X X X X X X X X X X X O O X X X X X X X X X O X X X X X X X X X X O X X --- --- --- --- --- 60 --- --- X X X X O X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X O X X X X X X X X X X O X X X X X X X X X X X O --- --- --- --- --- 61 --- --- X X X X O X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X O X X X X X X X X X X X X X X O X X X O X X X X --- --- --- --- --- 62 --- --- X X X X O X X X X X X X X X O X X X X O X X X X O X X X X X X X X X O X X X X X X X X X X X X O X X X X X O X X X O X X X X X X --- --- --- --- --- 63 --- --- X X X X O X X X X X X X X X X O X X X O X X X X O X X X X X X X X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X --- --- --- --- --- 64 --- --- X X X X O X X X X X X X X X X O X X X O X X X X O X X X X X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X --- --- --- --- --- 65 --- --- X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X X X X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X --- --- --- --- --- 66 --- --- X X X X X O X X X O X X X X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X O X X X X X X X X X X O X X X O X X X X --- --- --- --- --- 67 --- --- X X X X X O X X X O X X X X X X X X X X X X O X O X X X X X X X X X X O X X X X X X X X X X X O X X X X O X X X X X O X X X X X --- --- --- --- --- 68 --- --- X X X X X O X X X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X X X X X X X X X O X O X X X X X X X X X O X X X X --- --- --- --- --- 69 --- --- X X X X X O X X X X O X X X X X O X X X X X X X X X X X X X X O X X X O X X X X X O X X X X X X X X X X X X O X X X X X O X X X --- --- --- --- --- 70 --- --- X X X X X O X X X X O X X X X X O X X X X X X X X X X X X X X O X X X X O X X X X O X X X X X X X X X O X X X X X X X X X X O X --- --- --- --- --- 71 --- --- X X X X X O X X X X O X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X X O X X X X X O X X X X X X X X X X X X X O --- --- --- --- --- 72 --- --- X X X X X O X X X X O X X X X X X X X X O X X X X X X X X X X O O X X X X X X X X X X O X X X X X O X X X X X X X X X X X X O X --- --- --- --- --- 73 --- --- X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X O X X X X X X X X X X X O O X X X X X X X X X X X O X X X --- --- --- --- --- 74 --- --- X X X X X O X X X X O X X X X X X X X X X X O X X O X X X X X X X X X X X X X O X X X X O X X X O X X X X X X X X X X O X X X X --- --- --- --- --- 75 --- --- X X X X X O X X X X O X X X X X X X X X X X O X X X X O X X X X O X X X X X X X X X X X X X X O X O X X X X X X X X X X O X X X --- --- --- --- --- 76 --- --- X X X X X O X X X X X O X X X X O X X X X X X X X X X X O X X X X X X X X X X O X O X X X X X X X X X X X X O X X X O X X X X X --- --- --- --- --- 77 --- --- X X X X X O X X X X X O X X X X X O X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X X --- --- --- --- --- 78 --- --- X X X X X O X X X X X O X X X X X X X X X X O X O X X X X X X X X X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X O --- --- --- --- --- 79 --- --- X X X X X O X X X X X O X X X X X X X X X X O X O X X X X X X X X X X X X X X O X O X X X X X X X X X X O X X X X X O X X X X X --- --- --- --- --- 80 --- --- X X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X O X X X X X O X X X X X O X X X X X --- --- --- --- --- 81 --- --- X X X X X X O X O X X X X X X X X X O X X X X X X X X X X X X O X X X X X O X X X X X O X X X X X O X X X X X X X X X X O X X X --- --- --- --- --- 82 --- --- X X X X X X O X X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X X O X X X X O X X X X X O X X X X X X X X X X O X X --- --- --- --- --- 83 --- --- X X X X X X O X X O X X X X X X X X X X X O X X X X O X X X X X O X X X X X X X X X X O X X X X X X X X X X X O X X X X O X X X --- --- --- --- --- 84 --- --- X X X X X X O X X X O X X X X X O X X X X X X X X X X X X O X X X X X X X X X O X X X X O X X X X O X X X X X X X X X O X X X X --- --- --- --- --- 85 --- --- X X X X X X O X X X O X X X X X X X X X X X X O X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X X X X X O X X X X --- --- --- --- --- 86 --- --- X X X X X X O X X X X O X X X X X O X X X X X X X X X X O X X X X X X X X X X O O X X X X X X X X X O X X X X X X X X X X O X X --- --- --- --- --- 87 --- --- X X X X X X O X X X X O X X X X X O X X X X X X X X X X X X X O X X X X X O X X O X X X X X X X X X O X X X X X X X X X O X X X --- --- --- --- --- 88 --- --- X X X X X X O X X X X X O X X X X X O X X X X X O X X X X X X X X X X X X O X X X X X X X X X O X O X X X X X X X X X O X X X X --- --- --- --- --- 89 --- --- X X X X X X X O X O X X X X X X X X X O X X X X O X X X X X X X X X X X X X O X X X X X O X X X X X O X X X X X X X X X X O X X --- --- --- --- --- 90 --- --- X X X X X X X O X O X X X X X X X X X X O X X X X X O X X X X X O X X X X X X X X X X X X X O X X X X O X X X X X X X X X O X X --- --- --- --- --- 91 --- --- X X X X X X X O X X O X X X X X O X X X X X X X X X X X X O X X X O X X X X X X X X X X O X X X X X X X X X O X X X X O X X X X --- --- --- --- --- 92 --- --- X X X X X X X O X X X O X X X X O X X X X X X X X X O X X X X X X X X X X O X X X O X X X X X X X X X X X X O X X X X X O X X X
2014-04-12