15 puzzle solver: Difference between revisions
Content added Content deleted
m (→{{header|Wren}}: Minor tidy) |
(Added Uiua solution) |
||
Line 10,556: | Line 10,556: | ||
ddrruldrdlururddluuuldlddrruulldrrruuldlldrrruuldldrrululdlurddlurdrrdllluruurrddldllurdrrulldrurd |
ddrruldrdlururddluuuldlddrruulldrrruuldlldrrruuldldrrululdlurddlurdrrdllluruurrddldllurdrrulldrurd |
||
Total time: 117.666 seconds |
Total time: 117.666 seconds |
||
</pre> |
|||
=={{header|Uiua}}== |
|||
{{Works with |Uiua|0.12.0-dev.1}} Uses experimental `◹` and `astar`. |
|||
This works but it is very, very slow for complex states. |
|||
<syntaxhighlight lang="uiua"> |
|||
# Solve a 15 puzzle |
|||
# Experimental! |
|||
T ← ↯4_4 ↻1⇡16 |
|||
# Return shuffled copy of the input. |
|||
Shuffle ← ⊏⊸(⍏[⍥⚂]⧻) |
|||
# Positions of the numbers (not 0) |
|||
Pos ← ≡(⊢⊚⌕)↘1⇡16¤ |
|||
# Only keep numbers in this row/col which should be in this row/col, |
|||
# (a b) -> check a against b. |
|||
InRightRank ← □▽≡∊⊙¤, |
|||
# For each pair in the wrong order, add two (to a max of six). |
|||
InWrongOrder ← ↧6×2/+◹/+⊞<.▽⊸≠0°□ |
|||
Distance ← /+/+⌵-∩Pos |
|||
Penalties ← +∩(/+≡InWrongOrder≡InRightRank) ∩⍉,, |
|||
# Heuristic distance to goal = sum(manhattan distances) + Penalties |
|||
# (Target Current) -> n |
|||
Heuristic ← +⊃(Penalties|Distance) T |
|||
# Four possible neighbours |
|||
Nfour ← [[1 0] [¯1 0] [0 1] [0 ¯1]] |
|||
# Actual neighbours at a point. |
|||
ValidN ← ≡(⊂)⊙¤:⟜(▽⊸(≥0≡/↧)▽⊸(<4≡/↥)+Nfour)¤ |
|||
# Precalculate them. |
|||
ValidNs ← ⊞(□ ValidN⊟)⇡4 ⇡4 |
|||
# Get the valid (from to) moves from this cell. |
|||
Moves ← °□⊡:ValidNs⊢⊚⌕0 |
|||
# Swap the values at the indexes [0 1] [a b 2 3] -> [b a 2 3] |
|||
Swap ← ⍜(⊡|∘◌) ⊃(⇌⊙∘|⊡) |
|||
# List the possible next positions for a position |
|||
Next ← ⊙◌≡(Swap ⊙.)⊙¤⊸Moves |
|||
# Set up initial puzzle state. |
|||
# ⍥(Swap⊡⊸(⌊×⚂⧻)⊸Moves)90 T # Random shuffle. |
|||
# [[9 1 2 4] [13 6 5 7] [3 11 14 15] [10 0 8 12]] # 34 steps |
|||
[[15 14 1 6] [9 11 4 12] [0 10 7 3] [13 8 5 2]] # Main |
|||
# [[0 12 9 13] [15 11 10 14] [3 7 2 5] [4 8 6 1]] # Extra Credit |
|||
&p"Running..."&p. |
|||
⍜nowastar(Next|Heuristic|≍T) |
|||
&p$"_ seconds" |
|||
# Track the movement of the 0 between adjacent steps. |
|||
≡(/-)◫2◇≡(⊢⊚⌕0)⇌⊢ |
|||
# Map to directions |
|||
/⊂⇌≡⍣("d" °¯1_0|"u" °1_0|"r" °0_¯1|"l" °0_1|∘) |
|||
⊙⊙(&p$"_ seconds"- N now) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
╭─ |
|||
╷ 15 14 1 6 |
|||
9 11 4 12 |
|||
0 10 7 3 |
|||
13 8 5 2 |
|||
╯ |
|||
Running... |
|||
7531.316534996033 seconds |
|||
52 |
|||
"rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd" |
|||
</pre> |
</pre> |
||