GNOME Bugzilla – Bug 725797
"very hard" games were actually very easy the last three times in a row
Last modified: 2014-08-06 22:54:29 UTC
Normally a "very hard" game requires some guessing to complete. However, the last three "very hard" games were trivial to solve. I brought up the "statistics" analysis for the last one and it claimed: Calculated difficulty: Very Hard (0.77) Number of moves instantly fillable by elimination: 1 Number of moves instantly fillable by filling: 8 Amount of trial-and-error required to solve: 4 However, in reality, for the last three games it required no trial-and-error. Previously the game had produced some "very hard" games that required one or two trial and error efforts.
Thank you for your report. Do you usually play "very hard" games or was this a one off? Have you had "very hard" games in gnome-sudoku in the past that were actually of the expected difficulty?
I only play "very hard" games. In the past, Gnome Sudoku's "very hard" games did indeed require forking the solution at least once. The last three games I played all were trivial.
I was hoping this would be a duplicate of Bug #580055, but I think this is different. If you see this again, could you please post one example puzzle that is broken? Thanks.
Created attachment 278114 [details] image1 game statistics
Here's an example of a game that was promised to be "very hard" only required one guess to solve. See image1 for game statistics. Game was rated 0.85 hardness. See the statistics it claims for how few squares aare trivial to fill and how many guesses required to solve --three supposedly. See image2 for the squares I filled without guessing, which was 15. This image shows the remaining possible numbers in the unfilled squares. The quantity of each number trivially filled was: 1 -- 4 2 -- 6 3 -- 2 4 -- 6 5 -- 6 6 -- 9 7 -- 3 8 -- 5 9 -- 7 37 clearly was best for the guess. I tried 3 first, then 7 was the solution. I made an error on seven but corrected it. Despite having made this error, total game time was 49 min 22 seconds. See image3 for game time. I'll play some more games to get you one that is rated very hard but required no guessing. When I complained, three games in a row had been rated very hard but all were solvable without guessing.
Created attachment 278115 [details] image2 squares filled without guessing
Created attachment 278116 [details] image3 time to solve
Thanks for the detailed response -- that will help us a lot.
(In reply to comment #8) > Thanks for the detailed response -- that will help us a lot. I just played one that did not require any guessing, entirely trival despite being "very hard" will provide screen shots
Created attachment 278566 [details] "very hard" problem was trivially easy -- no guesses required attached "very hard" problem was trivially easy -- no guesses required attached, next comment will show erroneous statistics given by program
Created attachment 278567 [details] statistics given that are erroneous for this trivial problem listed as "very hard"
I think this could be connected to https://bugzilla.gnome.org/show_bug.cgi?id=731646 There it seems, that the solver re-rates the puzzles again and again rating it harder towards it being filled completely. So somehow I would guess, that the rating is off. Maybe it is just switched? Do we have an independent rater where we could rate our easy ones against the hard ones? I would think that a completely or nearly completely filled board is rated "very easy". That would be an invariant I would like to have, when I would program something like that.
The problem in Bug #731646 was that the difficulty was that the current version of the puzzle was passed to SudokuRater, rather than the original puzzle. I guess here we see the difficulty computed based on the original puzzle, but it's just wrong: at least "amount of trial-and-error required to solve" seems to be inaccurate.
Created attachment 278959 [details] Two guess puzzle rated as six guess Here's an example of the number of trial and error attempts required being way off. The program says six, but it only required guesses for two squares, in the bottom row, first the eight, then the two. I also tried the other option for each square, and each option led easily to a contradiction. Only when a guess dead ends into an inconclusive result does a game become noticeably difficult. It was obvious that the 8 square should be guessed first because 2 and 8 had the fewest appearances, and the two square obviously next for the same reason, and of course that each square had only two possibilities. I'm a programmer, number theory and iterative type math solutions, but it all has been Fortran (don't laugh, it is ideal for this work!). Maybe I'll get motivated to take apart the source code... I have a special fondness for thew world of NP-complete...
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/