468 karma · joined July 17, 2021
One can think of the set of all possible board configurations as the vertices as a graph, with edges indicating how to move between configurations. Then your 1536 solutions are the 1536 distinct shortest paths between the starting and target configuration.
Then, you can also choose to consider not just board configurations, but board configurations up to simultaneous permutation of rows and columns; that will also reduce the number of unique solutions.
I know of some work on trying out various heuristics for A*; Section 5 of https://arxiv.org/pdf/2201.06508 gives some examples of what works and what doesn't. I don't think D* Lite specifically has ever featured. There's plenty of room for trying to come up with other heuristics, and just for other takes in general.
> But for bigger boards you won't be able to materialize the whole graph.
If we restrict to boards corresponding to solvable puzzles, the number of vertices is https://oeis.org/A002884 (1, 1, 6, 168, 20160, 9999360, 20158709760, …) and indeed grows quickly. It's possible to manipulate the 7×7 case (https://arxiv.org/abs/2503.01467, shameless plug) but anything bigger than that seems hard.
One can ask, for example, how many moves are needed for the hardest n×n Swapple. For n = 1, …, 7 the answers are 0, 3, 6, 9, 12, 15, 18 respectively, but we don't know what the answer is for n = 8.
Compare https://adventofcode.com/2024/leaderboard/day/1 to e.g. https://fuglede.github.io/aoc-full-leaderboard/
There was also at least one instance of people working together where you would have 15 people from the same company submit solutions at the same time, which can be a bit frustrating but again, not a huge issue.
Something weird happened with this post. It appeared in a shadow banned sort of form (maybe because of the Unicode superscript?) so I made the other one instead, but now this one actually appeared. Mods should feel free to delete this; I don't think I can do so myself.
> because GIMPS always at least eventually gives out numbers to multiple people to check
For the 40th Mersenne prime, 2²⁰⁹⁹⁶⁰¹¹ − 1, for example, the status page on mersenne.org seems to suggest only a single check (and a handful of later NF checks later), but maybe follow-up proofs and proof certifications and reruns are omitted? https://www.mersenne.org/report_exponent/?exp_lo=20996011&fu...
Also, when you sign up, you're asked to provide an email address in case they want to get in touch with you, so even if OP didn't themselves do so, I imagine they would include their work just the same?
> However, your name could have ended up on that Wikipedia list as a discoverer. :-)
Along the same lines, since each (potential) prime is being worked on by many computers, some looking for factors, some running the Fermat test, some running proof certification work, who gets the "discoverer" title; just the person who ran the PRP test? If so, seems fair enough, since that's where most of the computational budget ends up, but on the other hand, it seems like that would disincentivize running anything but PRP tests. But maybe the people involved are just in it for the mission (or the GHz day leaderboards).
"Once upon a time!!!!!!!!!!!!!!!!!!!!!!!!!!!!!SEED42!!!!!??!!!??!"
and 3) actually just allow you to override the suggestions by typing what letters on your own, to be used in future inferences. At that point it'd be a fairly generic auto-complete kind of thing.