营销型网站建设的步骤流程是什么,做外贸首先要做网站,做网站公司 营销,新建网站怎么做关键词什么是八皇后问题#xff1f; 八皇后问题是一个古老而著名的问题#xff0c;它是回溯算法的典型案例。其问题的内容是#xff1a;在8x8格的国际棋盘上摆放八个皇后#xff0c;使其不能互相攻击#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上#xff0c;…什么是八皇后问题 八皇后问题是一个古老而著名的问题它是回溯算法的典型案例。其问题的内容是在8x8格的国际棋盘上摆放八个皇后使其不能互相攻击即任意两个皇后都不能处于同一行、同一列或同一斜线上问共有多少种摆法。 八皇后问题算法思路分析 1、先把第一个皇后放在第一行第一列 2、第二个皇后放在第二行第一列然后判断是否可行如果可以继续放在第二列、第三列依次把所有列都放完找到一个合适的 3、继续放第三个皇后还是从第一列、第二列…直到第八个皇后也能放在一个不冲突的位置上这样就找到了一个正确的解 4、当得到一个正确解时在栈上回退到上一个栈就会开始回溯即将第一个皇后放在第一列的所有正确的解都全部得到了 5、然后继续第一个皇后放第二列后面继续循环执行1、2、3、4的步骤 代码体现
public class EightQueens {//定义一个queens表示皇后的数量int queens 8;//定义数组array用于保存皇后位置摆放的结果其中数组的下标表示排数组下标对应的值表示列int[] array new int[queens];static int count 0;//用于记录最终存在多少种解法static int judgeCount 0;//用于记录判断冲突的次数public static void main(String[] args) {new EightQueens().check(0);System.out.printf(一共有%d种解法\n, count);//一共有92种解法System.out.printf(判断冲突的次数共%d次, judgeCount);//判断冲突的次数共15720次}/*** 该方法用于放置第n个皇后** param n 表示第n个皇后*/private void check(int n) {if (n queens) { //此时n8也就代表8个皇后都已经放好了count;print();return;}//依次放入皇后判断是否发生冲突for (int i 0; i queens; i) {//先把当前这个皇后放到该行的第一列array[n] i;//判断当放置第n个皇后到第i列时是否发生冲突if (judge(n)) {//不冲突接着放n1个皇后即开始递归check(n 1);}//如果发生冲突就继续执行array[n]i,即将第n个皇后放在本行后移的一个位置}}/*** 用于检测放置第n个皇后时是否和前面已经摆放好的皇后发生冲突** param n 表示第n个皇后* return*/private boolean judge(int n) {judgeCount;for (int i 0; i n; i) {//array[i] array[n]判断第n个皇后是否和前面的n-1个皇后在同一列//Math.abs(n - i) Math.abs(array[n] - array[i])判断第n个皇后是否和前面的n-1个皇后在同一对角线if (array[i] array[n] || Math.abs(n - i) Math.abs(array[n] - array[i])) {return false;}}return true;}/*** 用于输出皇后摆放好之后的位置*/private void print() {for (int i 0; i array.length; i) {System.out.print(array[i] \t);}System.out.println();}
}注
通过最终的结果看到了判断冲突的次数一共达到了1.5万余次相对而言效率不够高所以上诉代码后期还需要继续进行优化
