Hi
Afmob,
I try to code a BFS search like you suggest, maybe it will help? At least for the subset method, your suggestion made my code three times faster.
This is a bit of a ramble, but ...
The things I'm tracking, are a bitmask of solvable cells, and a bitmask of clues that if added, would cause one of the other clues to be redundant. Like with the subsets code, there is some code to feed "solvable cells" and "would cause a redundancy" masks, forward to the next depth. An early (?) test on puzzles at a given depth, is that if ancestor puzzles caused both flags to be set for the same cell, then the new puzzle isn't minimal. I think the (rest of) the minimality testing, actually comes last (now) in the tests at a given depth, since minimal or not, "solvable cell" information from the puzzle can be fed forward to the next depth.
The solver is called at all stages in the BFS process, and the code has some bits to track recent solutions from "is this cell solvable" tests ... "2nd" solutions where that cell value differs from the value in the designated solution. The "recent history" lists, let me skip solver calls at times, and the cells where the other solution differs from the designated solution, represent (additional) cells that can be flagged as "not solvable" -- cells that can be skipped in the process of finalizing a mask of solvable cells. UA sets are used too, to do an early collection of non-solvable cells.
The main speedup from UA sets (I think), was that if a UA set gets to the point where none of its clues cells have been added, and every clue is flagged as causing a redundancy if added, then the puzzle (minimal or not) can have no extension to a complete minimal puzzle. I don't use all of the UA sets, just the ones that are disjoint from the initial subgrid, and can be found in a quick initial scan.
My code is still somewhat of a mess, so I can't say much more than that -- fingers crossed, that I didn't mislead you above.
I need to find time this weekend, to go over it in detail.
Good luck, and have fun !
Another bottleneck in my algorithms is the random grid generation. I coded the linear probing method and in 10 minutes I only generated about 10 millions solutions grids where as Red Ed got about 21 million and you even got 47 million solution grids.
This seems to be less of a problem for the supersets method.
I have some (very old) code that can generate ~600
(correction) thousand grids per second.
It uses some large lookup tables, produced from a method for counting the ~6e+21 solution grids.
(If you can count them, you can reverse engineer the process, and use it to generate them with uniform probablity).
Best Regards,
Blue.
P.S. I forgot to add that I was
very impressed that on a first try, you were able to get the results that you did, in 16 hours.
Very well done
It took me a long time to get my code to anywhere near that point.