×

关注微信公众号

免备案网站空间虚拟主机双线空间域名查询PS数码后期
photoshop互助课堂数百G视频教程下载随时随地聆听大师开讲/课堂酷素材!视频教程打包下手绘教程
咔咔摄影抠图教程路径专辑photoshop cs3视频教程 
查看: 2429|回复: 20

回溯法解八皇后问题@张志晨as3教程73

[复制链接]

该用户从未签到

发表于 2013-10-27 16:45:25 | 显示全部楼层 |阅读模式
本帖最后由 dqxxx 于 2013-10-27 19:49 编辑

回溯法解八皇后问题@张志晨as3教程73

  在网上一搜,居然没有AS3的关于八皇后的算法代码,于是根据其它语言的思想写了自己的代码,可以说也是个首创!

  八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。


  八皇后问题解法大全:

  1. //var allanswer="

  2. 15863724,16837425,17468253,17582463,24683175,25713864,25741863,26174835,26831475,27368514,27581463,28613574,31758246,35281746,35286471,35714286,35841726,36258174,36271485,36275184,36418572,36428571,36814752,36815724,36824175,37285146,37286415,38471625,41582736,41586372,42586137,42736815,42736851,42751863,42857136,42861357,46152837,46827135,46831752,47185263,47382516,47526138,47531682,48136275,48157263,48531726,51468273,51842736,51863724,52468317,52473861,52617483,52814736,53168247,53172864,53847162,57138642,57142863,57248136,57263148,57263184,57413862,58413627,58417263,61528374,62713584,62714853,63175824,63184275,63185247,63571428,63581427,63724815,63728514,63741825,64158273,64285713,64713528,64718253,68241753,71386425,72418536,72631485,73168524,73825164,74258136,74286135,75316824,82417536,82531746,83162574,84136275"//92种



  3. //回溯法代码:

  4. function queen() :Array{
  5. var answers:Array=[];//记录方案
  6. var queencol:Array=[];//记录8个皇后所占用的列号 数值型
  7. //因为是按行放置,故不存在行的冲突
  8. var col:Array=[];//列安全标志 布尔型
  9. var diagonal:Array=[];//对角线安全标志 布尔型
  10. var undiagonal:Array=[];//反对角线安全标志 布尔型
  11. for (var i:int= 0; i < 16; i++) {
  12.   //所有列、线为安全
  13.   col[i]=diagonal[i]=undiagonal[i]=true;
  14. }
  15. solve(1);//开始运行-------------------------------------
  16. return (answers);//返回值


  17. //函数内封闭的子函数:
  18. function solve(i:int) {
  19.   for (var j:int = 0; j < 8; j++) {
  20.    if (col[j]&&diagonal[i-j+7]&&undiagonal[i+j]) {
  21.     //表示第i行第j列是安全的可以放皇后
  22.     queencol[i-1]=j+1;
  23.     //修改安全标志
  24.     col[j]=diagonal[i-j+7]=undiagonal[i+j]=false;
  25.     //判断是否放完8个皇后   
  26.     if (i < 8) {
  27.      solve(i + 1);//放下一个
  28.     } else {
  29.      //已经放完8个皇后
  30.      answers.push(queencol.join(""));
  31.     }
  32.     //修改安全标志,回溯
  33.     col[j]=diagonal[i-j+7]=undiagonal[i+j]=true;
  34.    }
  35.   }
  36. }
  37. }



  38. //执行主函数:

  39. trace(queen());
复制代码
下图的答案是:31758246




本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?[免费注册]

x

该用户从未签到

发表于 2017-12-24 11:42:57 | 显示全部楼层
楼主是超人
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2017-12-24 10:47:43 | 显示全部楼层
说的非常好
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2017-12-24 10:59:42 | 显示全部楼层
果断收藏了
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2017-12-24 11:01:20 | 显示全部楼层
教程网我挺你
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2017-12-24 11:11:29 | 显示全部楼层
楼主我支持你
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 19:51:23 | 显示全部楼层
楼主是超人
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 19:20:45 | 显示全部楼层
顶顶多好
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 19:44:46 | 显示全部楼层
很好哦。。。
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 19:32:59 | 显示全部楼层
果断收藏了
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 19:05:44 | 显示全部楼层
楼主我支持你
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 20:49:19 | 显示全部楼层
楼主是超人
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 20:05:04 | 显示全部楼层
顶顶多好
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 20:15:07 | 显示全部楼层
难得一见的好帖
回复 支持 反对

使用道具 举报

该用户从未签到

发表于 2018-9-24 20:46:32 | 显示全部楼层
说的非常好
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | [免费注册]

本版积分规则