GNOME Bugzilla – Bug 731215
Make SudokuGenerator work properly
Last modified: 2014-08-11 05:44:46 UTC
Created attachment 277881 [details] [review] Parin's initial SudokuGenerator patch We need to make sure SudokuGenerator is working excellently. The following patch implements most of the behavior, but there's a bit more to do: * We should fix whatever bug causes generation to sometimes take especially long * We probably need to move puzzle generation to a separate thread (but this will obscure bug #1) The possibility of using an external puzzle generator has been discussed. I'm fine with depending on a FLOSS Sudoku generator if that's easier, but I think it would need to be something that can generate symmetric puzzles, after discussing this with a user who expressed disdain of non-symmetric puzzles.
A note from Thomas Hinkle posted to games-list: "Back when I had time to think about such things, the next step I wanted to take with the game was to work on algorithms to generate *hard* puzzles more quickly. I think lots of people like really hard sudoku, and my algorithm basically randomly stumbles on them as is, but it doesn't do it nearly as often as I'd like." (Thomas wrote the original generator.)
Looking at the code for qqwing, it seems like it does nearly everything we need and would be super duper to have as a library, but it's not a library, it's an executable. Should be pretty easy to change that, but we'd have to (a) get our changes accepted upstream, (b) fork qqwing (let's not), or (c) bundle qqwing's source code with gnome-sudoku (prohibited by Fedora, so out of the question). Or (d) rewrite it in Vala, which is fine since it's GPL 2+, but that would be a lot more work. (Maybe not -- should be mostly mechanical, and it would probably be quite easy to add symmetric puzzle support were you to do this.) So the best way to use qqwing from Vala is GLib.Subprocess, which is hardly ideal but probably our best bet. Or get in touch with upstream and go with (a). To handle symmetry, I think we'd have to call qqwing --generate --solution to get a puzzle with its solution, then manually start masking out two symmetric squares at a time until we have multiple solutions (which can be detected with qqwing --solve --count-solutions). Then rate the difficulty of the puzzle, discard it if it's too easy, and start adding random symmetric pairs of squares until it's easy enough if not. Most of your code would just be parsing the output of qqwing. Of course, if you were to rewrite it, it should be pretty easy to add this functionality within qqwing, but I'm really hesitant to recommend that as it's a bunch of extra work. (P.S. qqwing --one-line looks like the easiest format to parse.) Probably the best thing to do is to get asymmetric puzzles working first, then decide how much we really care about symmetry. Looks like USA Today and The Guardian puzzles are always symmetric, but I think the New York Times does asymmetric sudokus, so we can probably get away with asymmetric.
The other disadvantage, of course, is that we're putting a lot of trust on qqwing. If we get complaints that the difficulty levels are not very good, we'll be in a more difficult position than if we had control of that code ourselves. (Still, probably best to go with qqwing and hope for the best: there are big advantages to not having to maintain the generator ourselves.)
This is Stephen Ostermiller, the author of qqwing. I am happy to accept patches to qqwing that add the features that you need. I'm even happy to accept ports to other programming languages. (There is already a Java port available.) In theory it wouldn't be hard to implement symmetry within qqwing. I would take the approach of modifying the generatePuzzle method. The call to rollbackNonGuesses would need to be removed because it could remove non-symmetrical squares. Then the for loop that removes one value at a time would need to be modified. Instead of removing just one value at a time, it would have to remove that value and all of the corresponding symmetrical values. (It would then have to also be able to put all of them back if it turns out they are actually needed.) It would be a fun project to work on myself, but I don't have a lot of spare time right now. I can't make any promises about when I would be able to get around to it.
An option for generating puzzles with symmetry has been added in qqwing 1.1.0.
Here is the link to the qqwing website: http://ostermiller.org/qqwing/ I also did some investigation about how symmetry changes the difficulty of the puzzles. The results were not quite what I expected: http://savvyroo.com/chart-940259529331-sudoku-puzzles-with-symmetry-easier-or-harder
Stephen, that's great, thanks for your help! qqwing is lightning-fast at generating or solving whatever difficulty of symmetric Sudoku we want; I no longer have any doubts about depending on it. Would you accept a patch to split qqwing into the current binary and a C++ library? We could just execute the binary and parse the output if not, but it'd be much nicer (and less fragile) to have a library. Another very small advantage to this is that distros won't be able to compile Sudoku 3.14 at all until they've packaged qqwing, whereas if we only have a binary to use then I suspect many distros that skim over our NEWS file will discover the new runtime dependency the hard way.
Created attachment 281530 [details] shared library patch for qqwing Does something like this look good? Caution: I haven't used it too much yet, besides to confirm that qqwing itself still works. P.S. I changed some of the #includes to use standard C++ headers, since on my system it was including string.h (aka <cstring>) instead of the <string> that has std::string.
Can you make the patch against the source in github? https://github.com/stephenostermiller/qqwing How does having a separate library change the way that rpm and deb archives are built?
Probably easiest for me to submit a pull request. I'll also take care of changes to the RPM spec; besides modifying the file list, I had to make a couple tweaks to make sure the buildroot doesn't show up in the library's rpath (which causes rpmbuild to emit a supremely unhelpful error message). Regarding changes to the deb... I don't suppose you have Debian/Ubuntu? If not I guess one of us (probably will end up being Parin, sorry Parin) will spin up a VM or mess around with OBS.
Patch accepted
Wonderful, thanks Steven! Expect qqwing to be installed by default in Ubuntu 15.04 if they upgrade GNOME Sudoku when I expect them to (probable) and don't drop it from the default install (unlikely since Sudoku is popular). So Parin, we have a minor problem: we now have a C++ library that's easy to use and does everything we need, but Vala code can only call functions declared with a C calling convention. So what you'll need to do is write some glue code: a few C++ functions that use qqwing, declared with C calling convention so that Vala can use them. Then you can write a vapi for those functions. Neither of these steps are hard, but they're probably quite different than the sort of programming you've done before, so ping me if you need help with any of this. Here's an example of how to write a vapi for C code, where the C code and the Vala code is compiled into the same binary: https://git.gnome.org/browse/gnome-chess/commit/?id=bdd5ff69fe04d41e28c44c523facc5e3f48ac47a You'll need to declare your wrapper functions in a header file like this: G_BEGIN_DECLS // wrapper function declarations go here G_END_DECLS These macros will ensure your functions are declared with C calling convention if the file is included by C++ code, and they'll expand to nothing when included by C code. (It's the usual #ifdef __cplusplus extern "C" you saw when you looked up how to do this earlier.) Then when you implement the functions in your C++ source file, you write completely normal C++ code, and Vala will be able to call it fine. (Pretty sure. :) The trick is that a C++ class cannot appear in the function declaration (pretty sure :(, so the SudokuBoard class has to basically not appear anywhere in your header file. (You'll probably need to convert it into a 2D array of ints to pass back to Vala.)
(In reply to comment #12) > Wonderful, thanks Steven! Stephen!
I added Michael Catanzaro to the copyright, bumped the version number (1.1.1), and published a new release of qqwing that has your changes to make it a library.
Created attachment 282507 [details] [review] Remove SudokuGenerator The next patches will be the removal of SudokuSolver, SudokuRater and DifficultyRating class. I'll also remove the float difficulty rating, and related code.
Created attachment 282531 [details] [review] Remove SudokuSolver, SudokuRater and DifficultyRating All the 3 classes were inter-connected so I had to remove them in one go. Sorry for the big patch. Small changes introduced by this patch - - Move DifficultyCategory enum to sudoku-board.vala - Move float difficulty ranges to SudokuBoard and make them private
Review of attachment 282507 [details] [review]: Were we getting our Sudokus exclusively from the pregenerated ones we distribute? I'm a little bit surprised to see that we had a class named SudokuGenerator that was not being used to generate Sudokus. Well, I guess I shouldn't be at all surprised at this point, but I am!
Review of attachment 282531 [details] [review]: The float ratings are still stored in the predistributed puzzles, right, so they need to remain until you get rid of those? ::: src/gnome-sudoku.vala @@ -171,1 @@ var difficulty_category = board.get_difficulty_category (); I THOUGHT this code was bogus, but never bothered to actually investigate. Great.
> Were we getting our Sudokus exclusively from the pregenerated ones we > distribute? I'm a little bit surprised to see that we had a class named > SudokuGenerator that was not being used to generate Sudokus. yeah, pathetic isn't it ?
> The float ratings are still stored in the predistributed puzzles, right, so > they need to remain until you get rid of those? yes, the next patches will remove them + set_from_string() which is their entry point
Comment on attachment 282507 [details] [review] Remove SudokuGenerator Pushed as a4b6aa4
Comment on attachment 282531 [details] [review] Remove SudokuSolver, SudokuRater and DifficultyRating 3f4401f
s/3f4401f/Pushed as 3f4401f
Good work Parin. AFAIK the only thing left to do is to improve the brief hang when using Print Multiple Sudokus. Let's use bug #580056 for that.
Hey Stephen, one last note from me: our next development release on August 18 is also the beginning of GNOME's pre-release freeze, so it would be super if you could release the next version of QQwing sometime earlier than that. Thanks a bunch for working with us!
Version 1.1.3 of QQWing has been released with all the changes you need: http://ostermiller.org/qqwing/download.html
Perfect, I'm merging the qqwing branch now and adding qqwing to GNOME jhbuild. Thanks!