八皇后问题 递归求解
八皇后问题递归求解
首先介绍一下八皇后问题，八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。
思路
首先采取按行放置皇后，即先放第一行的皇后，放置后，然后在第二行上放置皇后，并进行借测，不冲突的话继续放置第三行，一次类推，到最后发现超过8行后结束。
代码如下
/** * 八皇后问题 * @author Yuedong * */public class EightQueens {static int b[]={0,0,0,0,0,0,0,0};static int sum=0;static int times=1;public static void main(String[] args){search(0);System.out.println("一共有"+sum+"个结果");} /** * 搜索指定行 * @param row */private static void search(int row){if(row==8){sum++;printResult();return;}for(int i=0;i<8;i++){if(check(row,i)){search(row+1);}}}/** * 检查m,n 这个位置是否冲突 * @param row * @param col * @return */private static boolean check(int row,int col){for(int i=0;i<row;i++){if(b[i]==col){return false;}if((b[i]+i)==(row+col)){return false;}if((b[i]-i)==(col-row)){return false;}}b[row]=col;return true;}/** * 打印结果 */private static void printResult(){System.out.print(times+++"： ");for(int i=0;i<8;i++){System.out.print(b[i]+" ");}System.out.println(" ");}}