15 puzzle solver: Difference between revisions
Content added Content deleted
m (→{{header|Uiua}}: Added Uiua Pad link) |
m (→{{header|Uiua}}: Improved algorithm) |
||
Line 10,560: | Line 10,560: | ||
=={{header|Uiua}}== |
=={{header|Uiua}}== |
||
{{Works with |Uiua|0.12.0-dev.1}} Uses experimental `◹` and `astar`. |
{{Works with |Uiua|0.12.0-dev.1}} Uses experimental `◹` and `astar`. |
||
This works but it is very, very slow for complex states. |
|||
[https://www.uiua.org/pad?src=0_12_0-dev_1__IyBTb2x2ZSBhIDE1IHB1enpsZQojIEV4cGVyaW1lbnRhbCEKVCDihpAg4oavNF80IOKGuzHih6ExNgojIFJldHVybiBzaHVmZmxlZCBjb3B5IG9mIHRoZSBpbnB1dC4KU2h1ZmZsZSDihpAg4oqP4oq4KOKNj1vijaXimoJd4qe7KQojIFBvc2l0aW9ucyBvZiB0aGUgbnVtYmVycyAobm90IDApClBvcyDihpAg4omhKOKKouKKmuKMlSnihpgx4oehMTbCpAojIE9ubHkga2VlcCBudW1iZXJzIGluIHRoaXMgcm93L2NvbCB3aGljaCBzaG91bGQgYmUgaW4gdGhpcyByb3cvY29sLAojIChhIGIpIC0-IGNoZWNrIGEgYWdhaW5zdCBiLgpJblJpZ2h0UmFuayDihpAg4pah4pa94omh4oiK4oqZwqQsCiMgRm9yIGVhY2ggcGFpciBpbiB0aGUgd3Jvbmcgb3JkZXIsIGFkZCB0d28gKHRvIGEgbWF4IG9mIHNpeCkuCkluV3JvbmdPcmRlciDihpAg4oanNsOXMi8r4pe5Lyviip48LuKWveKKuOKJoDDCsOKWoQoKRGlzdGFuY2Ug4oaQIC8rLyvijLUt4oipUG9zClBlbmFsdGllcyDihpAgK-KIqSgvK-KJoUluV3JvbmdPcmRlcuKJoUluUmlnaHRSYW5rKSDiiKnijYksLAojIEhldXJpc3RpYyBkaXN0YW5jZSB0byBnb2FsID0gc3VtKG1hbmhhdHRhbiBkaXN0YW5jZXMpICsgUGVuYWx0aWVzCiMgKFRhcmdldCBDdXJyZW50KSAtPiBuCkhldXJpc3RpYyDihpAgK-KKgyhQZW5hbHRpZXN8RGlzdGFuY2UpIFQKCiMgRm91ciBwb3NzaWJsZSBuZWlnaGJvdXJzCk5mb3VyIOKGkCBbWzEgMF0gW8KvMSAwXSBbMCAxXSBbMCDCrzFdXQojIEFjdHVhbCBuZWlnaGJvdXJzIGF0IGEgcG9pbnQuClZhbGlkTiDihpAg4omhKOKKginiipnCpDrin5wo4pa94oq4KOKJpTDiiaEv4oanKeKWveKKuCg8NOKJoS_ihqUpK05mb3VyKcKkCiMgUHJlY2FsY3VsYXRlIHRoZW0uClZhbGlkTnMg4oaQIOKKnijilqEgVmFsaWRO4oqfKeKHoTQg4oehNAoKIyBHZXQgdGhlIHZhbGlkIChmcm9tIHRvKSBtb3ZlcyBmcm9tIHRoaXMgY2VsbC4KTW92ZXMg4oaQIMKw4pah4oqhOlZhbGlkTnPiiqLiiprijJUwCiMgU3dhcCB0aGUgdmFsdWVzIGF0IHRoZSBpbmRleGVzIFswIDFdIFthIGIgMiAzXSAtPiBbYiBhIDIgM10KU3dhcCDihpAg4o2cKOKKoXziiJjil4wpIOKKgyjih4ziipniiJh84oqhKQojIExpc3QgdGhlIHBvc3NpYmxlIG5leHQgcG9zaXRpb25zIGZvciBhIHBvc2l0aW9uCk5leHQg4oaQIOKKmeKXjOKJoShTd2FwIOKKmS4p4oqZwqTiirhNb3ZlcwoKIyBTZXQgdXAgaW5pdGlhbCBwdXp6bGUgc3RhdGUuCuKNpShTd2Fw4oqh4oq4KOKMisOX4pqC4qe7KeKKuE1vdmVzKTkwIFQgIyBSYW5kb20gc2h1ZmZsZS4KIyBbWzkgMSAyIDRdIFsxMyA2IDUgN10gWzMgMTEgMTQgMTVdIFsxMCAwIDggMTJdXSAjIDM0IHN0ZXBzCiMgW1sxNSAxNCAxIDZdIFs5IDExIDQgMTJdIFswIDEwIDcgM10gWzEzIDggNSAyXV0gIyBNYWluCiMgW1swIDEyIDkgMTNdIFsxNSAxMSAxMCAxNF0gWzMgNyAyIDVdIFs0IDggNiAxXV0gIyBFeHRyYSBDcmVkaXQKCiZwIlJ1bm5pbmcuLi4iJnAuCuKNnG5vd2FzdGFyKE5leHR8SGV1cmlzdGljfOKJjVQpCiZwJCJfIHNlY29uZHMiCiMgVHJhY2sgdGhlIG1vdmVtZW50IG9mIHRoZSAwIGJldHdlZW4gYWRqYWNlbnQgc3RlcHMuCuKJoSgvLSnil6sy4peH4omhKOKKouKKmuKMlTAp4oeM4oqiCiMgTWFwIHRvIGRpcmVjdGlvbnMKL-KKguKHjOKJoeKNoygiZCIgwrDCrzFfMHwidSIgwrAxXzB8InIiIMKwMF_CrzF8ImwiIMKwMF8xfOKImCkK Try it in Uiua Pad!] |
|||
[https://www.uiua.org/pad?src=0_12_0-dev_1__IyBTb2x2ZSBhIDE1IHB1enpsZSBodHRwczovL3Jvc2V0dGFjb2RlLm9yZy93aWtpLzE1X3B1enpsZV9zb2x2ZXIjVWl1YQojIEV4cGVyaW1lbnRhbCEKVCDihpAg4oavNF80IOKGuzHih6ExNgojIFJldHVybiBzaHVmZmxlZCBjb3B5IG9mIHRoZSBpbnB1dC4KU2h1ZmZsZSDihpAg4oqP4oq4KOKNj1vijaXimoJd4qe7KQojIFBvc2l0aW9ucyBvZiB0aGUgbnVtYmVycyAobm90IDApClBvcyDihpAg4omhKOKKouKKmuKMlSnihpgx4oehMTbCpAoKIyBBcHBseWluZyBhIHZlcnkgZ2VudGxlIHdlaWdodGluZyB0byBjZXJ0YWluIGNlbGxzIG1hc3NpdmVseQojIHNwZWVkcyB1cCB0aGUgYWxnb3JpdGhtCldlaWdodHMg4oaQIFtbMiAxIDEgMl0gWzIgMSAxIDJdIFsyIDEgMSAyXSBbMiAxIDEgMV1dCkRpc3RhbmNlIOKGkCAvK8OX4oqhOldlaWdodHM64omhLyvijLUt4oqZLuKIqVBvcwpIZXVyaXN0aWMg4oaQIERpc3RhbmNlIFQKCiMgRm91ciBwb3NzaWJsZSBuZWlnaGJvdXJzCk5mb3VyIOKGkCBbWzEgMF0gW8KvMSAwXSBbMCAxXSBbMCDCrzFdXQojIEFjdHVhbCBuZWlnaGJvdXJzIGF0IGEgcG9pbnQuClZhbGlkTiDihpAg4omhKOKKginiipnCpDrin5wo4pa94oq4KOKJpTDiiaEv4oanKeKWveKKuCg8NOKJoS_ihqUpK05mb3VyKcKkCiMgUHJlY2FsY3VsYXRlIHRoZW0uClZhbGlkTnMg4oaQIOKKnijilqEgVmFsaWRO4oqfKeKHoTQg4oehNAoKIyBHZXQgdGhlIHZhbGlkIChmcm9tIHRvKSBtb3ZlcyBmcm9tIHRoaXMgY2VsbC4KTW92ZXMg4oaQIMKw4pah4oqhOlZhbGlkTnPiiqLiiprijJUwCiMgU3dhcCB0aGUgdmFsdWVzIGF0IHRoZSBpbmRleGVzIFswIDFdIFthIGIgMiAzXSAtPiBbYiBhIDIgM10KU3dhcCDihpAg4o2cKOKKoXziiJjil4wpIOKKgyjih4ziipniiJh84oqhKQojIExpc3QgdGhlIHBvc3NpYmxlIG5leHQgcG9zaXRpb25zIGZvciBhIHBvc2l0aW9uCk5leHQg4oaQIOKKmeKXjOKJoShTd2FwIOKKmS4p4oqZwqTiirhNb3ZlcwpTb2x2ZSDihpAgKAogICZwIlJ1bm5pbmcuLi4iJnAuCiAg4o2cbm93YXN0YXIoTmV4dHxIZXVyaXN0aWN84omNVCkKICAmcCQiXyBzZWNvbmRzIgogICMgVHJhY2sgdGhlIG1vdmVtZW50IG9mIHRoZSAwIGJldHdlZW4gYWRqYWNlbnQgc3RlcHMuCiAg4omhKC8tKeKXqzLil4fiiaEo4oqi4oqa4oyVMCnih4ziiqIKICAjIE1hcCBlYWNoIHRvIGEgZGlyZWN0aW9uIHN0cmluZyBhbmQgam9pbi4KICAv4oqC4oeM4omh4o2jKCJkIiDCsMKvMV8wfCJ1IiDCsDFfMHwiciIgwrAwX8KvMXwibCIgwrAwXzF84oiYKQopCgojIFVuY29tbWVudCBvbmUgb2YgdGhlIGZvbGxvd2luZyBsaW5lcyB0byB0cnkgcmFuZG9tIGdyaWRzCiMg4o2lKFN3YXDiiqHiirgo4oyKw5fimoLip7sp4oq4TW92ZXMpOTAgVAojIFtbMiAxNCA2IDRdIFs1IDEgMyA4XSBbOSAxMCA3IDExXSBbMTMgMCAxNSAxMl1dICMgU2ltcGxlIDQwIHNodWZmbGVzCiMgW1s1IDEgMiAzXSBbNiAxMCA3IDRdIFsxMyA5IDExIDhdIFsxNCAwIDE1IDEyXV0gIyBTaW1wbGUgMTIgc3RlcHMKIyBbWzkgMSAyIDRdIFsxMyA2IDUgN10gWzMgMTEgMTQgMTVdIFsxMCAwIDggMTJdXSAjIDM0IHN0ZXBzCiMgW1sxMCAzIDEgNF0gWzEzIDUgOCA3XSBbOSA2IDAgMTFdIFsxNCAxNSAxMiAyXV0gIyAzOCBzdGVwcyAoYSBmZXcgc2Vjb25kcykKW1sxNSAxNCAxIDZdIFs5IDExIDQgMTJdIFswIDEwIDcgM10gWzEzIDggNSAyXV0gIyBNYWluIENoYWxsZW5nZQojIFtbMCAxMiA5IDEzXSBbMTUgMTEgMTAgMTRdIFszIDcgMiA1XSBbNCA4IDYgMV1dICMgRXh0cmEgQ3JlZGl0CgpTb2x2ZQo= Try it in Uiua Pad!] (runs about a third of the speed of native). |
|||
<syntaxhighlight lang="uiua"> |
<syntaxhighlight lang="uiua"> |
||
# Solve a 15 puzzle |
# Solve a 15 puzzle https://rosettacode.org/wiki/15_puzzle_solver#Uiua |
||
# Experimental! |
# Experimental! |
||
T ← ↯4_4 ↻1⇡16 |
T ← ↯4_4 ↻1⇡16 |
||
Line 10,571: | Line 10,571: | ||
# Positions of the numbers (not 0) |
# Positions of the numbers (not 0) |
||
Pos ← ≡(⊢⊚⌕)↘1⇡16¤ |
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°□ |
|||
# Applying a very gentle weighting to certain cells massively |
|||
⚫ | |||
# speeds up the algorithm |
|||
Penalties ← +∩(/+≡InWrongOrder≡InRightRank) ∩⍉,, |
|||
Weights ← [[2 1 1 2] [2 1 1 2] [2 1 1 2] [2 1 1 1]] |
|||
# Heuristic distance to goal = sum(manhattan distances) + Penalties |
|||
⚫ | |||
# (Target Current) -> n |
|||
Heuristic ← |
Heuristic ← Distance T |
||
# Four possible neighbours |
# Four possible neighbours |
||
Line 10,596: | Line 10,591: | ||
# List the possible next positions for a position |
# List the possible next positions for a position |
||
Next ← ⊙◌≡(Swap ⊙.)⊙¤⊸Moves |
Next ← ⊙◌≡(Swap ⊙.)⊙¤⊸Moves |
||
Solve ← ( |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
# Map each to a direction string and join. |
|||
⚫ | |||
) |
|||
# Uncomment one of the following lines to try random grids |
|||
# Set up initial puzzle state. |
|||
# ⍥(Swap⊡⊸(⌊×⚂⧻)⊸Moves)90 T |
# ⍥(Swap⊡⊸(⌊×⚂⧻)⊸Moves)90 T |
||
# [[2 14 6 4] [5 1 3 8] [9 10 7 11] [13 0 15 12]] # Simple 40 shuffles |
|||
# [[5 1 2 3] [6 10 7 4] [13 9 11 8] [14 0 15 12]] # Simple 12 steps |
|||
# [[9 1 2 4] [13 6 5 7] [3 11 14 15] [10 0 8 12]] # 34 steps |
# [[9 1 2 4] [13 6 5 7] [3 11 14 15] [10 0 8 12]] # 34 steps |
||
[[ |
# [[10 3 1 4] [13 5 8 7] [9 6 0 11] [14 15 12 2]] # 38 steps (a few seconds) |
||
[[15 14 1 6] [9 11 4 12] [0 10 7 3] [13 8 5 2]] # Main Challenge |
|||
# [[0 12 9 13] [15 11 10 14] [3 7 2 5] [4 8 6 1]] # Extra Credit |
# [[0 12 9 13] [15 11 10 14] [3 7 2 5] [4 8 6 1]] # Extra Credit |
||
Solve |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
# Map to directions |
|||
⚫ | |||
</syntaxhighlight> |
</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,620: | Line 10,621: | ||
╯ |
╯ |
||
Running... |
Running... |
||
7.321068048477173 seconds |
|||
52 |
52 |
||
"rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd" |
"rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd" |