设为首页收藏本站CRC32解密2.0更改用户名回帖奖励召回投票记录删除领夜猫子帮助中心 本站已运行
搜索
查看: 253|回复: 8
收起左侧

[PHP/ASP/JSP] 3D Puzzle 4x4x4 63Puzzle 自动搜索还原求解程序BFS算法实现 V1.1&PHP版

[复制链接]
发表于 2018-2-3 04:19:35 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?加入我们

x


  1. 3D Puzzle 4x4x4 63Puzzle 自动搜索还原求解程序BFS算法实现 V1.1&PHP版
  2. 版本修订历史:
  3. (2018/02/03) V1.1
  4.         其余3层一致则按照传统的平面模式搜索,不再进行里外搜索,至少节省10倍搜索时间。
  5.         可实时查看占用内存,运行时间,当前以及最低逆序数等,逆序数为0即为还原成功。


复制代码

  1. <?php
  2. ob_end_clean();
  3. ob_implicit_flush(1);
  4. set_time_limit(0);
  5. ini_set('memory_limit','1024M');
  6. ignore_user_abort(0);
  7. date_default_timezone_set("Asia/Shanghai");

  8. register_shutdown_function("check_abort"); // 在脚本结束时调用 check_abort 函数

  9. function check_abort(){
  10.   if (connection_aborted()){
  11.   exit();

  12. }
  13.   }

  14. function byte_con($i){
  15.         $byte = abs($i);
  16.         if($byte >=1099511627776){
  17.         $return = ($byte/1099511627776)."Tb";
  18.         } elseif($byte >=1073741824){
  19.         $return = ($byte/1073741824)."Gb";
  20.         } elseif($byte >=1048576){
  21.         $return =  ($byte/1048576)."Mb";
  22.         } elseif($byte >=1024){
  23.         $return = ($byte/1024)."Kb";
  24.         } else {
  25.         $return = $byte."b";
  26.         }
  27.         if($byte != $i) $return='-'.$return;
  28.         return $return;
  29. }




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


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

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

  44. $lay_map = array(); //拼图地图 多维数组 第二维固定64字节。
  45. $mov_dir = array(); //移动轨迹 保存着到指定地图的移动轨迹,文本6进制整数保存。
  46. $err_mov = array(); //每走过或失败一次指定的二进制位置为1,一但为1则不会进入搜索,只有6个二进制位用的到。


  47. $min_inv = 10000; //最小逆序数
  48. $b = 0;
  49. $old = 0;





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



  51. function get_adj_coo($zero_adj,$mov_dir){                 //获取相邻坐标
  52.         global $xyd;
  53.         return $xyd[$zero_adj*4+$mov_dir-1];
  54. }


  55. function get_0_lay(){ //获取0(空白)所在的层数 返回1~4
  56.         global $l1,$l2,$l3,$l4;
  57.         for($add=0;$add<16;$add++){
  58.                 if($l1[$add] == 0)return 1;
  59.                 if($l2[$add] == 0)return 2;
  60.                 if($l3[$add] == 0)return 3;
  61.                 if($l4[$add] == 0)return 4;
  62.         }
  63.         return 0; //不可能 除非没有0
  64. }


  65. function get_0_pla(){ //获取0(空白)的平面坐标 返回0~15
  66.         global $l1,$l2,$l3,$l4;
  67.         $lay=get_0_lay(); //获取0所在的层数
  68.         for($add=0;$add<16;$add++){
  69.                         if($lay == 1 && $l1[$add] == 0){
  70.                                 return $add;
  71.                         }elseif($lay == 2 && $l2[$add] == 0){
  72.                                 return $add;
  73.                         }elseif($lay == 3 && $l3[$add] == 0){
  74.                                 return $add;
  75.                         }elseif($lay == 4 && $l4[$add] == 0){
  76.                                 return $add;
  77.                         }
  78.                 }
  79.         return -1; //不可能
  80. }


  81. function pec($s,$a,$b){ //平面交换数字位置 层数:1~4 坐标A 坐标B
  82.         global $l1,$l2,$l3,$l4;
  83.         $ad=0;$bd=0;
  84.         if($a > 15 || $b > 15) return 0;
  85.                 if($s == 1){$ad=$l1[$a];$bd=$l1[$b];$l1[$a]=$bd;$l1[$b]=$ad;return 1;}
  86.                 if($s == 2){$ad=$l2[$a];$bd=$l2[$b];$l2[$a]=$bd;$l2[$b]=$ad;return 1;}
  87.                 if($s == 3){$ad=$l3[$a];$bd=$l3[$b];$l3[$a]=$bd;$l3[$b]=$ad;return 1;}
  88.                 if($s == 4){$ad=$l4[$a];$bd=$l4[$b];$l4[$a]=$bd;$l4[$b]=$ad;return 1;}
  89.         return 0;
  90. }


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


  99. function down_mov(){ //拼图下移
  100.         if(!is_mov(1)) return 0;
  101.         $lay0=get_0_lay(); //获取0的坐标所在层数
  102.         $pla0=get_0_pla(); //获取0的平面坐标
  103.         $adj=get_adj_coo($pla0,2); //获取相邻坐标
  104.         pec($lay0,$pla0,$adj); //平面交换数字位置
  105.         return 1;
  106. }

  107. function left_mov(){ //拼图左移
  108.         if(!is_mov(2)) return 0;
  109.         $lay0=get_0_lay(); //获取0的坐标所在层数
  110.         $pla0=get_0_pla(); //获取0的平面坐标
  111.         $adj=get_adj_coo($pla0,3); //获取相邻坐标
  112.         pec($lay0,$pla0,$adj); //平面交换数字位置
  113.         return 1;
  114. }

  115. function right_mov(){ //拼图右移
  116.         if(!is_mov(3)) return 0;
  117.         $lay0=get_0_lay(); //获取0的坐标所在层数
  118.         $pla0=get_0_pla(); //获取0的平面坐标
  119.         $adj=get_adj_coo($pla0,4); //获取相邻坐标
  120.         pec($lay0,$pla0,$adj); //平面交换数字位置
  121.         return 1;
  122. }

  123. function in_mov(){ //拼图里移
  124. global $l1,$l2,$l3,$l4;
  125.         if(!is_mov(4)) return 0;
  126.         $lay0=get_0_lay(); //获取0的坐标所在层数
  127.         $pla0=get_0_pla(); //获取0的平面坐标
  128.                 if($lay0 < 4){
  129.                         if($lay0 == 3){$l3[$pla0]=$l4[$pla0];$l4[$pla0]=0;}
  130.                         if($lay0 == 2){$l2[$pla0]=$l3[$pla0];$l3[$pla0]=0;}
  131.                         if($lay0 == 1){$l1[$pla0]=$l2[$pla0];$l2[$pla0]=0;}
  132.                 }
  133.         return 1;

  134. }

  135. function out_mov(){ //拼图外移
  136. global $l1,$l2,$l3,$l4;
  137.         if(!is_mov(5)) return 0;
  138.         $lay0=get_0_lay(); //获取0的坐标所在层数
  139.         $pla0=get_0_pla(); //获取0的平面坐标
  140.                 if($lay0 > 1){
  141.                         if($lay0 == 4){$l4[$pla0]=$l3[$pla0];$l3[$pla0]=0;}
  142.                         if($lay0 == 3){$l3[$pla0]=$l2[$pla0];$l2[$pla0]=0;}
  143.                         if($lay0 == 2){$l2[$pla0]=$l1[$pla0];$l1[$pla0]=0;}
  144.                 }
  145.         return 1;
  146. }

  147. function mov($dir){ //按数字指定指定的方向移动拼图
  148.         switch($dir){
  149.                 case 0:$return = up_mov();break;
  150.                 case 1:$return = down_mov();break;
  151.                 case 2:$return = left_mov();break;
  152.                 case 3:$return = right_mov();break;
  153.                 case 4:$return = in_mov();break;
  154.                 case 5:$return = out_mov();break;
  155.                 default:$return = -1;break;
  156.         }
  157.         return $return;
  158.        
  159. }

  160. function nge_dir($dir){ //获取移动对应的相反方向数字
  161.         return $dir&6|!($dir&1);

  162. }


  163. function is_mov($dir){ //可否往指定方向移动
  164.                 $pla = get_0_pla();
  165.                 switch($dir){        //判断移动方向
  166.                         case 0:$return = get_adj_coo($pla,1) <= 15;break;        //可否上移
  167.                         case 1:$return = get_adj_coo($pla,2) <= 15;break;        //可否下移
  168.                         case 2:$return = get_adj_coo($pla,3) <= 15;break;        //可否左移
  169.                         case 3:$return = get_adj_coo($pla,4) <= 15;break;        //可否右移
  170.                         case 4:$return = get_0_lay() < 4;break;                                //可否里移
  171.                         case 5:$return = get_0_lay() > 1;break;                                //可否外移
  172.                         default:$return = -1;break;                                        //无效方向
  173.                 }
  174.         return $return;                //返回结果 1允许移动 0禁止移动 -1无效方向
  175. }

  176. function import_lay($layout){ //导入拼图(地图) 接收64字节数据
  177.         global $l1,$l2,$l3,$l4;
  178.         $lay4 = array_chunk($layout,16);
  179.         $l1=$lay4[0];$l2=$lay4[1];
  180.         $l3=$lay4[2];$l4=$lay4[3];
  181. }

  182. function lay_merge(){ //导出拼图数组合并成一个,合成以后就是64字节的地图
  183.         global $l1,$l2,$l3,$l4;
  184.         return array_merge_recursive($l1,$l2,$l3,$l4);
  185. }

  186. function n2d($number){ //数字移动轨迹翻译成汉字
  187.         $n = $number;
  188.                 $n = str_replace('0',"上",$n);
  189.                 $n = str_replace('1',"下",$n);
  190.                 $n = str_replace('2',"左",$n);
  191.                 $n = str_replace('3',"右",$n);
  192.                 $n = str_replace('4',"里",$n);
  193.                 $n = str_replace('5',"外",$n);
  194.         return $n;

  195. }



  196. //------------------------计算拼图是否可解------------------------
  197. function inversion($number){        //计算逆序数 需接收单维数组整数
  198.         $size = sizeof($number); //数组成员数
  199.         $return = 0;
  200.                 for($add=0;$add<$size;$add++){
  201.                         $number2 = $number[$add]; //当前数
  202.                                 for($add2=$add;$add2<$size;$add2++){
  203.                                 if($number[$add2] < $number2) $return++;
  204.                         }
  205.                 }
  206.         return $return;
  207. }

  208. function get_0_ode(){ //取0(空白)所在的奇偶位置
  209.         global $o0,$o1;
  210.         $pla = get_0_pla(); //坐标
  211.                 switch(get_0_lay()){ //判断在第几层
  212.                         case 1:$return = $o0[$pla];break;
  213.                         case 2:$return = $o1[$pla];break;
  214.                         case 3:$return = $o0[$pla];break;
  215.                         case 4:$return = $o1[$pla];break;
  216.                         default:$return = -1;break; //不可能
  217.                 }

  218.         return $return;

  219. }


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

  222. }


  223. //------------------------计算拼图还原顺序------------------------


  224. function search_map($search_map){ //搜索当前地图是否已经存在于表中 存在返回位置 不存在返回-1
  225.         global $lay_map;
  226.         if(!in_array($search_map,$lay_map)) return -1; //不存在 返回-1
  227.                 return array_search($search_map,$lay_map); //存在返回位置 0开头
  228.        
  229. }

  230. function add_map($direction,$add){ //将地图加入表中 参数1 方向 参数2 计数
  231.         global $lay_map,$mov_dir,$err_mov;
  232.         $map = lay_merge();
  233.         //echo $direction." ".$add."<br>";
  234.                 if(search_map($map) != -1) return 0;  //已存在 不加入
  235.                 array_push($lay_map,$map); //加入拼图
  236.                 $add2 = sizeof($lay_map); //获取拼图记录中有多少表
  237.                         array_push($mov_dir,$mov_dir[$add].$direction); //加入移动轨迹                       
  238.                         array_push($err_mov,0);
  239.                         $err_mov[$add] |= (1 <<$direction);

  240.                 return 1;

  241. }

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






  248. function rmt($rmt){ //将移动的表反向处理 如 上下左(012) 转换成就是 右上下(301)
  249.         $return = "";
  250.         for($dec=strlen($rmt)-1;$dec>=0;$dec--){
  251.                 $return .= nge_dir(substr($rmt,$dec,1));
  252.                 }
  253.         return $return;
  254. }

  255. function is_plane(){ //其余3层是否一致,若一致不再进行里外搜索,节省N倍搜索时间
  256.         global $init_lay;
  257.         $lay = lay_merge();
  258.         for($add=16;$add<64;$add++){
  259.                 if($init_lay[$add] != $lay[$add]){
  260.                         return 0;
  261.                 }
  262.         }
  263.         return 1;
  264. }

  265. function opt_mov($m){ //优化去除移动记录表 比如里外 上下 左右 里里 外外 等重复没用的动作
  266.         $n = $m;
  267.         $n = str_replace('555444','',$n);
  268.         $n = str_replace('444555','',$n);
  269.         $n = str_replace('333222','',$n);
  270.         $n = str_replace('222333','',$n);
  271.         $n = str_replace('111000','',$n);
  272.         $n = str_replace('000111','',$n);
  273.         $n = str_replace('5544','',$n);
  274.         $n = str_replace('4455','',$n);
  275.         $n = str_replace('3322','',$n);
  276.         $n = str_replace('2233','',$n);
  277.         $n = str_replace('1100','',$n);
  278.         $n = str_replace('0011','',$n);
  279.         $n = str_replace('54','',$n);
  280.         $n = str_replace('45','',$n);
  281.         $n = str_replace('32','',$n);
  282.         $n = str_replace('23','',$n);
  283.         $n = str_replace('10','',$n);
  284.         $n = str_replace('01','',$n);
  285.         return $n;

  286. }


  287. //$b=0;
  288. $max_ram = 0;
  289. function solve(){ //还原拼图
  290.         global $lay_map,$mov_dir,$err_mov,$init_lay,$min_inv,$max_ram;
  291.         $add3=0;$add5=0;
  292.         $add4=0;$old=0;       
  293.         if(!is_solvable()) return "E1"; //不可解
  294.         if($init_lay == lay_merge()) return "E2"; //前后一致,不需要解
  295.                 $lay_map = array(lay_merge()); //地图,多维数组,每个地图64字节。
  296.                 $mov_dir = array(''); //轨迹,以6进制数字的方式保存。
  297.                 $err_mov = array(0);

  298.                 $old_inv = 0;  //旧逆序数
  299.                         if(is_plane()) { //其余3层一致则以平面模式搜索,否则立体
  300.                                         $max_dir = 4;
  301.                                         $mbd = 15;
  302.                                  } else {
  303.                                         $max_dir = 6;
  304.                                         $mbd = 63;
  305.                         }
  306.                         while(1){ //死循环
  307.                                 $end = sizeof($lay_map); //有多少个地图等待遍历
  308.                                 //echo "----------------------------------------------------------------<br>";
  309.                                 //echo "移动轨迹:{$mov_dir[sizeof($mov_dir)-1]}<br>";

  310.                                 for($add=$old;$add<$end;$add++){
  311.                                         $inv = inversion(lay_merge());
  312.                                         $min_inv = min($min_inv,$inv);
  313.                                                 $add4++;
  314.                                                 if($add4>=100){
  315.                                                 $add4=0;
  316.                                                 $ram = memory_get_usage();
  317.                                                 $max_ram = max($max_ram,$ram); //获取最大占用内存
  318.                                                 $cmr = byte_con($max_ram);
  319.                                                 $crr = byte_con($ram);


  320.                                 $tmp = n2d($mov_dir[sizeof($mov_dir)-1]);
  321.                                 $date = date("Y-m-d H:i:s");
  322.                                 echo "{$date} 范围:{$add}/{$end} 当前逆序数:{$inv} 最低逆序数:{$min_inv} 内存峰值:{$cmr} 实时内存:{$crr} <br>";
  323.                                                 }
  324.                                                         if($min_inv < $old_inv ){
  325.                                                        
  326.                                                         $tmp = n2d($mov_dir[sizeof($mov_dir)-1]);
  327.                                 echo "【最小逆序数】范围:{$add}/{$end} 当前逆序数:{$inv} 最小逆序数:{$min_inv}|{$tmp}<br>";
  328.                                 }

  329.                                 $old_inv = $min_inv; //保存旧逆序数
  330.                                         //echo ($err_mov[$add]&$mbd)."<br>";
  331.                                         if(($err_mov[$add]&$mbd) == $mbd){ //当前地图中所有方向二进制位都标记为1,都不可走不再进入搜索
  332.                                                 //unset($mov_dir[$add]);
  333.                                                 //unset($lay_map[$add]);
  334.                                         } else {
  335.                                         for($dir=0;$dir<$max_dir;$dir++){
  336.                                         //echo print_r($err_mov,1)."<br>";
  337.                                         if(!($err_mov[$add]&(1<<$dir))){ //标记位为0才可以进入判断
  338.                                         import_lay($lay_map[$add]); //导入当前拼图(地图)
  339.                                                 if(is_mov($dir)){ //可否往指定的方向移动
  340.                                                         mov($dir); //移动拼图 变量dir是方向
  341.                                                         if(!add_map($dir,$add)){ //地图已经存在于表中加入失败
  342.                                                         $err_mov[$add] |= (1<<$dir);  //执行位或运算,标记二进制位下次不再进入
  343.                                                         mov(nge_dir($dir)); //以反方向移动
  344.                                                                 } else {
  345.                                                         if(solve_ok() != -1) { //移动并还原成功
  346.                                                                 return $mov_dir[solve_ok()];
  347.                                                         }
  348.                                                 }
  349.                                                        
  350.                                                 } else { //不可移动
  351.                                                         $err_mov[$add] |= (1<<$dir);
  352.                                                 }
  353.                                         }
  354.                                 }



  355.                                 }

  356.                                 //$add++;
  357.                                 } //for



  358.                                
  359.                                
  360.                                
  361.                                 //echo "开始释放内存...<br>";
  362.                                 //$add5=0;
  363.                                 //$old=0;
  364.                        
  365.                         $old = $end;
  366.                        
  367.                         } //while
  368.         return "E3"; //死循环应该不可能退出
  369. } //function

  370. /*
  371. function solve(){ //还原拼图
  372. $l = "";

  373.         $rmd = "";
  374.                 while($rmd != "E2"){
  375.                         $rmd = dec_inv();
  376.                         if($rmd == "E2") break;
  377.                                 $l=$l.$rmd;

  378.                         }
  379.         return $l;
  380. }
  381. */




  382. $j = array(





  383. 9,2,13,11,3,6,12,10,5,7,8,1,4,0,15,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

  384. );

  385. import_lay($j);


  386. $start_time = time(); //开始时间
  387. $l = solve();

  388. $end_time = time() - $start_time; //结束时间
  389. $l = opt_mov($l);
  390. echo "结果:".n2d($l)."<br>";
  391. echo "消耗时间:{$end_time}秒<br>";



  392. //---------------------------------------------------------------------------------

  393. ?>
复制代码



回复

使用道具 举报

腾讯云服务器安全可靠高性能,多种配置供您选择
发表于 2018-2-3 08:16:03 | 显示全部楼层
跟以前发的1.0版应该是同一种东西吧。
回复 支持 反对

使用道具 举报

发表于 2018-2-3 13:47:54 | 显示全部楼层
回复看看,貌似百度上面都没有。
回复 支持 反对

使用道具 举报

发表于 2018-2-4 16:47:35 | 显示全部楼层
我也来看看啥更新
回复 支持 反对

使用道具 举报

发表于 2018-2-4 19:29:14 | 显示全部楼层
和之前的应该有很多变化
回复 支持 反对

使用道具 举报

发表于 2018-2-8 10:23:41 | 显示全部楼层
看不懂。
回复 支持 反对

使用道具 举报

发表于 2018-4-22 10:35:40 来自手机 | 显示全部楼层
我也没弄明白。。。
回复 支持 反对

使用道具 举报

发表于 2018-11-5 17:02:09 | 显示全部楼层
回复 支持 反对

使用道具 举报

发表于 2019-1-29 19:57:44 | 显示全部楼层
我来可空
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 加入我们

本版积分规则

小黑屋|手机版|Archiver|官方QQ群|从F到0 ( 蒙ICP备17002595号-1 )
蒙公网安备 15010402000325号 腾讯云安全认证

GMT+8, 2019-5-21 18:37, 34.229.151.87 , Processed in 0.157227 second(s), 26 queries .

Powered by Discuz! X3.4 © 2001-2017 Comsenz Inc.

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