设为首页收藏本站淘宝杂货铺

从F到0 - From F to 0

 找回密码
 注册已关闭
搜索
查看: 15028|回复: 25
收起左侧

[PHP/ASP/JSP] 3D立体数字滑块推盘自动搜索求解还原算法V1.0版

[复制链接]
发表于 2018-1-24 15:17:24 | 显示全部楼层 |阅读模式
经过了N天的研究,终于搞出了算法,步数少的也得几分钟,多的几亿年不清楚,占内存cpu非常高,也可能由于内存溢出等问题解不出来,有条件的建议挂到天河二号上运行,里面有判断是否可解的源码,可能会存在一些bug,大神可以拿去继续改进。
  1. <?php
  2. ob_end_clean();
  3. ob_implicit_flush(1);
  4. set_time_limit(3600);
  5. ini_set('memory_limit','1024M');
  6. ignore_user_abort(0);
  7. date_default_timezone_set("Asia/Shanghai");

  8. $xyd = array( //拼图板移动方向与0(空白)交换坐标数据,严禁修改否则数字会跳格或无法正常移动。
  9.         0x04,0x10,0x01,0x10,0x05,0x10,0x02,0x00,0x06,0x10,0x03,0x01,0x07,0x10,0x10,0x02,
  10.         0x08,0x00,0x05,0x10,0x09,0x01,0x06,0x04,0x0A,0x02,0x07,0x05,0x0B,0x03,0x10,0x06,
  11.         0x0C,0x04,0x09,0x10,0x0D,0x05,0x0A,0x08,0x0E,0x06,0x0B,0x09,0x0F,0x07,0x10,0x0A,
  12.         0x10,0x08,0x0D,0x10,0x10,0x09,0x0E,0x0C,0x10,0x0A,0x0F,0x0D,0x10,0x0B,0x10,0x0E
  13.         );


  14. $l1 = array(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15);                //推盘层1(最里层)
  15. $l2 = array(16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31);        //推盘层2
  16. $l3 = array(32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47);        //推盘层3
  17. $l4 = array(48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63);        //推盘层4(最外层)

  18. $init_lay = range(0,63); //还原后的拼图 0~63
  19. //推盘层奇偶位置,核验是否可解必须用的到
  20. $o0 = array(0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0);
  21. $o1 = array(1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1);

  22. $lay_map = array(); //拼图地图 多维数组 第二维固定64字节
  23. $mov_dir = array(); //移动轨迹 保存着到指定地图的移动轨迹,文本整数保存

  24. $err_mov = array(); //每走过或失败一次指定的二进制位置为1,一但为1则不会进入搜索,只有6个二进制位用的到。

  25. //------------------------3D推盘驱动程序------------------------



  26. function get_adj_coo($zero_adj,$mov_dir){                 //获取相邻坐标
  27.         global $xyd;
  28.         return $xyd[$zero_adj*4+$mov_dir-1];
  29. }


  30. function get_0_lay(){ //获取0(空白)所在的层数 返回1~4
  31.         global $l1,$l2,$l3,$l4;
  32.         for($add=0;$add<16;$add++){
  33.                 if($l1[$add] == 0)return 1;
  34.                 if($l2[$add] == 0)return 2;
  35.                 if($l3[$add] == 0)return 3;
  36.                 if($l4[$add] == 0)return 4;
  37.         }
  38.         return 0; //不可能 除非没有0
  39. }


  40. function get_0_pla(){ //获取0(空白)的平面坐标 返回0~15
  41.         global $l1,$l2,$l3,$l4;
  42.         $lay=get_0_lay(); //获取0所在的层数
  43.         for($add=0;$add<16;$add++){
  44.                         if($lay == 1 && $l1[$add] == 0){
  45.                                 return $add;
  46.                         }elseif($lay == 2 && $l2[$add] == 0){
  47.                                 return $add;
  48.                         }elseif($lay == 3 && $l3[$add] == 0){
  49.                                 return $add;
  50.                         }elseif($lay == 4 && $l4[$add] == 0){
  51.                                 return $add;
  52.                         }
  53.                 }
  54.         return -1; //不可能
  55. }


  56. function pec($s,$a,$b){ //平面交换数字位置 层数:1~4 坐标A 坐标B
  57.         global $l1,$l2,$l3,$l4;
  58.         $ad=0;$bd=0;
  59.         if($a > 15 || $b > 15) return 0;
  60.                 if($s == 1){$ad=$l1[$a];$bd=$l1[$b];$l1[$a]=$bd;$l1[$b]=$ad;return 1;}
  61.                 if($s == 2){$ad=$l2[$a];$bd=$l2[$b];$l2[$a]=$bd;$l2[$b]=$ad;return 1;}
  62.                 if($s == 3){$ad=$l3[$a];$bd=$l3[$b];$l3[$a]=$bd;$l3[$b]=$ad;return 1;}
  63.                 if($s == 4){$ad=$l4[$a];$bd=$l4[$b];$l4[$a]=$bd;$l4[$b]=$ad;return 1;}
  64.         return 0;
  65. }


  66. function up_mov(){ //拼图上移
  67.         if(!is_mov(0)) return 0;
  68.         $lay0=get_0_lay(); //获取0的坐标所在层数
  69.         $pla0=get_0_pla(); //获取0的平面坐标
  70.         $adj=get_adj_coo($pla0,1); //获取相邻坐标
  71.         pec($lay0,$pla0,$adj); //平面交换数字位置
  72.         return 1;
  73. }


  74. function down_mov(){ //拼图下移
  75.         if(!is_mov(1)) return 0;
  76.         $lay0=get_0_lay(); //获取0的坐标所在层数
  77.         $pla0=get_0_pla(); //获取0的平面坐标
  78.         $adj=get_adj_coo($pla0,2); //获取相邻坐标
  79.         pec($lay0,$pla0,$adj); //平面交换数字位置
  80.         return 1;
  81. }

  82. function left_mov(){ //拼图左移
  83.         if(!is_mov(2)) return 0;
  84.         $lay0=get_0_lay(); //获取0的坐标所在层数
  85.         $pla0=get_0_pla(); //获取0的平面坐标
  86.         $adj=get_adj_coo($pla0,3); //获取相邻坐标
  87.         pec($lay0,$pla0,$adj); //平面交换数字位置
  88.         return 1;
  89. }

  90. function right_mov(){ //拼图右移
  91.         if(!is_mov(3)) return 0;
  92.         $lay0=get_0_lay(); //获取0的坐标所在层数
  93.         $pla0=get_0_pla(); //获取0的平面坐标
  94.         $adj=get_adj_coo($pla0,4); //获取相邻坐标
  95.         pec($lay0,$pla0,$adj); //平面交换数字位置
  96.         return 1;
  97. }

  98. function in_mov(){ //拼图里移
  99. global $l1,$l2,$l3,$l4;
  100.         if(!is_mov(4)) return 0;
  101.         $lay0=get_0_lay(); //获取0的坐标所在层数
  102.         $pla0=get_0_pla(); //获取0的平面坐标
  103.                 if($lay0 < 4){
  104.                         if($lay0 == 3){$l3[$pla0]=$l4[$pla0];$l4[$pla0]=0;}
  105.                         if($lay0 == 2){$l2[$pla0]=$l3[$pla0];$l3[$pla0]=0;}
  106.                         if($lay0 == 1){$l1[$pla0]=$l2[$pla0];$l2[$pla0]=0;}
  107.                 }
  108.         return 1;

  109. }

  110. function out_mov(){ //拼图外移
  111. global $l1,$l2,$l3,$l4;
  112.         if(!is_mov(5)) return 0;
  113.         $lay0=get_0_lay(); //获取0的坐标所在层数
  114.         $pla0=get_0_pla(); //获取0的平面坐标
  115.                 if($lay0 > 1){
  116.                         if($lay0 == 4){$l4[$pla0]=$l3[$pla0];$l3[$pla0]=0;}
  117.                         if($lay0 == 3){$l3[$pla0]=$l2[$pla0];$l2[$pla0]=0;}
  118.                         if($lay0 == 2){$l2[$pla0]=$l1[$pla0];$l1[$pla0]=0;}
  119.                 }
  120.         return 1;
  121. }


  122. function is_mov($direction){ //可否往指定方向移动
  123.                 $pla = get_0_pla();
  124.                 switch($direction){        //判断移动方向
  125.                         case 0:$return = get_adj_coo($pla,1) <= 15;break;        //可否上移
  126.                         case 1:$return = get_adj_coo($pla,2) <= 15;break;        //可否下移
  127.                         case 2:$return = get_adj_coo($pla,3) <= 15;break;        //可否左移
  128.                         case 3:$return = get_adj_coo($pla,4) <= 15;break;        //可否右移
  129.                         case 4:$return = get_0_lay() < 4;break;                                //可否里移
  130.                         case 5:$return = get_0_lay() > 1;break;                                //可否外移
  131.                         default:$return = -1;break;                                        //无效方向
  132.                 }
  133.         return $return;                //返回结果 1允许移动 0禁止移动 -1无效方向
  134. }
  135. function import_lay($layout){ //导入拼图(地图) 接收64字节数据
  136.         global $l1,$l2,$l3,$l4;
  137.         $lay4 = array_chunk($layout,16);
  138.         $l1=$lay4[0];$l2=$lay4[1];
  139.         $l3=$lay4[2];$l4=$lay4[3];
  140. }

  141. //------------------------计算拼图是否可解------------------------
  142. function inversion($number){        //计算逆序数 需接收单维数组整数
  143.         $size = sizeof($number); //数组成员数
  144.         $return = 0;
  145.                 for($add=0;$add<$size;$add++){
  146.                         $number2 = $number[$add]; //当前数
  147.                                 for($add2=$add;$add2<$size;$add2++){
  148.                                 if($number[$add2] < $number2) $return++;
  149.                         }
  150.                 }
  151.         return $return;
  152. }

  153. function get_0_ode(){ //取0(空白)所在的奇偶位置
  154.         global $o0,$o1;
  155.         $pla = get_0_pla(); //坐标
  156.                 switch(get_0_lay()){ //判断在第几层
  157.                         case 1:$return = $o0[$pla];break;
  158.                         case 2:$return = $o1[$pla];break;
  159.                         case 3:$return = $o0[$pla];break;
  160.                         case 4:$return = $o1[$pla];break;
  161.                         default:$return = -1;break; //不可能
  162.                 }

  163.         return $return;

  164. }
  165. function lay_merge(){ //拼图数组合并成一个,合成以后就是64字节的地图
  166.         global $l1,$l2,$l3,$l4;
  167.         return array_merge_recursive($l1,$l2,$l3,$l4);
  168. }

  169. function is_solvable(){ //拼图是否可解
  170.         return ((inversion(lay_merge())&1) == 1) == get_0_ode();

  171. }


  172. //------------------------计算拼图还原顺序------------------------
  173. function search_map($search_map){ //搜索当前地图是否已经存在于表中 存在返回位置 不存在返回-1
  174.         global $lay_map;
  175.         if(!in_array($search_map,$lay_map)) return -1; //不存在 返回-1
  176.                 return array_search($search_map,$lay_map); //存在返回位置 0开头
  177.         
  178. }

  179. function add_map($direction,$add){ //将地图加入表中 参数1 方向 参数2 计数
  180.         global $lay_map,$mov_dir,$err_mov;
  181.         $map = lay_merge();
  182.         //echo $direction." ".$add."<br>";
  183.                 if(search_map($map) != -1) return 0;  //已存在 不加入
  184.                 array_push($lay_map,$map); //加入拼图
  185.                 $add2 = sizeof($lay_map); //获取拼图记录中有多少表
  186.                         array_push($mov_dir,$mov_dir[$add].$direction); //加入移动轨迹                        
  187.                         array_push($err_mov,0);
  188.                         $err_mov[$add] |= (1 << $direction);

  189.                 return 1;

  190. }

  191. function solve_ok(){ //还原是否成功
  192.         global $init_lay; //还原成功后的拼图(地图)
  193.         $result = search_map($init_lay); //查找当前地图是否存在于表中
  194.         if($result == -1) return -1; //没搜到 不成功
  195.         return $result; //成功 返回位置 0开头
  196. }

  197. function rmd(){ //读还原轨迹
  198.         global $mov_dir;
  199.         return $mov_dir[solve_ok()]; //读移动轨迹
  200. }


  201. function n2d($number){ //数字移动轨迹翻译成汉字
  202.         $n = $number;
  203.                 $n = str_replace('0',"上",$n);
  204.                 $n = str_replace('1',"下",$n);
  205.                 $n = str_replace('2',"左",$n);
  206.                 $n = str_replace('3',"右",$n);
  207.                 $n = str_replace('4',"里",$n);
  208.                 $n = str_replace('5',"外",$n);
  209.         return $n;

  210. }



  211. function solve(){ //还原拼图
  212.         global $lay_map,$mov_dir,$err_mov,$init_lay;
  213.         $add3=0;$old=0;
  214.         $add4=0;
  215.         if(!is_solvable()) return "E1"; //不可解
  216.         if($init_lay == lay_merge()) return "E2"; //前后一致,不需要解
  217.                 $lay_map = array(lay_merge()); //地图,多维数组,每个地图64字节。
  218.                 $mov_dir = array(''); //轨迹,以数字的方式保存。
  219.                 $err_mov = array(0);
  220.                 $min_inv = 10000; //最小逆序数
  221.                 $old_inv = 0;  //旧逆序数
  222.                         while(1){ //死循环,解成功了就会退出。
  223.                                 $end = sizeof($lay_map); //有多少个地图等待遍历
  224.                                 //echo "----------------------------------------------------------------<br>";
  225.                                 //echo "移动轨迹:{$mov_dir[sizeof($mov_dir)-1]}<br>";
  226.                         //$old = 0;
  227.                                 for($add=$old;$add<$end;$add++){
  228.                                         $inv = inversion(lay_merge());
  229.                                         $min_inv = min($min_inv,$inv);
  230.                                                 $add4++;
  231.                                                         if($min_inv < $old_inv || $add4 >=100){
  232.                                                         $add4=0;
  233.                                                         $tmp = n2d($mov_dir[sizeof($mov_dir)-1]);
  234.                                 echo "范围:{$add}/{$end} 当前逆序数:{$inv} 最低逆序数:{$min_inv}|{$tmp}<br>";
  235.                                 /*
  236.                                 $mdir = lay_merge();
  237.                                 $k="";
  238.                                 for($add5=0;$add5<64;$add5++) $k.=$mdir[$add5].",";
  239.                                 echo "{$k}<br>";
  240.                                         import_lay($lay_map[sizeof($lay_map)-1]);
  241.                                         $wz = search_map($lay_map[sizeof($lay_map)-1]);
  242.                                         return $mov_dir[$wz];
  243.                                 */
  244.                                 }

  245.                                 $old_inv = $min_inv; //保存旧逆序数



  246.                                         if($err_mov[$add] == 63){ //当前地图中六个方向二进制位都标记为1,都不可走不再进入搜索
  247.                                                 
  248.                                                 //$emn++;
  249.                                                 //unset($lay_map[$add]);
  250.                                                 //unset($mov_dir[$add]);
  251.                                                 //if($emn >= $end) return "E3{$add},{$emn},{$end}";
  252.                                                 
  253.                                         } else {

  254.                                         if(!($err_mov[$add]&1)){ //标记位为0才可以进入判断
  255.                                         import_lay($lay_map[$add]); //导入当前拼图(地图)
  256.                                                 if(is_mov(0)){ //可否上移
  257.                                                         up_mov(); //拼图上移
  258.                                                         if(!add_map(0,$add)){ //地图已经存在于表中加入失败
  259.                                                         $err_mov[$add] |= 1;  //执行位或运算,标记二进制位下次不再进入
  260.                                                         down_mov(); //回滚移动操作
  261.                                                         }else{if(solve_ok() != -1) return rmd();} //移动成功并且还原成功
  262.                                                         
  263.                                                 } else { //不可上移
  264.                                                         $err_mov[$add] |= 1;
  265.                                                 }
  266.                                         }

  267.                                         if(!($err_mov[$add]&2)){
  268.                                         import_lay($lay_map[$add]);
  269.                                                 if(is_mov(1)){ //可否下移
  270.                                                         down_mov();
  271.                                                         if(!add_map(1,$add)){
  272.                                                         $err_mov[$add] |= 2;
  273.                                                         up_mov();
  274.                                                         }else{if(solve_ok() != -1) return rmd();}
  275.                                                 } else {
  276.                                                         $err_mov[$add] |= 2;
  277.                                                 }
  278.                                         }

  279.                                         if(!($err_mov[$add]&4)){
  280.                                         import_lay($lay_map[$add]);
  281.                                                 if(is_mov(2)){ //可否左移
  282.                                                         left_mov();
  283.                                                         if(!add_map(2,$add)){
  284.                                                         $err_mov[$add] |= 4;
  285.                                                         right_mov();
  286.                                                         }else{if(solve_ok() != -1) return rmd();}
  287.                                                 } else {
  288.                                                         $err_mov[$add] |= 4;
  289.                                                 }
  290.                                         }

  291.                                         if(!($err_mov[$add]&8)){
  292.                                         import_lay($lay_map[$add]);
  293.                                                 if(is_mov(3)){ //可否右移
  294.                                                         right_mov();
  295.                                                         if(!add_map(3,$add)){
  296.                                                         $err_mov[$add] |= 8;
  297.                                                         left_mov();
  298.                                                         }else{if(solve_ok() != -1) return rmd();}
  299.                                                 } else {
  300.                                                         $err_mov[$add] |= 8;
  301.                                                 }
  302.                                         }

  303.                                         if(!($err_mov[$add]&16)){
  304.                                         import_lay($lay_map[$add]);
  305.                                                 if(is_mov(4)){ //可否里移
  306.                                                         in_mov();
  307.                                                         if(!add_map(4,$add)){
  308.                                                         $err_mov[$add] |= 16;
  309.                                                         out_mov();
  310.                                                         }else{if(solve_ok() != -1) return rmd();}
  311.                                                 } else {
  312.                                                         $err_mov[$add] |= 16;
  313.                                                 }
  314.                                         }

  315.                                         if(!($err_mov[$add]&32)){
  316.                                         import_lay($lay_map[$add]);
  317.                                                 if(is_mov(5)){ //可否外移
  318.                                                         out_mov();
  319.                                                         if(!add_map(5,$add)){
  320.                                                         $err_mov[$add] |= 32;
  321.                                                         in_mov();
  322.                                                         }else{if(solve_ok() != -1) return rmd();}
  323.                                                 } else {
  324.                                                         $err_mov[$add] |= 32;
  325.                                                 }
  326.                                         }

  327.                                 }

  328.                                 //$add++;
  329.                                 } //for



  330.                                 
  331.                                 
  332.                         $old = $end;
  333.                         } //while

  334. } //function





  335. $j = array(
  336. 1,5,2,3,4,6,10,7,8,9,11,15,0,12,13,14,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63
  337. );
  338. import_lay($j);
  339. $l = "";

  340. $start_time = time(); //开始时间
  341. $rmd = solve();
  342. $end_time = time() - $start_time; //结束时间

  343. echo "结果:".n2d($rmd)."<br>";
  344. echo "消耗时间:{$end_time}秒<br>";



  345. //---------------------------------------------------------------------------------

  346. ?>
复制代码



评分

2

查看全部评分

发表于 2018-1-25 08:31:50 | 显示全部楼层

回帖奖励 +2

不想长大 发表于 2018-1-24 21:32
占内存大的应该是bfs算法。

bfs是什么梗???
发表于 2018-4-16 16:00:38 | 显示全部楼层
啧啧啧 发表于 2018-1-30 21:59
先给腾开几亿年来看

不如直接用量子的吧
发表于 2018-1-25 11:36:14 | 显示全部楼层

回帖奖励 +2


我也不太清楚,自行百度吧。
发表于 2018-1-24 19:19:51 | 显示全部楼层

回帖奖励 +2

本帖最后由 最6的我 于 2018-1-24 19:21 编辑

谢谢斑竹大大研究。
发表于 2018-1-24 21:32:51 | 显示全部楼层

回帖奖励 +2

占内存大的应该是bfs算法。
发表于 2018-1-25 11:58:38 | 显示全部楼层

回帖奖励 +2

看看什么梗。
发表于 2018-1-26 10:12:19 | 显示全部楼层

回帖奖励 +2

看见很费时间。
发表于 2018-1-26 14:21:46 | 显示全部楼层

回帖奖励 +2

呃呃呃路过了。
发表于 2018-1-30 21:59:29 | 显示全部楼层

回帖奖励 +2

先给腾开几亿年来看
您需要登录后才可以回帖 登录 | 注册已关闭

本版积分规则

QQ|手机版|Archiver|从F到0 ( 蒙ICP备17002595号-1 )
蒙公网安备15010402000325号

腾讯云安全认证

GMT+8, 2024-3-28 17:59 , Processed in 0.493029 second(s), 22 queries .

Powered by Discuz! X3.4 Licensed

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表