deepSubDiver
Regular
Ugh, how come you remember? It's ages ago when I posted and worked on it.I'm planning to revamp the tips system. Your suggestion is now in my to do list.
Now my request: can you describe how your square-1 solver works? How the search tree is pruned? How much memory does it consume? How long is the preprocessing? What is the average time for a single solution?
The basic concept was using parity to get rid of the incorrect solution paths, which are partly fetched before the actual bidirectional bfs search.
Transition and pruning tables are merged into 3 distinct tables (separation and parity, permutation, shape). I use some weird heap structure for them (inserting O(1), fetching the smallest paths O(log n). Having them base-encoded (minimally) and zipped, they use about 1.1 GB HDD space.
Because fetching the smallest path requires removing (O(log n)) nodes, the memory usage increases due to duplicate temporary tables up to around 3GB RAM.
Preprocessing these tables took at least 6 hours (did it during night and was somewhere at the highest depth when I woke up), I don't know the exact time though.
[edit] Oh, and it takes around 15 seconds each solution.
If you're interested and manage to get my old machine running I can send you the (.NET) sources. It's all embedded in a big web service application though, but I'm sure you have no problem with that.
Last edited:
