八皇后问题的代码实现(回溯法找到所有可行摆放方法,java语言)
*问题表述为:(表述来自百度百科)
*在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转,和对角线对称变换的摆法看成一类,共有42类。计算机发明后,有多种计算机语言可以编程解决此问题.
代码实现
/** * className:EightQueen * * @author:zjl * @version:0.1 * @date:2020/8/1118:34 * @since:jdk1.8 */public class EightQueen { static int num = 0; //记录打印次数,即寻找到的第num种摆法 //测试 public static void main(String[] args) { int[] chessboard = creatChessboard(); searchRoute(chessboard,0); } //创建棋盘 /** * 利用一维数组表示棋盘 * chessboard[5] = 6 表示棋盘的第五行的第六列 * @return */ public static int[] creatChessboard() { int[] chessboard = new int[8]; return chessboard; } /** * 将一维数组表示的棋盘还原为8*8棋盘并输出 * @param chessboard */ public static void printChessboard(int[] chessboard) { num++; System.out.println("第"+num+"种摆法"); for (int p = 0; p < 8; p++) { for (int q = 0; q < 8; q++) { if(chessboard[p]==q){ System.out.print("★ "); continue; } System.out.print("○ "); } System.out.println(); } System.out.println(); System.out.println("-------------------------------------"); } /** * 判断放置皇后的位置是否与之前已经放置过皇后的位置是否相互会攻击 * @param chessboard * @param i * @return 会攻击 false 不会攻击 true */ public static boolean JudgmentConflic(int[] chessboard, int i) { for(int j=0;j<i;j++){ if(chessboard[i]==chessboard[j]) return false; if(Math.abs(i-j)==Math.abs(chessboard[i]-chessboard[j])) return false; } return true; } /** * 递归规划皇后放置位置 * @param chessboard * @param i */ public static void searchRoute(int[] chessboard, int i){ if(i==8){ //数组最后一个位置已经赋值,表示8个位置全部找到 printChessboard(chessboard);//打印棋盘 return; } for (int j = 0; j < 8; j++) { //从每行第一个位置开始寻找 chessboard[i]=j; if(JudgmentConflic(chessboard,i)){ //该位置不会发生攻击,寻找下一行可行位置 searchRoute(chessboard,i+1); } } }}
测试结果(结果中共92种摆法这里展示部分摆法)