数据结构之8皇后问题

在看这篇博文之前，大家可以先玩玩8皇后游戏，在此附上游戏连接点此开始游戏之旅！

8皇后游戏规则是任意在8*8的棋盘上摆放8个皇后，并且这8个皇后之间不能相互攻击（即任意两个皇后不能在同一行，同一列，同一条斜线上）。问：总共有多少种摆放？总共进行了多少次冲突检查？

在玩游戏的时候明显感觉大脑不足，写个代码帮我找一些摆放方式吧！

实现是利用递归，一维数组实现。8*8棋盘本应该用一个二维数组存放，但是由于8皇后问题的特殊性，选择一个长度为8的一维数组也可达到此效果。用数组的下标表示第i+1个皇后，每个皇后放在单独的一行（第一个皇后在第一行，第二个在第二行.....），对应的值代表这个皇后放置在第j+1列。这样就可实现了，下面来看看代码。

public class Queue8 {static int count;//总共有几种排发static int judgeCount;//总共判断了多少次//总共有多少个皇后int max = 8;//用一个一维数组即可存储，数组下标表示第几个皇后，对应的值表示这个皇后放到了第几列int[] array = new int[max];public static void main(String[] args) {Queue8 queue8 = new Queue8();queue8.check(0);System.out.println("总共有"+count+"种方式");System.out.println("冲突判断了"+judgeCount+"次");}/*** 检查第几个皇后应该放在哪个位置，每一个皇后都从第一列开始放，冲突后到下一列* @param n*/private void check(int n){if (n == max){//n==max时已经是第9个皇后，前8个皇后已经放置好了print();return;}for (int i = 0; i < max; i++) {//每个皇后都先放到第一列array[n] = i;//判断是不是冲突if (judge(n)){//不冲突，继续下一个皇后check(n+1);}//冲突则放到下一列}}private boolean judge(int n) {judgeCount++;//判断第n个皇后与前几个皇后位置是否冲突，在同一行，同一列，同一条斜线上即为冲突for (int i = 0; i < n; i++) {if (array[i] == array[n] || Math.abs(i-n) == Math.abs(array[i]-array[n])){//冲突return false;}}return true;}private void print(){count++;for (int i = 0; i < max; i++) {System.out.print(array[i]+" ");}System.out.println();}
}

附上程序跑出的结果：

0 4 7 5 2 6 1 3 
0 5 7 2 6 3 1 4 
0 6 3 5 7 1 4 2 
0 6 4 7 1 3 5 2 
1 3 5 7 2 0 6 4 
1 4 6 0 2 7 5 3 
1 4 6 3 0 7 5 2 
1 5 0 6 3 7 2 4 
1 5 7 2 0 3 6 4 
1 6 2 5 7 4 0 3 
1 6 4 7 0 3 5 2 
1 7 5 0 2 4 6 3 
2 0 6 4 7 1 3 5 
2 4 1 7 0 6 3 5 
2 4 1 7 5 3 6 0 
2 4 6 0 3 1 7 5 
2 4 7 3 0 6 1 5 
2 5 1 4 7 0 6 3 
2 5 1 6 0 3 7 4 
2 5 1 6 4 0 7 3 
2 5 3 0 7 4 6 1 
2 5 3 1 7 4 6 0 
2 5 7 0 3 6 4 1 
2 5 7 0 4 6 1 3 
2 5 7 1 3 0 6 4 
2 6 1 7 4 0 3 5 
2 6 1 7 5 3 0 4 
2 7 3 6 0 5 1 4 
3 0 4 7 1 6 2 5 
3 0 4 7 5 2 6 1 
3 1 4 7 5 0 2 6 
3 1 6 2 5 7 0 4 
3 1 6 2 5 7 4 0 
3 1 6 4 0 7 5 2 
3 1 7 4 6 0 2 5 
3 1 7 5 0 2 4 6 
3 5 0 4 1 7 2 6 
3 5 7 1 6 0 2 4 
3 5 7 2 0 6 4 1 
3 6 0 7 4 1 5 2 
3 6 2 7 1 4 0 5 
3 6 4 1 5 0 2 7 
3 6 4 2 0 5 7 1 
3 7 0 2 5 1 6 4 
3 7 0 4 6 1 5 2 
3 7 4 2 0 6 1 5 
4 0 3 5 7 1 6 2 
4 0 7 3 1 6 2 5 
4 0 7 5 2 6 1 3 
4 1 3 5 7 2 0 6 
4 1 3 6 2 7 5 0 
4 1 5 0 6 3 7 2 
4 1 7 0 3 6 2 5 
4 2 0 5 7 1 3 6 
4 2 0 6 1 7 5 3 
4 2 7 3 6 0 5 1 
4 6 0 2 7 5 3 1 
4 6 0 3 1 7 5 2 
4 6 1 3 7 0 2 5 
4 6 1 5 2 0 3 7 
4 6 1 5 2 0 7 3 
4 6 3 0 2 7 5 1 
4 7 3 0 2 5 1 6 
4 7 3 0 6 1 5 2 
5 0 4 1 7 2 6 3 
5 1 6 0 2 4 7 3 
5 1 6 0 3 7 4 2 
5 2 0 6 4 7 1 3 
5 2 0 7 3 1 6 4 
5 2 0 7 4 1 3 6 
5 2 4 6 0 3 1 7 
5 2 4 7 0 3 1 6 
5 2 6 1 3 7 0 4 
5 2 6 1 7 4 0 3 
5 2 6 3 0 7 1 4 
5 3 0 4 7 1 6 2 
5 3 1 7 4 6 0 2 
5 3 6 0 2 4 1 7 
5 3 6 0 7 1 4 2 
5 7 1 3 0 6 4 2 
6 0 2 7 5 3 1 4 
6 1 3 0 7 4 2 5 
6 1 5 2 0 3 7 4 
6 2 0 5 7 4 1 3 
6 2 7 1 4 0 5 3 
6 3 1 4 7 0 2 5 
6 3 1 7 5 0 2 4 
6 4 2 0 5 7 1 3 
7 1 3 0 6 4 2 5 
7 1 4 2 0 6 3 5 
7 2 0 5 1 4 6 3 
7 3 0 2 5 1 6 4 
总共有92种方式
冲突判断了15720次

用第一个结果完了一把游戏，结果如下图：

欢迎留言交流哦。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！