Generating a medium or tough sudoku takes forever

[samifruit514]

./dokugen -d medium -csv -g                                                                                                                                          
2016/04/13 08:53:35 Using difficulty max: 0.7 min: 0.6
2016/04/13 08:53:45 Rejecting grid of difficulty 0.20277861738626868
2016/04/13 08:53:45 Stored the puzzle for future use.
2016/04/13 08:53:45 Attempt 1 at generating puzzle.
2016/04/13 08:53:57 Rejecting grid of difficulty 0.45672840546233473
2016/04/13 08:53:57 Stored the puzzle for future use.
2016/04/13 08:53:57 Attempt 2 at generating puzzle.
2016/04/13 08:54:12 Rejecting grid of difficulty 0.39141150772385497
2016/04/13 08:54:12 Stored the puzzle for future use.
2016/04/13 08:54:12 Attempt 3 at generating puzzle.
2016/04/13 08:54:20 Rejecting grid of difficulty 0.1335769842873176
2016/04/13 08:54:20 Stored the puzzle for future use.
2016/04/13 08:54:20 Attempt 4 at generating puzzle.
2016/04/13 08:54:36 Rejecting grid of difficulty 0.26831964742664755
2016/04/13 08:54:36 Stored the puzzle for future use.
2016/04/13 08:54:36 Attempt 5 at generating puzzle.
2016/04/13 08:54:41 Rejecting grid of difficulty 0.15445928731762051
2016/04/13 08:54:41 Stored the puzzle for future use.
2016/04/13 08:54:41 Attempt 6 at generating puzzle.
2016/04/13 08:54:54 Rejecting grid of difficulty 0.16378679261800394
2016/04/13 08:54:54 Stored the puzzle for future use.
2016/04/13 08:54:54 Attempt 7 at generating puzzle.
2016/04/13 08:55:00 Rejecting grid of difficulty 0.39365513169203264
2016/04/13 08:55:00 Stored the puzzle for future use.
2016/04/13 08:55:00 Attempt 8 at generating puzzle.
2016/04/13 08:55:09 Rejecting grid of difficulty 0.15255952186744873
2016/04/13 08:55:09 Stored the puzzle for future use.
2016/04/13 08:55:09 Attempt 9 at generating puzzle.
2016/04/13 08:55:40 Rejecting grid of difficulty 0.4952128335613479
2016/04/13 08:55:40 Stored the puzzle for future use.
2016/04/13 08:55:40 Attempt 10 at generating puzzle.
2016/04/13 08:55:53 Rejecting grid of difficulty 0.3926094974589889
2016/04/13 08:55:53 Stored the puzzle for future use.
2016/04/13 08:55:53 Attempt 11 at generating puzzle.
2016/04/13 08:56:01 Rejecting grid of difficulty 0.11182446075005824
2016/04/13 08:56:01 Stored the puzzle for future use.
2016/04/13 08:56:01 Attempt 12 at generating puzzle.
2016/04/13 08:56:50 Rejecting grid of difficulty 0.20817310745207168
2016/04/13 08:56:50 Stored the puzzle for future use.
2016/04/13 08:56:50 Attempt 13 at generating puzzle.
2016/04/13 08:57:03 Rejecting grid of difficulty 0.46890243276389
2016/04/13 08:57:03 Stored the puzzle for future use.
2016/04/13 08:57:03 Attempt 14 at generating puzzle.
2016/04/13 08:57:09 Rejecting grid of difficulty 0.3872105585571663
2016/04/13 08:57:09 Stored the puzzle for future use.
2016/04/13 08:57:09 Attempt 15 at generating puzzle.
2016/04/13 08:57:17 Rejecting grid of difficulty 0.4174233928571427
2016/04/13 08:57:17 Stored the puzzle for future use.
2016/04/13 08:57:17 Attempt 16 at generating puzzle.
2016/04/13 08:57:21 Rejecting grid of difficulty 0.16944713167388167
2016/04/13 08:57:21 Stored the puzzle for future use.
2016/04/13 08:57:21 Attempt 17 at generating puzzle.
2016/04/13 08:57:41 Rejecting grid of difficulty 0.3005621205309444
2016/04/13 08:57:41 Stored the puzzle for future use.
2016/04/13 08:57:41 Attempt 18 at generating puzzle.
2016/04/13 08:57:50 Rejecting grid of difficulty 0.12115687234036059
2016/04/13 08:57:50 Stored the puzzle for future use.
2016/04/13 08:57:50 Attempt 19 at generating puzzle.

Is that normal? Thank you

[jkomoros]

Yeah, the current model in trunk for some reason is generating puzzles only in a very narrow band of difficulties. This means that if you're trying to generate puzzles that are outside that narrow band it will keep on trying for a long time until it randomly hits on one, which can take basically forever.

This is something I've been digging into for the past week or so. See #253 for more information (and issues like #254 and others for work I've been doing to help me dig into the problem and understand it). Unfortunately whatever is causing the underlying problem is pretty persistent now even as I train new models using the freshest data, which implies it a long-term sustainable fix will take some more investigation.

I didn't actually realize anyone else was relying on trunk's difficulty model being in a good state so I was taking my time digging in and fixing it. I was just going to temporarily revert to an old hs_difficulty_weights.go model from January, but I just spot checked it and found it also had a weird band of results. I'll dig into this tonight to see what the best short-term approach is to get the model to a better place.

By the way, thanks for filing an issue--please feel free to provide any feedback or ask any questions you have!

[jkomoros]

I'm going to track the underlying problem and my investigation in #253 . For now I'm going to close this issue and encourage you to follow along there.

If you want a short-term solution while I track down the solution, checking out an old version of the repo and using that should work. 758540e833 should be pretty safe.

[jkomoros]

My investigation in #253 implies that a good short term solution for you is to use the 758540e snapshot for now to generate puzzles. I think I might know what the underlying problem is; tomorrow night hopefully I'll be able to implement a long-term fix (assuming my hypothesis is correct)