15 puzzle solver: Difference between revisions
m
syntax highlighting fixup automation
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 39:
{{trans|Nim}}
<
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]
Line 122:
0, 10, 7, 3,
13, 8, 5, 2])
solver.run()</
{{out}}
Line 131:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program puzzle15solvex64.s */
Line 1,151:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
<pre>
File name : casR1.txt
Line 1,172:
=={{header|Ada}}==
{{trans|C++}} Decoding actually...
<
procedure Puzzle_15 is
Line 1,363:
(0, 10, 7, 3),
(13, 8, 5, 2)));
end Puzzle_15;</
{{out}}
<pre>Solved in 52 moves: RRRULDDLUUULDRURDDDRULLULURRRDDLDLUURDDLULURRULDRDRD</pre>
Line 1,369:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<
/* ARM assembly Raspberry PI */
/* program puzzle15solver.s */
Line 2,311:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
<pre>
Nom du fichier : casR1.txt
Line 2,332:
=={{header|C}}==
===IDA*===
<syntaxhighlight lang=C>
/**@file HybridIDA.c
* @brief solve 4x4 sliding puzzle with IDA* algorithm
Line 2,619:
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,659:
[http://www.rosettacode.org/wiki/15_puzzle_solver/20_Random see] for an analysis of 20 randomly generated 15 puzzles solved with this solver.
====The Solver====
<
// Solve Random 15 Puzzles : Nigel Galloway - October 18th., 2017
class fifteenSolver{
Line 2,701:
void Solve(){for(;not fY();++_n);}
};
</syntaxhighlight>
====The Task====
<
int main (){
fifteenSolver start(8,0xfe169b4c0a73d852);
start.Solve();
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,718:
====Extra Credit====
<
int main (){
fifteenSolver start(0,0x0c9dfbae37254861);
start.Solve();
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,737:
Using an A* search algorithm which is good enough for the first task. I increased SBCL's dynamic memory to 2GB for the code to run smoothly.
<
(eval-when (:load-toplevel :compile-toplevel :execute)
(ql:quickload "pileup"))
Line 3,068:
(format t "Found the shortest path in ~D steps and ~3,2F seconds~%" result time))
(print-state goal-state))
</syntaxhighlight>
{{out}}
Line 3,088:
=={{header|F_Sharp|F#}}==
===The Function===
<
// A Naive 15 puzzle solver using no memory. Nigel Galloway: October 6th., 2017
let Nr,Nc = [|3;0;0;0;0;1;1;1;1;2;2;2;2;3;3;3|],[|3;0;1;2;3;0;1;2;3;0;1;2;3;0;1;2|]
Line 3,111:
solve {i=n;g=[L];e=g;l=0}
let n = Seq.collect fN n
</syntaxhighlight>
===The Task===
<
let test n g=match [1..15]|>Seq.tryPick(solve n g) with
Some n->n|>List.rev|>List.iter(fun n->printf "%c" (match n with N->'d'|I->'u'|G->'r'|E->'l'|L->'\u0000'));printfn " (%n moves)" (List.length n)
|_ ->printfn "No solution found"
test 0xfe169b4c0a73d852UL 8
</syntaxhighlight>
{{out}}
<pre>
Line 3,128:
The code tested with gforth 0.7.2. It required a 64-bit system.
<
#! /usr/bin/gforth
Line 3,194:
\ -1 0 hex 123456789afbde0c decimal 14 solve \ some trivial case, 3 moves
bye
</syntaxhighlight>
{{out}}
Line 3,289:
(The source below has the ABS outside the MOD: I don't care [[Talk:Carmichael_3_strong_pseudoprimes|what sort of mod]] is used here, just that negative numbers be as scrambled as positive) In both cases the array indexing is checkable by the compiler at compile time so that there need be no run-time checking on that. Such bound checking may be not as strict as might be expected when EQUIVALENCE tricks are involved. In tests with a variant board size of 3x4, the board position array was declared BOARD(N) where N = 12, but was still equivalenced to BORED(4) and so still allowed room for sixteen elements in BOARD. Subroutine UNPACK was not written to deal with anything other than a 4x4 board and so accessed elements 13, 14, 15, and 16 of BOARD that were outside its declared upper bound of 12, but no run-time objection was made. Similarly with a 3x3 board.
Granted a flexible pre-processor scheme (as in pl/i, say) one could imagine a menu of tricks being selected from according to the board shape specified, but without such a facility, the constants are merely named rather than literal. Any change, such as to a 3x4 board, can be made by adjusting the appropriate PARAMETER and many usages will adjust accordingly. Others will require adjustment by the diligent programmer for good results. In the absence of a pre-processor one could present the various possible code sequences surrounded by tests as in <
code specialised for NR = 4
ELSE IF (NR.EQ.3) THEN
code specialised for NR = 3
END IF</
and hope that the compiler would carry forward the actual value of <code>NR</code> into the IF-statement's conditional expression, recognise that the result is also constant (for the current compilation with a particular value of <code>NR</code>) and so generate code only for the case that the expression came out as ''true'', without any test to select this being employed in the compiled code. This soon becomes a tangle of combinations, and has not been attempted. And there could be difficulties too. One wonders if, say, with NR = 3, the specialised code for the NR = 4 case could contain a mention of element 4 of an array which is actually of size NR. Would the compiler regard this as an error, given that it will be discarding this code anyway? Even if one used NR rather than a literal such as 4 there could still be problems, such as code calling for a division by (NR - 3).
Line 3,301:
===Source===
<
DOUBLE PRECISION T !The time, in seconds. Positive only, please.
DOUBLE PRECISION S !A copy I can mess with.
Line 3,829:
CALL PURPLE HAZE(FNAME(1:14))
END</
===The Results===
Line 4,571:
=={{header|Go}}==
{{trans|C++}}
<
import "fmt"
Line 4,812:
fifteenSolver(8, 0xfe169b4c0a73d852)
solve()
}</
{{out}}
Line 4,821:
=={{header|Julia}}==
{{trans|C++}}
<
const Nc = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2]
Line 5,035:
run() = (N0[1] = 8; _n[1] = 1; N2[1] = 0xfe169b4c0a73d852; solve(0))
run()
</
{{output}} <pre>
next iteration, _n[1] will be 2...
Line 5,050:
=={{header|Lua}}==
===Original===
<
#!/usr/bin/lua
--[[
Line 5,275:
print_tiles(Goal)
solve(Tiles);
</syntaxhighlight>
{{output}} <pre>
FOUND SOLUTION of length 52 rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
Line 5,281:
===Alternate (with extra credit)===
<
----------
-- SOLVER
Line 5,485:
print("ELAPSED: " .. (os.clock()-sclock) .. "s")
end
</syntaxhighlight>
{{out}}
<pre>
Line 5,538:
{{trans|C++}}
====The solver====
<
# 15 puzzle.
Line 5,679:
ms = ms mod d
if ms > 0: result.add(' ')
</syntaxhighlight>
====The task====
<
let start = getTime()
var solver = initSolver([Value 15, 14, 1, 6,
Line 5,690:
solver.run()
echo fmt"Execution time: {(getTime() - start).toString}."
</syntaxhighlight>
{{out}}
<pre>
Line 5,697:
</pre>
====Extra credit====
<
let start = getTime()
var solver = initSolver([Value 0, 12, 9, 13,
Line 5,705:
solver.run()
echo fmt"Execution time: {(getTime() - start).toString}."
</syntaxhighlight>
{{out}}
<pre>
Line 5,714:
=={{header|Pascal}}==
===The Solver===
<
unit FifteenSolverT;
\\ Solve 15 Puzzle. Nigel Galloway; February 1st., 2019.
Line 5,746:
end;
end.
</syntaxhighlight>
<
// Threaded use of 15 solver Unit. Nigel Galloway; February 1st., 2019.
program testFifteenSolver;
Line 5,779:
end;
end.
</syntaxhighlight>
===The Task===
{{out}}
Line 5,797:
=={{header|Picat}}==
<
main =>
Line 5,854:
{(R,C),(FR,FC)} in zip(Tiles,FTiles)]).
</syntaxhighlight>
{{out}}
Line 5,863:
=={{header|Perl}}==
{{trans|Raku}}
<
no warnings;
Line 5,924:
($N0[0], $N2[0]) = (8, 0xfe169b4c0a73d852); # initial state
while () { fY() or ++$m }</
{{out}}
<pre>Solution found in 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd</pre>
=={{header|Phix}}==
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Solve15puzzle.exw</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">STM</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- single-tile metrics.</span>
Line 6,080:
<span style="color: #0000FF;">{<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- down</span>
<span style="color: #0000FF;">{<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #000000;">0<span style="color: #0000FF;">}<span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- right
<!--</
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">iddfs<span style="color: #0000FF;">(<span style="color: #004080;">integer</span> <span style="color: #000000;">step<span style="color: #0000FF;">,</span> <span style="color: #000000;">lim<span style="color: #0000FF;">,</span> <span style="color: #000000;">space<span style="color: #0000FF;">,</span> <span style="color: #000000;">prevmv<span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
Line 6,223:
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main<span style="color: #0000FF;">(<span style="color: #0000FF;">)
<!--</
{{out}}
<pre>
Line 6,240:
-- (clearly optimal by exhaustively disproving all lesser n)
<!--<
<span style="color: #000080;font-style:italic;">-- demo/rosetta/Solve15puzzle_simple.exw</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">left<span style="color: #0000FF;">,</span> <span style="color: #000000;">down<span style="color: #0000FF;">,</span> <span style="color: #000000;">up<span style="color: #0000FF;">,</span> <span style="color: #000000;">right</span> <span style="color: #000080;font-style:italic;">-- (nb 5-move flips it, as in down===5-up, etc)</span>
Line 6,368:
<span style="color: #7060A8;">printf<span style="color: #0000FF;">(<span style="color: #000000;">1<span style="color: #0000FF;">,<span style="color: #008000;">"solution of %d moves found in %s: %s\n"<span style="color: #0000FF;">,</span>
<span style="color: #0000FF;">{<span style="color: #7060A8;">length<span style="color: #0000FF;">(<span style="color: #000000;">moves<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #7060A8;">elapsed<span style="color: #0000FF;">(<span style="color: #7060A8;">time<span style="color: #0000FF;">(<span style="color: #0000FF;">)<span style="color: #0000FF;">-<span style="color: #000000;">t0<span style="color: #0000FF;">)<span style="color: #0000FF;">,<span style="color: #000000;">moves<span style="color: #0000FF;">}<span style="color: #0000FF;">)
<!--</
{{out}}
uppercase indicates the non-free moves (in manhattan cost terms).
Line 6,383:
Works with PowerBASIC 6 Console Compiler
{{trans|Go}}
<
' Test not completed with 0c9dfbae37254861 (still running after about 4 hours).
' Most of initialization is done in procedure fifteenSolver(), so it's possible to call it many times from the main function.
Line 6,850:
'call fifteenSolver(&h0c9dfbae37254861, 1000)
end function
</syntaxhighlight>
=={{header|Python}}==
Line 6,860:
Modified to run this task's 52 move problem.
<
import random
Line 7,047:
print(", ".join({-1: "Left", 1: "Right", -4: "Up", 4: "Down"}[move[1]] for move in moves))
print(cost, num_eval)
</syntaxhighlight>
Output - this solution of the problem for this task is the same as the second solution:
Line 7,066:
===A* with good heuristic===
;File - astar.py
<
"""
Line 7,907:
return strpath
</syntaxhighlight>
;File - testone.py
<
"""
Line 7,950:
print(" ")
print("Run time in seconds: "+str(after - before))
</syntaxhighlight>
Output:
Line 7,973:
</pre>
=={{header|Racket}}==
<
#lang racket
Line 8,294:
(module+ main
(print-path (A* initial-state)))
</syntaxhighlight>
=={{header|Raku}}==
{{trans|C++}}
<
constant \Nr = <3 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3>;
Line 8,366:
fifteenSolver(8,0xfe169b4c0a73d852);
loop { fY() or ++$m }
</syntaxhighlight>
{{out}}
<pre>
Line 8,374:
=={{header|Rust}}==
{{trans|C++}}
<
const NC: [i32; 16] = [3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2];
Line 8,575:
fn main() {
FifteenSolver::new(8, 0xfe169b4c0a73d852).solve();
}</
{{out}}
Line 8,581:
=== alternative ===
<
use std::cmp::{Ord, Ordering, PartialOrd, Reverse};
Line 8,746:
closed_states.push(parent_order, Reverse(parent_state));
}
}</
{{out}}
Line 8,769:
===Implementation===
<
case class Board(table: Array[Int], r: Int, c: Int, parent: List[String] = List()) {
def cloneSwap(r: Int, c: Int, rr: Int, cc: Int) = {
Line 8,866:
val startHard = Board(Array(Array(0, 12, 9, 13), Array(15, 11, 10, 14), Array(3, 7, 2, 5), Array(4, 8, 6, 1)).flatten, 0, 0)
}
</syntaxhighlight>
===Results===
Line 8,914:
{{libheader|Wren-long}}
This works but is very slow (132 seconds).
<
var Nr = [3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3]
Line 9,088:
fifteenSolver.call(8, ULong.fromBaseString("fe169b4c0a73d852", 16))
solve.call()</
{{out}}
|