GNOME Bugzilla – Bug 619190
gnome-sudoku generates invalid puzzles
Last modified: 2014-08-06 22:54:30 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
Confirming as they are 3 users
Created attachment 209886 [details] screenshot from solver showing one possible solution count. first puzzle
Created attachment 209887 [details] screenshot from solver showing one possible solution count for second example.
Created attachment 209888 [details] screenshot showing invalid puzzle for the 3rd user.
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.
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.
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); } }
Removing whiteboard; this is a priority for me but not related to the success of GNOME 3.14.
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/