A087725
34 views
Skip to first unread message
Michael Spiegel
Sep 3, 2026, 9:06:26 PMSep 3
to SeqFan
Hello,
I believe I am two weeks away from finishing the computation of 156 as a
lower bound of the 5x5 sliding tile puzzle. I am working on a proof that
the "turned 180-degree" puzzle configuration requires 156 single-tile
moves.
The search is an exhaustive IDA* ladder. I have written a solver that
uses three novel variations of Takahashi's Walking Distance heuristic.
The variations are:
- cWD, escape-constrained Walking Distance. Two tiles in the same row
cannot pass each other while both stay in it -- one has to step out and
come back. Those exits are vertical moves, but WD treats a row as an
unordered bag and so charges nothing for them. cWD counts how many tiles
each line is obliged to eject, then asks WD for its cheapest plan that
also makes those exits: the count constrains WD's own move budget
instead of being added on top of it.
- Last-moves Walking Distance. The blank's final one or two steps into its
home corner admit only two endings, or four corridors, each obliging a
named tile to cross a line and return; WD is refined by tracking those
tiles by identity, which its anonymous row and column bags cannot
express. The last-moves idea is Korf & Taylor's (1996) -- pricing it
against a WD abstraction is what is new.
- cLM2, the two combined. Taking the maximum of cWD and the last-two-move
bound never prices their conjunction, so cLM2 evaluates escape demands
and corridor obligations jointly. Restricting that to one demanded line
at a time keeps it a table lookup rather than a search at every node.
These three are where the work is new, and they are what I would most like
scrutinized: the rest of the solver is established technique, but if any one
of these variations is not in fact admissible, the lower bound is wrong.
I would love any feedback, critical reviews, identification of mistakes I
have made, etc. More information about the Walking Distance variations is
at https://github.com/mspiegel/A087725/blob/main/WD.md
My solver uses the following optimizations:
- Iterative, not recursive. Search state lives in a depth-indexed arena
allocated once; there is no call frame to spill across.
- No allocation on the per-node path. The arena and every front cache are
built once per worker and reused across work units and thresholds.
- One axis copied per move, the other shared with an ancestor for the
cost of a one-byte index.
- Move-pruning DFA. Taylor-Korf duplicate elimination (Taylor & Korf,
1993), compiled to a 41,396-state automaton (687 KiB) and folded into
the candidate mask.
- Child pre-prune from the parent's neighbour-WD -- over-bound children
are skipped before being built, with no table probe.
- sigma-orbit split at the root (Culberson & Schaeffer, 1994), halving
the tree on a sigma-symmetric board.
- Additive (Korf & Felner, 2002) 8-tile zero-aware PDBs (Clausecker
& Reinefeld, 2019), each queried in both sigma-views.
- 1 bit per PDB entry (Clausecker & Reinefeld, 2019), not 8 -- distances
reconstructed differentially.
- Lazy cascade: each tier is consulted only at nodes the cheaper ones
failed to prune.
I am using approximately 53,000 core hours on AMD EPYC 9V74 (Genoa) cores
to complete the proof. The computation is expected to complete in two weeks.
More information about the solver, including the source code, is at
https://github.com/mspiegel/A087725
Thank you,
--Michael
Turned 180-degree Puzzle Configuration
. 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1
I believe I am two weeks away from finishing the computation of 156 as a
lower bound of the 5x5 sliding tile puzzle. I am working on a proof that
the "turned 180-degree" puzzle configuration requires 156 single-tile
moves.
The search is an exhaustive IDA* ladder. I have written a solver that
uses three novel variations of Takahashi's Walking Distance heuristic.
The variations are:
- cWD, escape-constrained Walking Distance. Two tiles in the same row
cannot pass each other while both stay in it -- one has to step out and
come back. Those exits are vertical moves, but WD treats a row as an
unordered bag and so charges nothing for them. cWD counts how many tiles
each line is obliged to eject, then asks WD for its cheapest plan that
also makes those exits: the count constrains WD's own move budget
instead of being added on top of it.
- Last-moves Walking Distance. The blank's final one or two steps into its
home corner admit only two endings, or four corridors, each obliging a
named tile to cross a line and return; WD is refined by tracking those
tiles by identity, which its anonymous row and column bags cannot
express. The last-moves idea is Korf & Taylor's (1996) -- pricing it
against a WD abstraction is what is new.
- cLM2, the two combined. Taking the maximum of cWD and the last-two-move
bound never prices their conjunction, so cLM2 evaluates escape demands
and corridor obligations jointly. Restricting that to one demanded line
at a time keeps it a table lookup rather than a search at every node.
These three are where the work is new, and they are what I would most like
scrutinized: the rest of the solver is established technique, but if any one
of these variations is not in fact admissible, the lower bound is wrong.
I would love any feedback, critical reviews, identification of mistakes I
have made, etc. More information about the Walking Distance variations is
at https://github.com/mspiegel/A087725/blob/main/WD.md
My solver uses the following optimizations:
- Iterative, not recursive. Search state lives in a depth-indexed arena
allocated once; there is no call frame to spill across.
- No allocation on the per-node path. The arena and every front cache are
built once per worker and reused across work units and thresholds.
- One axis copied per move, the other shared with an ancestor for the
cost of a one-byte index.
- Move-pruning DFA. Taylor-Korf duplicate elimination (Taylor & Korf,
1993), compiled to a 41,396-state automaton (687 KiB) and folded into
the candidate mask.
- Child pre-prune from the parent's neighbour-WD -- over-bound children
are skipped before being built, with no table probe.
- sigma-orbit split at the root (Culberson & Schaeffer, 1994), halving
the tree on a sigma-symmetric board.
- Additive (Korf & Felner, 2002) 8-tile zero-aware PDBs (Clausecker
& Reinefeld, 2019), each queried in both sigma-views.
- 1 bit per PDB entry (Clausecker & Reinefeld, 2019), not 8 -- distances
reconstructed differentially.
- Lazy cascade: each tier is consulted only at nodes the cheaper ones
failed to prune.
I am using approximately 53,000 core hours on AMD EPYC 9V74 (Genoa) cores
to complete the proof. The computation is expected to complete in two weeks.
More information about the solver, including the source code, is at
https://github.com/mspiegel/A087725
Thank you,
--Michael
Turned 180-degree Puzzle Configuration
. 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1
David Rabahy
Sep 3, 2026, 9:43:19 PMSep 3
to seq...@googlegroups.com
binary: 11, 1100, 1111, 110000, 110011, ...
quaternary: 3, 30, 33, 300, 303, ...
decimal: 3, 12, 15, 96, 99, ...
I practice counting in binary with my fingers (doesn't everyone?). It's led to me thinking about things like binary patterns, like 10, 1010, 101010, ... which is https://oeis.org/A163662; and binary palidromes which is https://oeis.org/A006995; etc. This latest variant is just counting with two fingers at a time, which is naturally just quaternary natural numbers using only 3 and 0 which I didn't find in the OEIS. Worthy, trite, or banal? You won't hurt my feelings.
David Rabahy
Sep 3, 2026, 9:50:23 PMSep 3
to seq...@googlegroups.com
Well, that's embarassing. https://oeis.org/A006995
--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/1960346683.273269.1788486196240%40connect.xfinity.com.
M. F. Hasler
Sep 4, 2026, 9:44:10 AMSep 4
to seq...@googlegroups.com
Le jeu. 3 sept. 2026 à 21:50, 'David Rabahy' via SeqFan <seq...@googlegroups.com> a écrit :
Well, that's embarassing. https://oeis.org/A006995
What's embarrasing there ?
On 09/03/2026 9:43 PM EDT 'David Rabahy' via SeqFan <seq...@googlegroups.com> wrote:binary: 11, 1100, 1111, 110000, 110011, ...quaternary: 3, 30, 33, 300, 303, ...decimal: 3, 12, 15, 96, 99, ...
This latest variant is just counting with two fingers at a time, which is naturally just quaternary natural numbers using only 3 and 0
Why isn't 5 = 0b110 (where prefix 0b means binary) = 0q12 (i.e. in base 4)
included in "counting with two fingers at a time" ?
which I didn't find in the OEIS. Worthy, trite, or banal?
Indeed, the sequence "numbers having only digits 0 or 3 in base 3" isn't in OEIS.
The reason is certainly that all these are multiples of 3, more precisely,
In general, when a sequence is just a multiple of another sequence,
we usually don't add it to the encyclopedia.
(So you should always divide by the gcd of your terms ;
I thought "superseeker" would do that...)
Now I'm guessing, maybe your follow-up message meant to mention A695 in addition to A6995...
(But no need to send another mail to the list just for confirmation or not.)
- Maximilian
- Maximilian
Daniel Mondot
Sep 4, 2026, 10:07:27 AMSep 4
to seq...@googlegroups.com
Because 5 = 0b101 and counting with 2 fingers at a time, in this context means pairs of binary digits have the same value, starting with digit 0&1 having the same value, then 2&3 having the same value, etc... at least that the way I understood it.
--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAFqvfd8pQWRBx%3D4Z2fHXckQaVgua%2B_eYb9%2BHg%2B4iDsq%3Dt2vO2A%40mail.gmail.com.
Reply all
Reply to author
Forward
0 new messages