经过了N天的研究,终于搞出了算法,步数少的也得几分钟,多的几亿年不清楚,占内存cpu非常高,也可能由于内存溢出等问题解不出来,有条件的建议挂到天河二号上运行,里面有判断是否可解的源码,可能会存在一些bug,大神可以拿去继续改进。
- <?php
- ob_end_clean();
- ob_implicit_flush(1);
- set_time_limit(3600);
- ini_set('memory_limit','1024M');
- ignore_user_abort(0);
- date_default_timezone_set("Asia/Shanghai");
- $xyd = array( //拼图板移动方向与0(空白)交换坐标数据,严禁修改否则数字会跳格或无法正常移动。
- 0x04,0x10,0x01,0x10,0x05,0x10,0x02,0x00,0x06,0x10,0x03,0x01,0x07,0x10,0x10,0x02,
- 0x08,0x00,0x05,0x10,0x09,0x01,0x06,0x04,0x0A,0x02,0x07,0x05,0x0B,0x03,0x10,0x06,
- 0x0C,0x04,0x09,0x10,0x0D,0x05,0x0A,0x08,0x0E,0x06,0x0B,0x09,0x0F,0x07,0x10,0x0A,
- 0x10,0x08,0x0D,0x10,0x10,0x09,0x0E,0x0C,0x10,0x0A,0x0F,0x0D,0x10,0x0B,0x10,0x0E
- );
- $l1 = array(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); //推盘层1(最里层)
- $l2 = array(16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31); //推盘层2
- $l3 = array(32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47); //推盘层3
- $l4 = array(48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63); //推盘层4(最外层)
- $init_lay = range(0,63); //还原后的拼图 0~63
- //推盘层奇偶位置,核验是否可解必须用的到
- $o0 = array(0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0);
- $o1 = array(1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1);
- $lay_map = array(); //拼图地图 多维数组 第二维固定64字节
- $mov_dir = array(); //移动轨迹 保存着到指定地图的移动轨迹,文本整数保存
- $err_mov = array(); //每走过或失败一次指定的二进制位置为1,一但为1则不会进入搜索,只有6个二进制位用的到。
- //------------------------3D推盘驱动程序------------------------
- function get_adj_coo($zero_adj,$mov_dir){ //获取相邻坐标
- global $xyd;
- return $xyd[$zero_adj*4+$mov_dir-1];
- }
- function get_0_lay(){ //获取0(空白)所在的层数 返回1~4
- global $l1,$l2,$l3,$l4;
- for($add=0;$add<16;$add++){
- if($l1[$add] == 0)return 1;
- if($l2[$add] == 0)return 2;
- if($l3[$add] == 0)return 3;
- if($l4[$add] == 0)return 4;
- }
- return 0; //不可能 除非没有0
- }
- function get_0_pla(){ //获取0(空白)的平面坐标 返回0~15
- global $l1,$l2,$l3,$l4;
- $lay=get_0_lay(); //获取0所在的层数
- for($add=0;$add<16;$add++){
- if($lay == 1 && $l1[$add] == 0){
- return $add;
- }elseif($lay == 2 && $l2[$add] == 0){
- return $add;
- }elseif($lay == 3 && $l3[$add] == 0){
- return $add;
- }elseif($lay == 4 && $l4[$add] == 0){
- return $add;
- }
- }
- return -1; //不可能
- }
- function pec($s,$a,$b){ //平面交换数字位置 层数:1~4 坐标A 坐标B
- global $l1,$l2,$l3,$l4;
- $ad=0;$bd=0;
- if($a > 15 || $b > 15) return 0;
- if($s == 1){$ad=$l1[$a];$bd=$l1[$b];$l1[$a]=$bd;$l1[$b]=$ad;return 1;}
- if($s == 2){$ad=$l2[$a];$bd=$l2[$b];$l2[$a]=$bd;$l2[$b]=$ad;return 1;}
- if($s == 3){$ad=$l3[$a];$bd=$l3[$b];$l3[$a]=$bd;$l3[$b]=$ad;return 1;}
- if($s == 4){$ad=$l4[$a];$bd=$l4[$b];$l4[$a]=$bd;$l4[$b]=$ad;return 1;}
- return 0;
- }
- function up_mov(){ //拼图上移
- if(!is_mov(0)) return 0;
- $lay0=get_0_lay(); //获取0的坐标所在层数
- $pla0=get_0_pla(); //获取0的平面坐标
- $adj=get_adj_coo($pla0,1); //获取相邻坐标
- pec($lay0,$pla0,$adj); //平面交换数字位置
- return 1;
- }
- function down_mov(){ //拼图下移
- if(!is_mov(1)) return 0;
- $lay0=get_0_lay(); //获取0的坐标所在层数
- $pla0=get_0_pla(); //获取0的平面坐标
- $adj=get_adj_coo($pla0,2); //获取相邻坐标
- pec($lay0,$pla0,$adj); //平面交换数字位置
- return 1;
- }
- function left_mov(){ //拼图左移
- if(!is_mov(2)) return 0;
- $lay0=get_0_lay(); //获取0的坐标所在层数
- $pla0=get_0_pla(); //获取0的平面坐标
- $adj=get_adj_coo($pla0,3); //获取相邻坐标
- pec($lay0,$pla0,$adj); //平面交换数字位置
- return 1;
- }
- function right_mov(){ //拼图右移
- if(!is_mov(3)) return 0;
- $lay0=get_0_lay(); //获取0的坐标所在层数
- $pla0=get_0_pla(); //获取0的平面坐标
- $adj=get_adj_coo($pla0,4); //获取相邻坐标
- pec($lay0,$pla0,$adj); //平面交换数字位置
- return 1;
- }
- function in_mov(){ //拼图里移
- global $l1,$l2,$l3,$l4;
- if(!is_mov(4)) return 0;
- $lay0=get_0_lay(); //获取0的坐标所在层数
- $pla0=get_0_pla(); //获取0的平面坐标
- if($lay0 < 4){
- if($lay0 == 3){$l3[$pla0]=$l4[$pla0];$l4[$pla0]=0;}
- if($lay0 == 2){$l2[$pla0]=$l3[$pla0];$l3[$pla0]=0;}
- if($lay0 == 1){$l1[$pla0]=$l2[$pla0];$l2[$pla0]=0;}
- }
- return 1;
- }
- function out_mov(){ //拼图外移
- global $l1,$l2,$l3,$l4;
- if(!is_mov(5)) return 0;
- $lay0=get_0_lay(); //获取0的坐标所在层数
- $pla0=get_0_pla(); //获取0的平面坐标
- if($lay0 > 1){
- if($lay0 == 4){$l4[$pla0]=$l3[$pla0];$l3[$pla0]=0;}
- if($lay0 == 3){$l3[$pla0]=$l2[$pla0];$l2[$pla0]=0;}
- if($lay0 == 2){$l2[$pla0]=$l1[$pla0];$l1[$pla0]=0;}
- }
- return 1;
- }
- function is_mov($direction){ //可否往指定方向移动
- $pla = get_0_pla();
- switch($direction){ //判断移动方向
- case 0:$return = get_adj_coo($pla,1) <= 15;break; //可否上移
- case 1:$return = get_adj_coo($pla,2) <= 15;break; //可否下移
- case 2:$return = get_adj_coo($pla,3) <= 15;break; //可否左移
- case 3:$return = get_adj_coo($pla,4) <= 15;break; //可否右移
- case 4:$return = get_0_lay() < 4;break; //可否里移
- case 5:$return = get_0_lay() > 1;break; //可否外移
- default:$return = -1;break; //无效方向
- }
- return $return; //返回结果 1允许移动 0禁止移动 -1无效方向
- }
- function import_lay($layout){ //导入拼图(地图) 接收64字节数据
- global $l1,$l2,$l3,$l4;
- $lay4 = array_chunk($layout,16);
- $l1=$lay4[0];$l2=$lay4[1];
- $l3=$lay4[2];$l4=$lay4[3];
- }
- //------------------------计算拼图是否可解------------------------
- function inversion($number){ //计算逆序数 需接收单维数组整数
- $size = sizeof($number); //数组成员数
- $return = 0;
- for($add=0;$add<$size;$add++){
- $number2 = $number[$add]; //当前数
- for($add2=$add;$add2<$size;$add2++){
- if($number[$add2] < $number2) $return++;
- }
- }
- return $return;
- }
- function get_0_ode(){ //取0(空白)所在的奇偶位置
- global $o0,$o1;
- $pla = get_0_pla(); //坐标
- switch(get_0_lay()){ //判断在第几层
- case 1:$return = $o0[$pla];break;
- case 2:$return = $o1[$pla];break;
- case 3:$return = $o0[$pla];break;
- case 4:$return = $o1[$pla];break;
- default:$return = -1;break; //不可能
- }
- return $return;
- }
- function lay_merge(){ //拼图数组合并成一个,合成以后就是64字节的地图
- global $l1,$l2,$l3,$l4;
- return array_merge_recursive($l1,$l2,$l3,$l4);
- }
- function is_solvable(){ //拼图是否可解
- return ((inversion(lay_merge())&1) == 1) == get_0_ode();
- }
- //------------------------计算拼图还原顺序------------------------
- function search_map($search_map){ //搜索当前地图是否已经存在于表中 存在返回位置 不存在返回-1
- global $lay_map;
- if(!in_array($search_map,$lay_map)) return -1; //不存在 返回-1
- return array_search($search_map,$lay_map); //存在返回位置 0开头
-
- }
- function add_map($direction,$add){ //将地图加入表中 参数1 方向 参数2 计数
- global $lay_map,$mov_dir,$err_mov;
- $map = lay_merge();
- //echo $direction." ".$add."<br>";
- if(search_map($map) != -1) return 0; //已存在 不加入
- array_push($lay_map,$map); //加入拼图
- $add2 = sizeof($lay_map); //获取拼图记录中有多少表
- array_push($mov_dir,$mov_dir[$add].$direction); //加入移动轨迹
- array_push($err_mov,0);
- $err_mov[$add] |= (1 << $direction);
- return 1;
- }
- function solve_ok(){ //还原是否成功
- global $init_lay; //还原成功后的拼图(地图)
- $result = search_map($init_lay); //查找当前地图是否存在于表中
- if($result == -1) return -1; //没搜到 不成功
- return $result; //成功 返回位置 0开头
- }
- function rmd(){ //读还原轨迹
- global $mov_dir;
- return $mov_dir[solve_ok()]; //读移动轨迹
- }
- function n2d($number){ //数字移动轨迹翻译成汉字
- $n = $number;
- $n = str_replace('0',"上",$n);
- $n = str_replace('1',"下",$n);
- $n = str_replace('2',"左",$n);
- $n = str_replace('3',"右",$n);
- $n = str_replace('4',"里",$n);
- $n = str_replace('5',"外",$n);
- return $n;
- }
- function solve(){ //还原拼图
- global $lay_map,$mov_dir,$err_mov,$init_lay;
- $add3=0;$old=0;
- $add4=0;
- if(!is_solvable()) return "E1"; //不可解
- if($init_lay == lay_merge()) return "E2"; //前后一致,不需要解
- $lay_map = array(lay_merge()); //地图,多维数组,每个地图64字节。
- $mov_dir = array(''); //轨迹,以数字的方式保存。
- $err_mov = array(0);
- $min_inv = 10000; //最小逆序数
- $old_inv = 0; //旧逆序数
- while(1){ //死循环,解成功了就会退出。
- $end = sizeof($lay_map); //有多少个地图等待遍历
- //echo "----------------------------------------------------------------<br>";
- //echo "移动轨迹:{$mov_dir[sizeof($mov_dir)-1]}<br>";
- //$old = 0;
- for($add=$old;$add<$end;$add++){
- $inv = inversion(lay_merge());
- $min_inv = min($min_inv,$inv);
- $add4++;
- if($min_inv < $old_inv || $add4 >=100){
- $add4=0;
- $tmp = n2d($mov_dir[sizeof($mov_dir)-1]);
- echo "范围:{$add}/{$end} 当前逆序数:{$inv} 最低逆序数:{$min_inv}|{$tmp}<br>";
- /*
- $mdir = lay_merge();
- $k="";
- for($add5=0;$add5<64;$add5++) $k.=$mdir[$add5].",";
- echo "{$k}<br>";
- import_lay($lay_map[sizeof($lay_map)-1]);
- $wz = search_map($lay_map[sizeof($lay_map)-1]);
- return $mov_dir[$wz];
- */
- }
- $old_inv = $min_inv; //保存旧逆序数
- if($err_mov[$add] == 63){ //当前地图中六个方向二进制位都标记为1,都不可走不再进入搜索
-
- //$emn++;
- //unset($lay_map[$add]);
- //unset($mov_dir[$add]);
- //if($emn >= $end) return "E3{$add},{$emn},{$end}";
-
- } else {
- if(!($err_mov[$add]&1)){ //标记位为0才可以进入判断
- import_lay($lay_map[$add]); //导入当前拼图(地图)
- if(is_mov(0)){ //可否上移
- up_mov(); //拼图上移
- if(!add_map(0,$add)){ //地图已经存在于表中加入失败
- $err_mov[$add] |= 1; //执行位或运算,标记二进制位下次不再进入
- down_mov(); //回滚移动操作
- }else{if(solve_ok() != -1) return rmd();} //移动成功并且还原成功
-
- } else { //不可上移
- $err_mov[$add] |= 1;
- }
- }
- if(!($err_mov[$add]&2)){
- import_lay($lay_map[$add]);
- if(is_mov(1)){ //可否下移
- down_mov();
- if(!add_map(1,$add)){
- $err_mov[$add] |= 2;
- up_mov();
- }else{if(solve_ok() != -1) return rmd();}
- } else {
- $err_mov[$add] |= 2;
- }
- }
- if(!($err_mov[$add]&4)){
- import_lay($lay_map[$add]);
- if(is_mov(2)){ //可否左移
- left_mov();
- if(!add_map(2,$add)){
- $err_mov[$add] |= 4;
- right_mov();
- }else{if(solve_ok() != -1) return rmd();}
- } else {
- $err_mov[$add] |= 4;
- }
- }
- if(!($err_mov[$add]&8)){
- import_lay($lay_map[$add]);
- if(is_mov(3)){ //可否右移
- right_mov();
- if(!add_map(3,$add)){
- $err_mov[$add] |= 8;
- left_mov();
- }else{if(solve_ok() != -1) return rmd();}
- } else {
- $err_mov[$add] |= 8;
- }
- }
- if(!($err_mov[$add]&16)){
- import_lay($lay_map[$add]);
- if(is_mov(4)){ //可否里移
- in_mov();
- if(!add_map(4,$add)){
- $err_mov[$add] |= 16;
- out_mov();
- }else{if(solve_ok() != -1) return rmd();}
- } else {
- $err_mov[$add] |= 16;
- }
- }
- if(!($err_mov[$add]&32)){
- import_lay($lay_map[$add]);
- if(is_mov(5)){ //可否外移
- out_mov();
- if(!add_map(5,$add)){
- $err_mov[$add] |= 32;
- in_mov();
- }else{if(solve_ok() != -1) return rmd();}
- } else {
- $err_mov[$add] |= 32;
- }
- }
- }
- //$add++;
- } //for
-
-
- $old = $end;
- } //while
- } //function
- $j = array(
- 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
- );
- import_lay($j);
- $l = "";
- $start_time = time(); //开始时间
- $rmd = solve();
- $end_time = time() - $start_time; //结束时间
- echo "结果:".n2d($rmd)."<br>";
- echo "消耗时间:{$end_time}秒<br>";
- //---------------------------------------------------------------------------------
- ?>
复制代码
|