八皇后
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。但是通过计算机计算最终结果是92种方案。
首先来看下面这张图：
我们来分析一下：
首先，从第一行开始，在第一行中首先找个位置放置一个皇后，比如放到第一行第一列的位置接着，从第二行开始，首先看第二行第一列是否能够放置，由于第一列中以放置了皇后，所以该位置不能再放置；接着来判断第二行第二列是否能放置，判断方式是：1. 首先看该列(第二列)是否已放置皇后，2.接着看该行(第二行)是否已放置皇后；3.接着看该位置的斜线上是否已放置皇后；经过这三步，可以判断出第二行第二列可以放置
分析到这里是否能找出什么规律呢？
流程是首先从第一行开始遍历，第一行的遍历列，选择一列放置皇后，接着开始第二行，从第二行中选择一个能放置皇后的位置，接着开始第三行.....，一直到第八行，我们发现每一次放置皇后时都需要判断一下该位置是否能放置，而且判断的方法都是一样的，所以可以使用递归来实现！
直接上代码：
/**
* 八皇后问题
*/
public class EightQueens {
public static int count = 0;
/**
* 从第row行开始，找出一个位置放置棋子
*/
public static void search(int row, int[][] queens){
int[][] queens2 = queens.clone();
if(8 == row){
count++;
System.out.println("第"+ count +"种方案：");
for(int i=0;i<8;i++){
for(int j=0; j<8;j++){
System.out.print(queens2[i][j] + " ");
}
System.out.println();
}
}else{
for(int j=0; j<8; j++){
//判断下该位置是否可以放置
if(check(queens2, row, j)){
//继续下一行
queens2[row][j] = 1;
search(row+1, queens2);
queens2[row][j] = 0;
}
}
}
}
private static boolean check(int[][] queens, int row, int column) {
//1.判断该行是否已放置棋子
for(int j=0; j<8; j++){
if(queens[row][j] == 1)
return false;
}
//2.判断该列是否已放置棋子
for(int i=0; i<8; i++){
if(queens[i][column] == 1)
return false;
}
//3.判断该点的左上方是否已放置棋子
for(int i=row, j=column; i>=0 && j>=0; i--,j--){
if(queens[i][j] == 1)
return false;
}
//4.判断该点的右下方是否已放置棋子
for(int i=row, j=column; i<8 && j<8; i++,j++){
if(queens[i][j] == 1)
return false;
}
//5.判断该点的左下方是否已放置棋子
for(int i=row, j=column; i<8 && j>=0; i++,j--){
if(queens[i][j] == 1)
return false;
}
//6.判断该点的右上方是否已放置棋子
for(int i=row, j=column; i>=0 && j<8; i--,j++){
if(queens[i][j] == 1)
return false;
}
return true;
}
public static void main(String[] args) {
//8行8列，初始化为0
int[][] queens = new int[8][8];
search(0, queens);
}
}
结果
第1种方案：
.........
第91种方案： 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 第92种方案： 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
