15 puzzle solver: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: twiddles) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 36: | Line 36: | ||
* [[A* search algorithm]] |
* [[A* search algorithm]] |
||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Nim}} |
|||
<lang 11l>-V |
|||
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] |
|||
T Solver |
|||
n = 0 |
|||
np = 0 |
|||
n0 = [0] * 100 |
|||
n2 = [UInt64(0)] * 100 |
|||
n3 = [Char("\0")] * 100 |
|||
n4 = [0] * 100 |
|||
F (values) |
|||
.n0[0] = values.index(0) |
|||
UInt64 tmp = 0 |
|||
L(val) values |
|||
tmp = (tmp << 4) [|] val |
|||
.n2[0] = tmp |
|||
F fI() |
|||
V n = .n |
|||
V g = (11 - .n0[n]) * 4 |
|||
V a = .n2[n] [&] (UInt64(15) << g) |
|||
.n0[n + 1] = .n0[n] + 4 |
|||
.n2[n + 1] = .n2[n] - a + (a << 16) |
|||
.n3[n + 1] = Char(‘d’) |
|||
.n4[n + 1] = .n4[n] + Int(Nr[Int(a >> g)] > .n0[n] I/ 4) |
|||
F fG() |
|||
V n = .n |
|||
V g = (19 - .n0[n]) * 4 |
|||
V a = .n2[n] [&] (UInt64(15) << g) |
|||
.n0[n + 1] = .n0[n] - 4 |
|||
.n2[n + 1] = .n2[n] - a + (a >> 16) |
|||
.n3[n + 1] = Char(‘u’) |
|||
.n4[n + 1] = .n4[n] + Int(Nr[Int(a >> g)] < .n0[n] I/ 4) |
|||
F fE() |
|||
V n = .n |
|||
V g = (14 - .n0[n]) * 4 |
|||
V a = .n2[n] [&] (UInt64(15) << g) |
|||
.n0[n + 1] = .n0[n] + 1 |
|||
.n2[n + 1] = .n2[n] - a + (a << 4) |
|||
.n3[n + 1] = Char(‘r’) |
|||
.n4[n + 1] = .n4[n] + Int(Nc[Int(a >> g)] > .n0[n] % 4) |
|||
F fL() |
|||
V n = .n |
|||
V g = (16 - .n0[n]) * 4 |
|||
V a = .n2[n] [&] (UInt64(15) << g) |
|||
.n0[n + 1] = .n0[n] - 1 |
|||
.n2[n + 1] = .n2[n] - a + (a >> 4) |
|||
.n3[n + 1] = Char(‘l’) |
|||
.n4[n + 1] = .n4[n] + Int(Nc[Int(a >> g)] < .n0[n] % 4) |
|||
F fY() |
|||
I .n2[.n] == 1234'5678'9ABC'DEF0 |
|||
R 1B |
|||
I .n4[.n] <= .np |
|||
R .fN() |
|||
R 0B |
|||
F fN() -> Bool |
|||
V n = .n |
|||
I .n3[n] != ‘u’ & .n0[n] I/ 4 < 3 {.fI(); .n++; I .fY() {R 1B}; .n--} |
|||
I .n3[n] != ‘d’ & .n0[n] I/ 4 > 0 {.fG(); .n++; I .fY() {R 1B}; .n--} |
|||
I .n3[n] != ‘l’ & .n0[n] % 4 < 3 {.fE(); .n++; I .fY() {R 1B}; .n--} |
|||
I .n3[n] != ‘r’ & .n0[n] % 4 > 0 {.fL(); .n++; I .fY() {R 1B}; .n--} |
|||
R 0B |
|||
F run() |
|||
L !.fY() |
|||
.np++ |
|||
print(‘Solution found with ’(.n)‘ moves: ’, end' ‘’) |
|||
L(g) 1 .. .n |
|||
print(.n3[g], end' ‘’) |
|||
print(‘.’) |
|||
V solver = Solver([15, 14, 1, 6, |
|||
9, 11, 4, 12, |
|||
0, 10, 7, 3, |
|||
13, 8, 5, 2]) |
|||
solver.run()</lang> |
|||
{{out}} |
|||
<pre> |
|||
Solution found with 52 moves: rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd. |
|||
</pre> |
|||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |