首页 > 代码库 > 八皇后问题 （全排列的运用）
八皇后问题 （全排列的运用）
8皇后问题相信大家都听说过：
在一个8*8格子的矩形里，放上8个皇后，如果在同一直线上（横，竖，(左右)斜线）存在两个皇后，他们就互相攻击了，现在要我们来求一共有多少种摆法，让他们相安无事！
一般的解法都是回溯法，一步一步的试探，不行就返回再来，这样做时间效率很低，2的64次方，
今天我介绍的是全排列法解此题：
我们可以把这个问题抽象出来：
1.序号为0-7的8个皇后；
2.放置到序号为0-7的8个箱子里；
3.同时所有皇后的序号与箱子序号的和各不相同；
4.所有皇后的序号与箱子序号的差也各不相同。
前两条相当于横方向和竖方向都是唯一的，（用全排列实现）（用递归实现的全排列）
后两天相当于（左右）斜线上也都唯一的，（直接过滤）
嗯，写到这里大家应该明白所以然了吧。
代码如下
import java.util.ArrayList;import java.util.HashSet;import java.util.List;import java.util.Set;public class Demo1 { public static List<List<Integer>>list = new ArrayList<List<Integer>>(); private static void sort(List<Integer> datas, List<Integer> target) { if (datas.size()==0) { Set<Integer> s1 = new HashSet<Integer>(); Set<Integer> s2 = new HashSet<Integer>(); for(int i=0;i<target.size();i++){ s1.add(i+target.get(i)); s2.add(i-target.get(i)); } if(s1.size()==8&&s2.size()==8){ list.add(target); } return; } for (int i = 0; i < datas.size(); i++) { List<Integer> newDatas = new ArrayList<Integer>(datas); List<Integer> newTarget = new ArrayList<Integer>(target); newTarget.add(newDatas.get(i)); newDatas.remove(i); sort(newDatas, newTarget); } } public static void main(String[] args) { List<Integer> li = new ArrayList<Integer>(); for(int i=0;i<8;i++){ li.add(i); } sort(li, new ArrayList<Integer>()); System.out.println(list.size()); } }
结果大家都知道：92
我没计算时间，因为结果是立刻蹦出来的，我也用此方法计算了“10皇后”的问题，只需要4秒！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。