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 619190 - gnome-sudoku generates invalid puzzles
gnome-sudoku generates invalid puzzles
Status: RESOLVED OBSOLETE
Product: gnome-sudoku
Classification: Applications
Component: general
git master
Other Linux
: High major
: ---
Assigned To: gnome-sudoku-maint
gnome-sudoku-maint
Depends on:
Blocks: 731215
 
 
Reported: 2010-05-20 12:57 UTC by Pablo Castellano (IRC: pablog)
Modified: 2014-08-06 22:54 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
screenshot from solver showing one possible solution count. (255.02 KB, image/png)
2012-03-15 21:08 UTC, Tiffany Antopolski
Details
screenshot from solver showing one possible solution count for second example. (249.98 KB, image/png)
2012-03-15 21:09 UTC, Tiffany Antopolski
Details
screenshot showing invalid puzzle for the 3rd user. (248.52 KB, image/png)
2012-03-15 21:12 UTC, Tiffany Antopolski
Details

Description Pablo Castellano (IRC: pablog) 2010-05-20 12:57:52 UTC
I have found a bugreport in launchpad where 3 people report that they have got sudokus invalid to resolve.

Original here:
https://bugs.launchpad.net/ubuntu/+source/gnome-games/+bug/397783
Comment 1 Pablo Castellano (IRC: pablog) 2010-05-20 13:01:51 UTC
Confirming as they are 3 users
Comment 2 Tiffany Antopolski 2012-03-15 21:08:47 UTC
Created attachment 209886 [details]
screenshot from solver showing one possible solution count.

first puzzle
Comment 3 Tiffany Antopolski 2012-03-15 21:09:26 UTC
Created attachment 209887 [details]
screenshot from solver showing one possible solution count for second example.
Comment 4 Tiffany Antopolski 2012-03-15 21:12:34 UTC
Created attachment 209888 [details]
screenshot showing invalid puzzle for the 3rd user.
Comment 5 Tiffany Antopolski 2012-03-15 21:13:55 UTC
Using the solver at http://www.sudokuwiki.org/sudoku.htm, I ran all 3 example from the downstream bug report through the solver.  The first 2 screenshots show that both puzzles have 1 possible solution, and therefore, the puzzles are valid.

However, for the 3rd puzzle, the solver returned 0 possible solutions, which is quite obvious if you look at the 8's and the top centre 3X3 area.

Therefore, only one of the 3 reports of invalid puzzles appears to be actually a valid report of an invalid puzzle.
Comment 6 Michael Catanzaro 2014-05-31 22:39:41 UTC
Obvious first steps:

* The generator must check all puzzles it produces. (This means sorting through the mess of commented-out code.)
* We need a test case to ensure the solver cannot solve that third puzzle.
* Should also generate a ton of puzzles on 'make check' and ensure the solver can solve them all.

The generator code is going to require significant cleanup and maybe a rewrite to actually figure out what's wrong.  Parin or I will handle this prior to 3.14. We might also switch to an external puzzle generator.
Comment 7 Michael Catanzaro 2014-06-01 00:07:43 UTC
I just deleted this gem (it's absolutely incredible how literal this port was) which might be a good starting point for such a test:

public static void gen_python_test () {
    stdout.printf("import sudoku\n\n");

    for (int repeat = 0; repeat < 20; repeat++)
    {
        SudokuGenerator gen = new SudokuGenerator();
        gen.clues = Random.int_range(17, 60);

        SudokuBoard board = gen.make_symmetric_puzzle (Random.int_range(0, 

        stdout.printf("diff = sudoku.SudokuRater(");
        board.get_string ();
        stdout.printf(").difficulty()\n");

        SudokuRater rater = new SudokuRater(ref board);
        DifficultyRating diff = rater.get_difficulty ();

        stdout.printf("print diff.value, %f\n\n", diff.rating);
    }
}
Comment 8 Michael Catanzaro 2014-08-01 22:58:05 UTC
Removing whiteboard; this is a priority for me but not related to the success of GNOME 3.14.
Comment 9 Michael Catanzaro 2014-08-06 22:54:30 UTC
Hi, I'm closing this bug because we've removed our Sudoku generation backend that was affected by this bug. Beginning with 3.14 we'll be using the QQwing Sudoku puzzle generator [1] to create puzzles. If you experience this issue with the new generator in 3.14 (which will be released next month) then please open a new bug. Thanks!

[1] http://ostermiller.org/qqwing/