PiJohn & PrintTinker
PiJohn PiJohn
PrintTinker PrintTinker
PiJohn PiJohn
I’ve been looking at the 15‑puzzle’s permutation group and I think we can derive an algorithm that finds a minimal solution faster than the usual A*. What do you think about turning that into a quick‑look solver you can drop into your workflow?
PrintTinker PrintTinker
That’s an interesting idea, but a quick‑look solver usually ends up being a brute‑force fallback that’s slower than a well‑tuned A* with pattern databases. If you really want to drop something into a script, consider an IDA* implementation that uses a precomputed Manhattan + linear conflict heuristic, then add a tiny cache for already‑seen states. Keep the state representation compact—bit‑packed 4‑by‑4 array is faster than a list of tuples. Also, expose the solver as a command‑line tool so you can pipe it into other workflows; no need to build a full GUI. If you’re worried about minimality, remember that proving optimality on the fly is expensive—just return the best solution found within a time budget and let the user decide if that’s good enough.
PiJohn PiJohn
That’s a solid plan, and I agree a cache can shave a lot off the search. I’ll sketch a minimal prototype: a 4‑byte array for the board, a fast hash for visited states, and an IDA* loop that stops when the cost exceeds a set bound. I’ll also throw in a quick sanity check on the Manhattan + linear conflict values so we don’t waste time on obviously doomed paths. I’ll expose it as a tiny CLI that reads a 16‑char string from stdin and prints moves, so you can shell it into whatever pipeline you need. If you want the solver to be more “academic” you can add a flag that runs a full pattern‑database A* just to confirm optimality. Sound good?
PrintTinker PrintTinker
Sounds solid, but just a heads‑up: a 4‑byte array can’t hold the 16 tiles unless you pack 4 bits per tile, which is doable but adds overhead. A 16‑byte array or a 64‑bit integer bit‑pack is simpler and faster for hashing. Also make sure your hash table uses open addressing to keep cache locality high. The sanity check on Manhattan + linear conflict is great – it prunes a lot of dead branches. And the CLI hook is perfect for scripts. If you add the optional pattern‑DB A* flag, remember to store the DBs on disk and load them lazily; loading a full DB every run kills throughput. All in all, good plan.
PiJohn PiJohn
Thanks for the nitpicks—good points on the bit‑packing and hash table design. I’ll switch to a 64‑bit packed state for the hash, use linear probing for the table, and make the pattern‑DB loader lazy so the first run pays the cost and subsequent runs reuse the memory. I’ll also add a verbosity flag so you can watch the pruning statistics if you want to tweak the heuristics. That should keep the pipeline snappy and the code clean.
PrintTinker PrintTinker
Nice. 64‑bit packing keeps the state tiny, linear probing keeps cache hits, lazy DB loading avoids a startup hiccup. A verbosity flag is a good sanity check – you’ll see the hit ratio of your heuristic and whether the pattern‑DB is really worth the extra memory. Keep the code modular so you can swap in a different heuristic later without touching the CLI. If anyone complains about “too many flags,” just point them to the README; a well‑documented tool is the best kind of open‑source evangelist.
PiJohn PiJohn
Sounds like a plan—happy to hand over the clean, modular code once I finish polishing the tests. Let me know if you want a quick walkthrough of the architecture before I push it.
PrintTinker PrintTinker
Sure, a quick walkthrough would be great.
PiJohn PiJohn
Sure, here’s a quick tour: the CLI parses a 16‑char string or file, builds a 64‑bit packed state and passes it to the solver module. The solver module contains the core IDA* loop, a linear‑conflict + Manhattan helper, and the open‑addressing hash set for pruning. If you enable the pattern‑DB flag, the DB loader reads a lazily‑loaded file into a memory‑mapped array, so the first search builds the cache and later ones hit it instantly. All of this is wired together by a thin driver that just forwards options; you can swap out the heuristic function or replace the hash table without touching the command line code. The README explains each flag and gives an example pipeline.