赞
踩
八皇后问题介绍
在8x8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后不能处于同一行、同一列或同一斜线上,问有多少种摆法(92种)
八皇后问题思路分析
1)第一个皇后先放在第一行第一列
2)第二个皇后放在第二行第一列,然后判断是否可以,如果不可以,则放在第二列、第三列、依次把所有的列都放完,找到一个合适的位置
3)继续放第三个皇后,重复步骤(2)······直到第八个皇后也能放在一个不冲突的位置时,便是找到了一种方法
4)当得到一种正确方法时,在栈回退到上一个栈时,就会开始回溯,即:将第一个皇后,放到第一列的所有正确方法全部得到
5)然后第一个皇后放在第二列,后面继续循环执行1,2,3,4的步骤
说明
1.每一行都应要有一个皇后
2.创建一个一维数组array[8]来解决八皇后问题
比如:array[i]=value,表示第i+1个皇后,放在第i+1行的第value+1列
代码实现
//定义一个数组array,保存皇后放置位置的结果 int[] array = new int[8]; static int count=0;//静态成员变量存在堆内存中,每个方法都可以给它赋值并保存 //方法:放置第n个皇后 private void check(int n) { if (n == array.length) { //表示八个皇后已经放置好 //打印解决八皇后问题的解法 print(); return; } //依次放入皇后,并判断是否冲突 for (int i = 0; i < array.length; i++) { //先把当前皇后n放到该行的第一列 array[n] = i; //判断当放置第n个皇后到第i+1列时,是否冲突 if (judge(n)) { //如果不冲突,接着放第n+1个皇后,即递归 check(n + 1); } //如果冲突,该皇后就移到下一列,再判断是否可以 } } //查看当放置第n个皇后,检测该皇后是否和前面的皇后发生冲突 private boolean judge(int n){ for(int i=0;i<n;i++){ //1.因为n每次都在递增,n代表第n+1个皇后位于第n+1行,因此不需要判断是否在同一行上 //2.array[i]==array[n] 判断第n个皇后是否和前面的n-1个皇后在同一列 //Math.abs方法是求两个值相减的绝对值 //下面式子是求两个皇后所在位置的斜率绝对值是否为1 如果为1,则在同一条斜线上 //3.Math.abs(n-i)==Math.abs(array[n]-array[i]) 判断第n个皇后是否和第i个皇后是否在同一斜线上 if(array[i]==array[n]||Math.abs(n-i)==Math.abs(array[n]-array[i])){ return false; } } return true; } //方法 将皇后摆放的位置输出 private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print((array[i] + 1) + " "); } System.out.println(); } }
测试
//测试
public static void main(String[] args) {
Queen8 q=new Queen8();
q.check(0);
System.out.println("一共有"+count+"中解法");//92种
}
八皇后问题一些解法如下
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。