-------- Forwarded Message -------- From: Simon Tatham <ana...@pobox.com> To: Ben Hutchings <b...@decadent.org.uk> Subject: Re: Bug#580713: sgt-puzzles: Larger puzzles randomly freezes on generation Date: Wed, 12 May 2010 09:14:44 +0100
Ben Hutchings <b...@decadent.org.uk> wrote: > It does seem like the time taken to generate puzzles for some of the > given settings is at least very variable. Is it possible that certain > seed values could result in infinite loops? I can't think why that > would happen. There shouldn't be any cause for a literally _infinite_ loop, no; if anybody can prove otherwise, I'll certainly treat it as a bug needing to be fixed. Of course many of the puzzle generators, if you dial them up to big enough grids, will take time which is theoretically finite but in practice too long to wait for. But more subtly than that, yes, it is perfectly possible that generation time for some sizes of some puzzles can be very variable. The typical process of generation is to invent part of a puzzle at random, run a solver (perhaps repeatedly) to check its solubility while refining the clue set and/or solution to converge on a uniquely soluble puzzle of the right difficulty, and then encode it. Sometimes the randomly invented puzzle at the start of that process happens to be such that the next phase has to spend a lot of time tweaking and may not get anywhere, but sometimes it comes out right first time. My general editorial criterion is that the _preset_ puzzle settings should generally give reasonable generation times; if you ask for settings significantly outside that range, they'll still make their best effort to return games for you, but I don't attempt to guarantee anything about their efficiency. It is possible that some of the generators might be improved by being a little less persistent. 5x5 Solo, for example, used to be very hit-and-miss: sometimes it was able to generate a puzzle immediately, but sometimes it would sit there and think (for practical purposes) indefinitely, depending on whether the initial recursive function that constructs a filled valid Sudoku grid happened to recurse into a large dead end or luckily went straight to a plausible arrangement. This problem was even worse when I introduced jigsaw mode, so I came up with r7978 - the filled-grid generator has limited time to come up with an answer, and otherwise is guillotined and told to start again. This turned out to work much better, since the length of time taken to negotiate a dead end was much larger than the time needed to keep restarting the generator until it didn't get into one in the first place; so now 5x5 Solo grids are generated much more reliably. So it's possible that other puzzles would benefit from similar work, but a comprehensive review of that nature is a long way from the top of my list. Competent assistance welcome! Cheers, Simon -- To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org
