After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 731215 - Make SudokuGenerator work properly
Make SudokuGenerator work properly
Status: RESOLVED FIXED
Product: gnome-sudoku
Classification: Applications
Component: general
git master
Other Linux
: High major
: ---
Assigned To: gnome-sudoku-maint
gnome-sudoku-maint
Depends on: 580055 580056 619190 725797
Blocks:
 
 
Reported: 2014-06-04 14:34 UTC by Michael Catanzaro
Modified: 2014-08-11 05:44 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
Parin's initial SudokuGenerator patch (19.90 KB, patch)
2014-06-04 14:34 UTC, Michael Catanzaro
none Details | Review
shared library patch for qqwing (50.11 KB, application/octet-stream)
2014-07-23 21:32 UTC, Michael Catanzaro
  Details
Remove SudokuGenerator (15.08 KB, patch)
2014-08-05 08:31 UTC, Parin Porecha
committed Details | Review
Remove SudokuSolver, SudokuRater and DifficultyRating (32.54 KB, patch)
2014-08-05 09:30 UTC, Parin Porecha
committed Details | Review

Description Michael Catanzaro 2014-06-04 14:34:33 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.
Comment 1 Michael Catanzaro 2014-06-04 16:52:55 UTC
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.)
Comment 2 Michael Catanzaro 2014-07-16 03:14:34 UTC
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.
Comment 3 Michael Catanzaro 2014-07-17 15:18:41 UTC
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.)
Comment 4 Stephen 2014-07-23 09:26:23 UTC
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.
Comment 5 Stephen 2014-07-23 18:59:34 UTC
An option for generating puzzles with symmetry has been added in qqwing 1.1.0.
Comment 6 Stephen 2014-07-23 19:22:14 UTC
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
Comment 7 Michael Catanzaro 2014-07-23 20:54:48 UTC
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.
Comment 8 Michael Catanzaro 2014-07-23 21:32:09 UTC
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.
Comment 9 Stephen 2014-07-23 21:50:04 UTC
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?
Comment 10 Michael Catanzaro 2014-07-23 23:20:44 UTC
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.
Comment 11 Stephen 2014-07-24 01:46:25 UTC
Patch accepted
Comment 12 Michael Catanzaro 2014-07-24 03:25:52 UTC
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.)
Comment 13 Michael Catanzaro 2014-07-24 03:26:16 UTC
(In reply to comment #12)
> Wonderful, thanks Steven! 

Stephen!
Comment 14 Stephen 2014-07-24 09:39:41 UTC
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.
Comment 15 Parin Porecha 2014-08-05 08:31:13 UTC
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.
Comment 16 Parin Porecha 2014-08-05 09:30:43 UTC
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
Comment 17 Michael Catanzaro 2014-08-05 16:44:35 UTC
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!
Comment 18 Michael Catanzaro 2014-08-05 16:50:28 UTC
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.
Comment 19 Parin Porecha 2014-08-05 17:25:33 UTC
> 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 ?
Comment 20 Parin Porecha 2014-08-05 17:28:05 UTC
> 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 21 Parin Porecha 2014-08-05 17:35:06 UTC
Comment on attachment 282507 [details] [review]
Remove SudokuGenerator

Pushed as 	a4b6aa4
Comment 22 Parin Porecha 2014-08-05 17:35:27 UTC
Comment on attachment 282531 [details] [review]
Remove SudokuSolver, SudokuRater and DifficultyRating

3f4401f
Comment 23 Parin Porecha 2014-08-05 17:36:06 UTC
s/3f4401f/Pushed as 3f4401f
Comment 24 Michael Catanzaro 2014-08-07 00:41:56 UTC
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.
Comment 25 Michael Catanzaro 2014-08-07 15:13:35 UTC
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!
Comment 26 Stephen 2014-08-11 03:05:17 UTC
Version 1.1.3 of QQWing has been released with all the changes you need: http://ostermiller.org/qqwing/download.html
Comment 27 Michael Catanzaro 2014-08-11 05:44:46 UTC
Perfect, I'm merging the qqwing branch now and adding qqwing to GNOME jhbuild. Thanks!