15 puzzle solver: Difference between revisions

Content added Content deleted

Inline

@@ Line 10,556: / Line 10,556: @@
 ddrruldrdlururddluuuldlddrruulldrrruuldlldrrruuldldrrululdlurddlurdrrdllluruurrddldllurdrrulldrurd
 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
+11 4 12
+10 7  3
+8 5  2
+             ╯
+Running...
+.316534996033 seconds
+"rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd"
 </pre>