15 puzzle solver: Difference between revisions
No edit summary |
No edit summary |
||
Line 1: | Line 1: | ||
{{task|Games}} |
{{task|Games}} |
||
Your task is to write a program that finds a solution in the fewest moves possible to a random [[wp:15_puzzle|Fifteen Puzzle Game]].<br /> |
Your task is to write a program that finds a solution in the fewest moves possible single moves to a random [[wp:15_puzzle|Fifteen Puzzle Game]].<br /> |
||
For this task you will be using the following puzzle:<br /> |
For this task you will be using the following puzzle:<br /> |
||
<pre>15 14 1 6 |
<pre>15 14 1 6 |
Revision as of 11:58, 30 November 2017
You are encouraged to solve this task according to the task description, using any language you may know.
Your task is to write a program that finds a solution in the fewest moves possible single moves to a random Fifteen Puzzle Game.
For this task you will be using the following puzzle:
15 14 1 6 9 11 4 12 0 10 7 3 13 8 5 2
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0
The output must show the moves' directions, like so: left, left, left, down, right... and so on.
There are 2 solutions with 52 moves:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd
finding either one, or both is an acceptable result.
see: Pretty Print of Optimal Solution
- Extra credit.
Solve the following problem:
0 12 9 13 15 11 10 14 3 7 2 5 4 8 6 1
- Related Task
C++
Staying Functional (as possible in C++)
The Solver
<lang cpp> // Solve Random 15 Puzzles : Nigel Galloway - October 11th., 2017 const int Nr[]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}; using N = std::tuple<int,int,unsigned long,std::string,int>; void fN(const N,const int); const N fI(const N n){
int g = (11-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n)+1,std::get<1>(n),std::get<2>(n)-a+(a<<16),std::get<3>(n)+"d",(Nr[a>>g]<=std::get<0>(n))?std::get<4>(n):std::get<4>(n)+1);
} const N fG(const N n){
int g = (19-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n)-1,std::get<1>(n),std::get<2>(n)-a+(a>>16),std::get<3>(n)+"u",(Nr[a>>g]>=std::get<0>(n))?std::get<4>(n):std::get<4>(n)+1);
} const N fE(const N n){
int g = (14-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n),std::get<1>(n)+1,std::get<2>(n)-a+(a<<4),std::get<3>(n)+"r",(Nc[a>>g]<=std::get<1>(n))?std::get<4>(n):std::get<4>(n)+1);
} const N fL(const N n){
int g = (16-std::get<1>(n)-std::get<0>(n)*4)*4; unsigned long a = std::get<2>(n)&((unsigned long)15<<g); return N (std::get<0>(n),std::get<1>(n)-1,std::get<2>(n)-a+(a>>4),std::get<3>(n)+"l",(Nc[a>>g]>=std::get<1>(n))?std::get<4>(n):std::get<4>(n)+1);
} void fZ(const N n, const int g){
if (std::get<2>(n)==0x123456789abcdef0){ int g{};for (char a: std::get<3>(n)) ++g; std::cout<<"Solution found with "<<g<<" moves: "<<std::get<3>(n)<<std::endl; exit(0);} if (std::get<4>(n) <= g) fN(n,g);
} void fN(const N n, const int g){
const int i{std::get<0>(n)}, e{std::get<1>(n)}, l{std::get<3>(n).back()}; switch(i){case 0: switch(e){case 0: switch(l){case 'l': fZ(fI(n),g); return; case 'u': fZ(fE(n),g); return; default : fZ(fE(n),g); fZ(fI(n),g); return;} case 3: switch(l){case 'r': fZ(fI(n),g); return; case 'u': fZ(fL(n),g); return; default : fZ(fL(n),g); fZ(fI(n),g); return;} default: switch(l){case 'l': fZ(fI(n),g); fZ(fL(n),g); return; case 'r': fZ(fI(n),g); fZ(fE(n),g); return; case 'u': fZ(fE(n),g); fZ(fL(n),g); return; default : fZ(fL(n),g); fZ(fI(n),g); fZ(fE(n),g); return;}} case 3: switch(e){case 0: switch(l){case 'l': fZ(fG(n),g); return; case 'd': fZ(fE(n),g); return; default : fZ(fE(n),g); fZ(fG(n),g); return;} case 3: switch(l){case 'r': fZ(fG(n),g); return; case 'd': fZ(fL(n),g); return; default : fZ(fL(n),g); fZ(fG(n),g); return;} default: switch(l){case 'l': fZ(fG(n),g); fZ(fL(n),g); return; case 'r': fZ(fG(n),g); fZ(fE(n),g); return; case 'd': fZ(fE(n),g); fZ(fL(n),g); return; default : fZ(fL(n),g); fZ(fG(n),g); fZ(fE(n),g); return;}} default: switch(e){case 0: switch(l){case 'l': fZ(fI(n),g); fZ(fG(n),g); return; case 'u': fZ(fE(n),g); fZ(fG(n),g); return; case 'd': fZ(fE(n),g); fZ(fI(n),g); return; default : fZ(fE(n),g); fZ(fI(n),g); fZ(fG(n),g); return;} case 3: switch(l){case 'd': fZ(fI(n),g); fZ(fL(n),g); return; case 'u': fZ(fL(n),g); fZ(fG(n),g); return; case 'r': fZ(fI(n),g); fZ(fG(n),g); return; default : fZ(fL(n),g); fZ(fI(n),g); fZ(fG(n),g); return;} default: switch(l){case 'd': fZ(fI(n),g); fZ(fL(n),g); fZ(fE(n),g); return; case 'l': fZ(fI(n),g); fZ(fL(n),g); fZ(fG(n),g); return; case 'r': fZ(fI(n),g); fZ(fE(n),g); fZ(fG(n),g); return; case 'u': fZ(fE(n),g); fZ(fL(n),g); fZ(fG(n),g); return; default : fZ(fL(n),g); fZ(fI(n),g); fZ(fE(n),g); fZ(fG(n),g); return;}}}
} void Solve(N n){for(int g{};;++g) fN(n,g);} </lang>
The Task
<lang cpp> int main (){
N start(2,0,0xfe169b4c0a73d852,"",0); Solve(start);
} </lang>
- Output:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd real 0m2.897s user 0m2.887s sys 0m0.008s
Time to get Imperative
see for an analysis of 20 randomly generated 15 puzzles solved with this solver.
The Solver
<lang cpp> // Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017 class fifteenSolver{
const int Nr[16]{3,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3}, Nc[16]{3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2}, i{1}, g{8}, e{2}, l{4}; int n{},_n{}, N0[85]{},N3[85]{},N4[85]{}; unsigned long N2[85]{}; const bool fY(){ if (N2[n]==0x123456789abcdef0) return true; if (N4[n]<=_n) return fN(); return false; } const bool fZ(const int w){ if ((w&i)>0){fI(); if (fY()) return true;--n;} if ((w&g)>0){fG(); if (fY()) return true;--n;} if ((w&e)>0){fE(); if (fY()) return true;--n;} if ((w&l)>0){fL(); if (fY()) return true;--n;} return false; } const bool fN(){ switch(N0[n]){case 0: switch(N3[n]){case 'l': return fZ(i); case 'u': return fZ(e); default : return fZ(i+e);} case 3: switch(N3[n]){case 'r': return fZ(i); case 'u': return fZ(l); default : return fZ(i+l);} case 1: case 2: switch(N3[n]){case 'l': return fZ(i+l); case 'r': return fZ(i+e); case 'u': return fZ(e+l); default : return fZ(l+e+i);} case 12: switch(N3[n]){case 'l': return fZ(g); case 'd': return fZ(e); default : return fZ(e+g);} case 15: switch(N3[n]){case 'r': return fZ(g); case 'd': return fZ(l); default : return fZ(g+l);} case 13: case 14: switch(N3[n]){case 'l': return fZ(g+l); case 'r': return fZ(e+g); case 'd': return fZ(e+l); default : return fZ(g+e+l);} case 4: case 8: switch(N3[n]){case 'l': return fZ(i+g); case 'u': return fZ(g+e); case 'd': return fZ(i+e); default : return fZ(i+g+e);} case 7: case 11: switch(N3[n]){case 'd': return fZ(i+l); case 'u': return fZ(g+l); case 'r': return fZ(i+g); default : return fZ(i+g+l);} default: switch(N3[n]){case 'd': return fZ(i+e+l); case 'l': return fZ(i+g+l); case 'r': return fZ(i+g+e); case 'u': return fZ(g+e+l); default : return fZ(i+g+e+l);}} } void fI(){ const int g = (11-N0[n])*4; const unsigned long a = N2[n]&((unsigned long)15<<g); N0[n+1]=N0[n]+4; N2[n+1]=N2[n]-a+(a<<16); N3[n+1]='d'; N4[n+1]=N4[n]+(Nr[a>>g]<=N0[n++]/4?0:1); } void fG(){ const int g = (19-N0[n])*4; const unsigned long a = N2[n]&((unsigned long)15<<g); N0[n+1]=N0[n]-4; N2[n+1]=N2[n]-a+(a>>16); N3[n+1]='u'; N4[n+1]=N4[n]+(Nr[a>>g]>=N0[n++]/4?0:1); } void fE(){ const int g = (14-N0[n])*4; const unsigned long a = N2[n]&((unsigned long)15<<g); N0[n+1]=N0[n]+1; N2[n+1]=N2[n]-a+(a<<4); N3[n+1]='r'; N4[n+1]=N4[n]+(Nc[a>>g]<=N0[n++]%4?0:1); } void fL(){ const int g = (16-N0[n])*4; const unsigned long a = N2[n]&((unsigned long)15<<g); N0[n+1]=N0[n]-1; N2[n+1]=N2[n]-a+(a>>4); N3[n+1]='l'; N4[n+1]=N4[n]+(Nc[a>>g]>=N0[n++]%4?0:1); }
public:
fifteenSolver(int n, unsigned long g){N0[0]=n; N2[0]=g; N4[0]=0;} void Solve(){ if (fN()) {std::cout<<"Solution found in "<<n<<" moves: "; for (int g{1};g<=n;++g) std::cout<<(char)N3[g]; std::cout<<std::endl;} else {n=0; ++_n; Solve();} }
}; </lang>
The Task
<lang cpp> int main (){
fifteenSolver start(8,0xfe169b4c0a73d852); start.Solve();
} </lang>
- Output:
Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd real 0m0.795s user 0m0.794s sys 0m0.000s
Extra Credit
I have updated the 20 random examples, which showed n the number of moves to include _n. As seen when _n is less than 10 the puzzle is solved quickly. This suggests a multi-threading strategy. I have 8 cores available. Modifying solve so that it starts a thread for _n=0 to _n=9, 1 for _n=10, 1 for _n=11, 1 for _n=12, and 1 for _n=13 tests that the fan is still working and turns the computer into a hair-dryer. It also finds the following solution to the extra credit task:
Solution found in 80 moves: dddrurdruuulllddrulddrrruuullddruulldddrrurulldrruulldlddrurullddrrruullulddrdrr
in 29m19.973s.
It also solves the 5th. example which requires 29.3s single threaded in 7s.
F#
<lang fsharp> // A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017 let Nr = [|3;0;0;0;0;1;1;1;1;2;2;2;2;3;3;3|] let Nc = [|3;0;1;2;3;0;1;2;3;0;1;2;3;0;1;2|] let rec Solve n =
let rec fN (i,g,e,l,_) = seq { let fI = let n = (11-g-i*4)*4 let a = (e&&&(15UL<<<n)) (i+1,g,e-a+(a<<<16),'d'::l,Nr.[(int (a>>>n))] <= i) let fG = let n = (19-g-i*4)*4 let a = (e&&&(15UL<<<n)) (i-1,g,e-a+(a>>>16),'u'::l,Nr.[(int (a>>>n))] >= i) let fE = let n = (14-g-i*4)*4 let a = (e&&&(15UL<<<n)) (i,g+1,e-a+(a<<<4), 'r'::l,Nc.[(int (a>>>n))] <= g) let fL = let n = (16-g-i*4)*4 let a = (e&&&(15UL<<<n)) (i,g-1,e-a+(a>>>4), 'l'::l,Nc.[(int (a>>>n))] >= g) let fZ (n,i,g,e,l) = seq{yield (n,i,g,e,l); if l then yield! fN (n,i,g,e,l)} match (i,g,l) with |(0,0,'l'::_) -> yield! fZ fI |(0,0,'u'::_) -> yield! fZ fE |(0,0,_) -> yield! fZ fI; yield! fZ fE |(0,3,'r'::_) -> yield! fZ fI |(0,3,'u'::_) -> yield! fZ fL |(0,3,_) -> yield! fZ fI; yield! fZ fL |(3,0,'l'::_) -> yield! fZ fG |(3,0,'d'::_) -> yield! fZ fE |(3,0,_) -> yield! fZ fE; yield! fZ fG |(3,3,'r'::_) -> yield! fZ fG |(3,3,'d'::_) -> yield! fZ fL |(3,3,_) -> yield! fZ fG; yield! fZ fL |(0,_,'l'::_) -> yield! fZ fI; yield! fZ fL |(0,_,'r'::_) -> yield! fZ fI; yield! fZ fE |(0,_,'u'::_) -> yield! fZ fE; yield! fZ fL |(0,_,_) -> yield! fZ fI; yield! fZ fE; yield! fZ fL |(_,0,'l'::_) -> yield! fZ fI; yield! fZ fG |(_,0,'u'::_) -> yield! fZ fE; yield! fZ fG |(_,0,'d'::_) -> yield! fZ fI; yield! fZ fE |(_,0,_) -> yield! fZ fI; yield! fZ fE; yield! fZ fG |(3,_,'l'::_) -> yield! fZ fG; yield! fZ fL |(3,_,'r'::_) -> yield! fZ fE; yield! fZ fG |(3,_,'d'::_) -> yield! fZ fE; yield! fZ fL |(3,_,_) -> yield! fZ fE; yield! fZ fG; yield! fZ fL |(_,3,'d'::_) -> yield! fZ fI; yield! fZ fL |(_,3,'u'::_) -> yield! fZ fL; yield! fZ fG |(_,3,'r'::_) -> yield! fZ fI; yield! fZ fG |(_,3,_) -> yield! fZ fI; yield! fZ fL; yield! fZ fG |(_,_,'d'::_) -> yield! fZ fI; yield! fZ fE; yield! fZ fL |(_,_,'l'::_) -> yield! fZ fI; yield! fZ fG; yield! fZ fL |(_,_,'r'::_) -> yield! fZ fI; yield! fZ fE; yield! fZ fG |(_,_,'u'::_) -> yield! fZ fE; yield! fZ fG; yield! fZ fL |_ -> yield! fZ fI; yield! fZ fE; yield! fZ fG; yield! fZ fL } let n = Seq.collect fN n match (Seq.tryFind(fun(_,_,n,_,_)->n=0x123456789abcdef0UL)) n with |Some(_,_,_,n,_) -> printf "Solution found with %d moves: " (List.length n); List.iter (string >> printf "%s") (List.rev n); printfn "" |_ -> Solve (Seq.filter(fun (_,_,_,_,n)->not n) n)
Solve [(2,0,0xfe169b4c0a73d852UL,[],false)] </lang>
- Output:
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
Phix
<lang Phix>-- -- demo\rosetta\Solve15puzzle.exw -- constant STM = 0 -- single-tile metrics. constant MTM = 0 -- multi-tile metrics. if STM and MTM then ?9/0 end if -- both prohibited -- 0 0 -- fastest, but non-optimal -- 1 0 -- optimal in STM -- 0 1 -- optimal in MTM (slowest by far)
--Note: The fast method uses an inadmissible heuristic - see "not STM" in iddfs(). -- It explores mtm-style using the higher stm heuristic and may therefore -- fail badly in some cases.
constant SIZE = 4
constant goal = { 1, 2, 3, 4,
5, 6, 7, 8, 9,10,11,12, 13,14,15, 0}
-- -- multi-tile-metric walking distance heuristic lookup (mmwd). -- ========================================================== -- Uses patterns of counts of tiles in/from row/col, eg the solved state -- (ie goal above) could be represented by the following: -- {{4,0,0,0}, -- {0,4,0,0}, -- {0,0,4,0}, -- {0,0,0,3}} -- ie row/col 1 contains 4 tiles from col/row 1, etc. In this case -- both are identical, but you can count row/col or col/row, and then -- add them together. There are up to 24964 possible patterns. The -- blank space is not counted. Note that a vertical move cannot change -- a vertical pattern, ditto horizontal, and basic symmetry means that -- row/col and col/row patterns will match (at least, that is, if they -- are calculated sympathetically), halving the setup cost. -- The data is just the number of moves made before this pattern was -- first encountered, in a breadth-first search, backwards from the -- goal state, until all patterns have been enumerated. -- (The same ideas/vars are now also used for stm metrics when MTM=0) -- sequence wdkey -- one such 4x4 pattern constant mmwd = new_dict() -- lookup table, data is walking distance.
--
-- We use two to-do lists: todo is the current list, and everything
-- of walkingdistance+1 ends up on tdnx. Once todo is exhausted, we
-- swap the dictionary-ids, so tdnx automatically becomes empty.
-- Key is an mmwd pattern as above, and data is {distance,space_idx}.
--
integer todo = new_dict()
integer tdnx = new_dict()
--
enum UP = 1, DOWN = -1
procedure explore(integer space_idx, walking_distance, direction) -- -- Given a space index, explore all the possible moves in direction, -- setting the distance and extending the tdnx table. -- integer tile_idx = space_idx+direction
for group=1 to SIZE do if wdkey[tile_idx][group] then -- ie: check row tile_idx for tiles belonging to rows 1..4 -- Swap one of those tiles with the space wdkey[tile_idx][group] -= 1 wdkey[space_idx][group] += 1
if getd_index(wdkey,mmwd)=0 then -- save the walking distance value setd(wdkey,walking_distance+1,mmwd) -- and add to the todo next list: if getd_index(wdkey,tdnx)!=0 then ?9/0 end if setd(wdkey,{walking_distance+1,tile_idx},tdnx) end if
if MTM then
if tile_idx>1 and tile_idx<SIZE then -- mtm: same direction means same distance: explore(tile_idx, walking_distance, direction) end if
end if
-- Revert the swap so we can look at the next candidate. wdkey[tile_idx][group] += 1 wdkey[space_idx][group] -= 1 end if end for
end procedure
procedure generate_mmwd() -- Perform a breadth-first search begining with the solved puzzle state -- and exploring from there until no more new patterns emerge. integer walking_distance = 0, space = 4
wdkey = {{4,0,0,0}, -- \ {0,4,0,0}, -- } 4 tiles in correct row positions {0,0,4,0}, -- / {0,0,0,3}} -- 3 tiles in correct row position setd(wdkey,walking_distance,mmwd) while 1 do if space<4 then explore(space, walking_distance, UP) end if if space>1 then explore(space, walking_distance, DOWN) end if if dict_size(todo)=0 then if dict_size(tdnx)=0 then exit end if {todo,tdnx} = {tdnx,todo} end if wdkey = getd_partial_key(0,todo) {walking_distance,space} = getd(wdkey,todo) deld(wdkey,todo) end while
end procedure
function walking_distance(sequence puzzle) sequence rkey = repeat(repeat(0,SIZE),SIZE),
ckey = repeat(repeat(0,SIZE),SIZE) integer k = 1 for i=1 to SIZE do -- rows for j=1 to SIZE do -- columns integer tile = puzzle[k] if tile!=0 then integer row = floor((tile-1)/4)+1, col = mod(tile-1,4)+1 rkey[i][row] += 1 ckey[j][col] += 1 end if k += 1 end for end for if getd_index(rkey,mmwd)=0 or getd_index(ckey,mmwd)=0 then ?9/0 -- sanity check end if integer rwd = getd(rkey,mmwd), cwd = getd(ckey,mmwd) return rwd+cwd
end function
sequence puzzle string res = "" atom t0 = time(),
t1 = time()+1
atom tries = 0
constant ok = {{0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1}, -- left
{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1}, -- up {1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0}, -- down {1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0}} -- right
function iddfs(integer step, lim, space, prevmv)
if time()>t1 then printf(1,"working... (depth=%d, tries=%d, time=%3ds)\r",{lim,tries,time()-t0}) t1 = time()+1 end if tries += 1 integer d = iff(step==lim?0:walking_distance(puzzle)) if d=0 then
return (puzzle==goal)
elsif step+d<=lim then
for mv=1 to 4 do -- l/u/d/r if prevmv!=(5-mv) -- not l after r or vice versa, ditto u/d and ok[mv][space] then integer nspace = space+{-1,-4,+4,+1}[mv] integer tile = puzzle[nspace] if puzzle[space]!=0 then ?9/0 end if -- sanity check puzzle[space] = tile puzzle[nspace] = 0 if iddfs(step+iff(MTM or not STM?(prevmv!=mv):1),lim,nspace,mv) then res &= "ludr"[mv] return true end if puzzle[nspace] = tile puzzle[space] = 0 end if end for end if return false
end function
function pack(string s) integer n = length(s), n0 = n
for i=1 to 4 do integer ch = "lrud"[i], k while 1 do k = match(repeat(ch,3),s) if k=0 then exit end if s[k+1..k+2] = "3" n -= 2 end while while 1 do k = match(repeat(ch,2),s) if k=0 then exit end if s[k+1] = '2' n -= 1 end while end for return {n,iff(MTM?sprintf("%d",n):sprintf("%d(%d)",{n,n0})),s}
end function
procedure apply_moves(string moves, integer space) integer move, ch, nspace
puzzle[space] = 0 for i=1 to length(moves) do ch = moves[i] if ch>'3' then move = find(ch,"ulrd") end if -- (hint: "r" -> the 'r' does 1 -- "r2" -> the 'r' does 1, the '2' does 1 -- "r3" -> the 'r' does 1, the '3' does 2!) for j=1 to 1+(ch='3') do nspace = space+{-4,-1,+1,4}[move] puzzle[space] = puzzle[nspace] space = nspace puzzle[nspace] = 0 end for end for
end procedure
function solvable(sequence board) integer n = length(board) sequence positions = repeat(0,n)
-- prepare the mapping from each tile to its position board[find(0,board)] = n for i=1 to n do positions[board[i]] = i end for -- check whether this is an even or odd state integer row = floor((positions[16]-1)/4), col = (positions[16]-1)-row*4 bool even_state = (positions[16]==16) or (mod(row,2)==mod(col,2)) -- count the even cycles integer even_count = 0 sequence visited = repeat(false,16) for i=1 to n do if not visited[i] then -- a new cycle starts at i. Count its length.. integer cycle_length = 0, next_tile = i while not visited[next_tile] do cycle_length +=1 visited[next_tile] = true next_tile = positions[next_tile] end while even_count += (mod(cycle_length,2)==0) end if end for return even_state == (mod(even_count,2)==0)
end function
procedure main()
puzzle = {15,14, 1, 6, 9,11, 4,12, 0,10, 7, 3, 13, 8, 5, 2}
if not solvable(puzzle) then ?puzzle printf(1,"puzzle is not solveable\n") else
generate_mmwd()
sequence original = puzzle integer space = find(0,puzzle)
for lim=walking_distance(puzzle) to iff(MTM?43:80) do if iddfs(0, lim, space, '-') then exit end if end for
{integer n, string ns, string ans} = pack(reverse(res))
printf(1,"\n\noriginal:") ?original atom t = time()-t0 printf(1,"\n%soptimal solution of %s moves found in %s: %s\n\nresult: ", {iff(MTM?"mtm-":iff(STM?"stm-":"non-")),ns,elapsed(t),ans}) puzzle = original apply_moves(ans,space) ?puzzle end if
end procedure main()</lang>
- Output:
original:{15,14,1,6,9,11,4,12,0,10,7,3,13,8,5,2} non-optimal solution of 35(60) moves found in 2.42s: u2r2d3ru2ld2ru3ld3l2u3r2d2l2dru2ldru2rd3lulur3dl2ur2d2 stm-optimal solution of 38(52) moves found in 1 minute and 54s: r3uldlu2ldrurd3lu2lur3dld2ruldlu2rd2lulur2uldr2d2 mtm-optimal solution of 31(60) moves found in 2 hours, 38 minutes and 28s: u2r2d3ru2ld2ru3ld3l2u3r2d2l2dru3rd3l2u2r3dl3dru2r2d2