脚本宝典收集整理的这篇文章主要介绍了递归解决八皇后问题，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

递归解决八皇后问题

√八皇后问题说明

• 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。

• 该问题是国际西洋祺棋手马克斯贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击

• 即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

√八皇后思路分析

1)第一个皇后先放第一行第一列 arr[8] = {0,0}

2)第二个皇后放在第二行第一列、然后判断是否OK, 如果不OK,继续放在第二列、第三列、依次把所有列都放完，找到一个合适

3)继续第三个皇后，还是第一列、第二列.直到第8个皇后也能放 在一个不冲突的位置，算是找到了一个正确解

4)当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即 将第一个皇后，放到第一列的所有正确解，全部得到.

5)然后回头继续第一个皇后放第二列，后面继续循环执行1,2,3,4的 步骤

说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通 过算法，用一个一维数组即可解决问题

例如 : arr[8]={0,4,7,5,2,6,1,3} ,我们可以使用这样的一维数组来解决问题, 例如该数组 就是将皇后摆放到 ,第一行的第一列 ,第二行的第五列 .........

代码示例(通过视频参考,对着敲出来的)

public class Eight_questions {    public static void main(String[] args) {​        checkerboard c1 = new checkerboard();        c1.check(8,0);​    }}​class checkerboard {    int [] arr= new int[8];    int count = 0;    public void check(int n, int index) {        if (n == index){            for (int i = 0;i < n ;i++){                System.out.print(arr[i]+" ");            }            count+=1;​            System.out.println();            System.out.println("第"+count+"种摆放");​        }else {            for (int i = 0;i < n ;i++){                //此时的n代表列                arr[index] = i;                //第index行第i列                if (judge(index)){                    check(n,index + 1);                }            }        }​​    }​    public boolean judge(int index){        for (int i=0;i<index;i++){            if (arr[i]==arr[index]||Math.abs(index - i)==Math.abs(arr[index]-arr[i])){                return false;            }        }        return true;        //如果不起冲突就返回true    }​}

实际分析一下代码

class checkerboard

创建一个类 ,用于实现八皇后的棋盘填充

 int [] arr= new int[8]; //在类中创建一个全局变量数组,因为下面有两个方法需要使用到 public void check(int n, int index) { //创建方法check,传参的参数 n为皇后棋子的个数,index表示从第几行开始        if (n == index){        //如果棋子个数和和行数一致表示皇后已经全部下完            for (int i = 0;i < n ;i++){            //循环行数对数组进行遍历,然后将数组的内容打印出来                System.out.print(arr[i]+" ");            }            count+=1;            System.out.println();            System.out.println("第"+count+"种摆放");        }

//如果数组没有完成填充(也就是八皇后的棋子没有下完)else {       for (int i = 0;i < n ;i++)       //循环       {           //此时的n代表列           arr[index] = i;           //循环填充数组的内容           //第index行第i列           if (judge(index)){           //接收judge方法来判断这个位置是否符合规范,若符合规范就执行下面的递归           check(n,index + 1);           //递归调用方法,每次添加都会增加一次行数           }       }    }

public boolean judge(int index){//这个方法主要用于判断皇后放置是否合法,接收参数index表示每行进行判断        for (int i=0;i<index;i++){        //循环            if (arr[i]==arr[index]||Math.abs(index - i)==Math.abs(arr[index]-arr[i])){            //判断数组的上下两行放置的列是否一致(如若一致表示皇后在同一列触犯了规则)            //判断数组的上下两行,通过两个位置横纵坐标互减如果数值一致就说明在一条斜线之上            //同时由于不可能同行因此不判断同行的情况                return false;                //如果不符合判断就返回false            }        }        return true;        //如果符合规范就返回true    }

脚本宝典总结

以上是脚本宝典为你收集整理的递归解决八皇后问题全部内容，希望文章能够帮你解决递归解决八皇后问题所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。