Bug#351043: [gnudoku]: Puzzle generation, reasons for ambiguous behaviour
From the looks of the code, puzzle generation is dependent on a good solve
method:
[GNUDoku.C]
void GNUDoku::generatePuzzle(float const difficulty, int const seed){
...
Sudoku::solve(stack, top, &flag_data, visited);
...
}
Glancing at the solve algorithm, it looks like the solve method in its current
form will not give up straight away if it cannot solve a puzzle from a specific
step. In this case it will carry out a series of trials (I think up to 10) until
a working solution is found. The advantage of such a technique is that it allows
the program to solve puzzles that are beyond the ability of its logical
reasoning. The disadvantage is that the puzzle generation algorithm is not able
to determine whether or not a puzzle will have multiple solutions.
[sudoku-solve.C]
bool Solve(Board& board, std::vector& moves){
...
/* once the forced moves have been exhausted, we need to make a 'likely'
* move. Such moves are based on trial and error, like random moves, but
* more directed, as they will go for the boxes with the fewest possible
* mistakes. */
...
}
I would expect that fixing this bug in the code would, in the simplest case,
require the removal of this trial-and-error algorithm. While doing that would
(probably) result in unambiguous puzzles, it would also make the generated
puzzles a lot simpler.
Hope this helps,
David
--
To UNSUBSCRIBE, email to [EMAIL PROTECTED]
with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Bug#351043: gnudoku
tags 351043 +help thanks I don't know how to deal with this bug. I am quite surprised of its severity since I totally agree with John. Of course I don't want to start a "severity war" so I just mark the bug with the help tag. > The generation of ambiguous puzzles is a known bug. None of the authors > has the time to do anything about it at this time. > > However, I would argue that the poster overestimates the seriousness of > it. > 1. Nowhere I can find is there some official definition of Su Doku > that states puzzles must be unambiguous, although I acknowlege > that it is conventional. > 2. gnudoku also serves to load puzzles obtained elsewhere, as well > as solving puzzles the user inputs. > > > The presence of ksudoku and gnome-sudoku in testing also makes the > > transition of gnudoku to testing quite useless > > I don't know how debian operates, but I didn't realise that an > application had to satisfy a criterion of usefulness compared to > existing alternatives to be allowed into the distribution. > > -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Bug#351043: gnudoku
Please excuse me if this message doesn't come through properly, I have no idea how the debian bug tracker is meant to work, and no instructions were prominent. The generation of ambiguous puzzles is a known bug. None of the authors has the time to do anything about it at this time. However, I would argue that the poster overestimates the seriousness of it. 1. Nowhere I can find is there some official definition of Su Doku that states puzzles must be unambiguous, although I acknowlege that it is conventional. 2. gnudoku also serves to load puzzles obtained elsewhere, as well as solving puzzles the user inputs. > The presence of ksudoku and gnome-sudoku in testing also makes the > transition of gnudoku to testing quite useless I don't know how debian operates, but I didn't realise that an application had to satisfy a criterion of usefulness compared to existing alternatives to be allowed into the distribution. -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Bug#351043: gnudoku: Reproduced
Package: gnudoku Version: 0.93-1 Followup-For: Bug #351043 Subject: gnudoku: Reproduced Followup-For: Bug #351043 Package: gnudoku Version: 0.93-1 This is a report from my second Etch machine. As gnudoku is 9 days old and about to enter testing but my bug hasn't been confirmed, I've tried to reproduce here. I succeeded at the first attempt and am attaching the following files: tocheck: The initial puzzle with multiple solutions generated. tocheck_solved_by_gnudoku: gnudoku's initial solution to the puzzle. tocheck_solved_by_gnudoku_with_hint: gnudoku's solution to the puzzle after 1 number conflicting with gnudoku's initial solution was entered. I loaded tocheck, entered that number, and asked gnudoku to solve. The conflicting number is from another solution to the puzzle found again by Josh Metzler's logicgamesonline.com's sudoku solver. If Josh's solver would be buggy, one would expect gnudoku to fail to find a solution to the initial puzzle plus 1 number conflicting with gnudoku's initial solution. I'm bumping this to serious until somebody's input suggests that this bug is unreproducible or...specific to my house? :) -- System Information: Debian Release: testing/unstable APT prefers testing APT policy: (990, 'testing'), (500, 'unstable') Architecture: i386 (i686) Shell: /bin/sh linked to /bin/bash Kernel: Linux 2.6.12-1-386 Locale: LANG=fr_CA, LC_CTYPE=fr_CA (charmap=ISO-8859-1) Versions of packages gnudoku depends on: ii libatk1.0-0 1.10.3-1The ATK accessibility toolkit ii libc62.3.5-8 GNU C Library: Shared libraries an ii libcairo21.0.2-3 The Cairo 2D vector graphics libra ii libfontconfig1 2.3.2-1.1 generic font configuration library ii libgcc1 1:4.0.2-5 GCC support library ii libglib2.0-0 2.8.6-1 The GLib library of C routines ii libglibmm-2.4-1c2a 2.8.2-2 C++ wrapper for the GLib toolkit ( ii libgtk2.0-0 2.8.9-2 The GTK+ graphical user interface ii libgtkmm-2.4-1c2a1:2.6.5-1 C++ wrappers for GTK+ 2.4 (shared ii libpango1.0-01.10.2-1Layout and rendering of internatio ii libsigc++-2.0-0c2a 2.0.16-2type-safe Signal Framework for C++ ii libstdc++6 4.0.2-5 The GNU Standard C++ Library v3 ii libx11-6 6.8.2.dfsg.1-11 X Window System protocol client li ii libxcursor1 1.1.3-1 X cursor management library ii libxext6 6.8.2.dfsg.1-11 X Window System miscellaneous exte ii libxi6 6.8.2.dfsg.1-11 X Window System Input extension li ii libxinerama1 6.8.2.dfsg.1-11 X Window System multi-head display ii libxrandr2 6.8.2.dfsg.1-11 X Window System Resize, Rotate and ii libxrender1 1:0.9.0.2-1 X Rendering Extension client libra gnudoku recommends no packages. -- no debconf information -- System Information: Debian Release: testing/unstable APT prefers testing APT policy: (990, 'testing'), (500, 'unstable') Architecture: i386 (i686) Shell: /bin/sh linked to /bin/bash Kernel: Linux 2.6.12-1-386 Locale: LANG=fr_CA, LC_CTYPE=fr_CA (charmap=ISO-8859-1) Versions of packages gnudoku depends on: ii libatk1.0-0 1.10.3-1The ATK accessibility toolkit ii libc62.3.5-8 GNU C Library: Shared libraries an ii libcairo21.0.2-3 The Cairo 2D vector graphics libra ii libfontconfig1 2.3.2-1.1 generic font configuration library ii libgcc1 1:4.0.2-5 GCC support library ii libglib2.0-0 2.8.6-1 The GLib library of C routines ii libglibmm-2.4-1c2a 2.8.2-2 C++ wrapper for the GLib toolkit ( ii libgtk2.0-0 2.8.10-1The GTK+ graphical user interface ii libgtkmm-2.4-1c2a1:2.6.5-1 C++ wrappers for GTK+ 2.4 (shared ii libpango1.0-01.10.2-1Layout and rendering of internatio ii libsigc++-2.0-0c2a 2.0.16-2type-safe Signal Framework for C++ ii libstdc++6 4.0.2-5 The GNU Standard C++ Library v3 ii libx11-6 6.8.2.dfsg.1-11 X Window System protocol client li ii libxcursor1 1.1.3-1 X cursor management library ii libxext6 6.8.2.dfsg.1-11 X Window System miscellaneous exte ii libxi6 6.8.2.dfsg.1-11 X Window System Input extension li ii libxinerama1 6.8.2.dfsg.1-11 X Window System multi-head display ii libxrandr2 6.8.2.dfsg.1-11 X Window System Resize, Rotate and ii libxrender1 1:0.9.0.2-1 X Rendering Extension client libra gnudoku recommends no packages. -- no debconf information -- To UNSUBSCRIBE, email to [EMAIL PROTECTED] with a subject of "unsubscribe". Trouble? Contact [EMAIL PROTECTED]
Bug#351043: gnudoku: Reproduced
Package: gnudoku Version: 0.93-1 Followup-For: Bug #351043 This is a report from my second Etch machine. As gnudoku is 9 days old and about to enter testing but my bug hasn't been confirmed, I've tried to reproduce here. I succeeded at the first attempt and am attaching the following files: tocheck: The initial puzzle with multiple solutions generated. tocheck_solved_by_gnudoku: gnudoku's initial solution to the puzzle. tocheck_solved_by_gnudoku_with_hint: gnudoku's solution to the puzzle after 1 number conflicting with gnudoku's initial solution was entered. I loaded tocheck, entered that number, and asked gnudoku to solve. The conflicting number is from another solution to the puzzle found again by Josh Metzler's logicgamesonline.com's sudoku solver. If Josh's solver would be buggy, one would expect gnudoku to fail to find a solution to the initial puzzle plus 1 number conflicting with gnudoku's initial solution. I'm bumping this to serious until somebody's input suggests that this bug is unreproducible or...specific to my house? :) -- System Information: Debian Release: testing/unstable APT prefers testing APT policy: (990, 'testing'), (500, 'unstable') Architecture: i386 (i686) Shell: /bin/sh linked to /bin/bash Kernel: Linux 2.6.12-1-386 Locale: LANG=fr_CA, LC_CTYPE=fr_CA (charmap=ISO-8859-1) Versions of packages gnudoku depends on: ii libatk1.0-0 1.10.3-1The ATK accessibility toolkit ii libc62.3.5-8 GNU C Library: Shared libraries an ii libcairo21.0.2-3 The Cairo 2D vector graphics libra ii libfontconfig1 2.3.2-1.1 generic font configuration library ii libgcc1 1:4.0.2-5 GCC support library ii libglib2.0-0 2.8.6-1 The GLib library of C routines ii libglibmm-2.4-1c2a 2.8.2-2 C++ wrapper for the GLib toolkit ( ii libgtk2.0-0 2.8.9-2 The GTK+ graphical user interface ii libgtkmm-2.4-1c2a1:2.6.5-1 C++ wrappers for GTK+ 2.4 (shared ii libpango1.0-01.10.2-1Layout and rendering of internatio ii libsigc++-2.0-0c2a 2.0.16-2type-safe Signal Framework for C++ ii libstdc++6 4.0.2-5 The GNU Standard C++ Library v3 ii libx11-6 6.8.2.dfsg.1-11 X Window System protocol client li ii libxcursor1 1.1.3-1 X cursor management library ii libxext6 6.8.2.dfsg.1-11 X Window System miscellaneous exte ii libxi6 6.8.2.dfsg.1-11 X Window System Input extension li ii libxinerama1 6.8.2.dfsg.1-11 X Window System multi-head display ii libxrandr2 6.8.2.dfsg.1-11 X Window System Resize, Rotate and ii libxrender1 1:0.9.0.2-1 X Rendering Extension client libra gnudoku recommends no packages. -- no debconf information 02467040060259006000813315402614057380356738700060059408007061280829513467143867259756924813978231546261495738435678921387142695594386172612759384829513467143867259756924813978231546261495738435678921387152694594386172612749385
Bug#351043: gnudoku: generates puzzles with multiple solutions
Package: gnudoku Version: 0.93-1 Severity: important I have tried 2 puzzles in gnudoku generated with the defaults (difficulty between Easy and Hard). Both puzzles generated have multiple solutions. In the first case, I realized the problem 7 digits away from completion, so the problem is pretty obvious. This puzzle as it was when I abdicated is the first attached. I abdicated about the second puzzle earlier and entered where I was in Logic Games Online's Sudoku Solver. The solution found by this site is not the same as the one gnudoku gives after asking it to solve the puzzle (at least one of the solutions given by the site, I don't know if the choice is deterministic). The site also mentions at the bottom that the puzzle entered had multiple solutions. The URL for the solution is http://www.logicgamesonline.com/sudoku/solver.php?s=...649275452378961967...348724..3516..94..7325367..489348...127691237854275..4693 gnudoku's solution is the second attachment. Given that this happened in the 2 first tries with the defaults, I suggest to bump this bug to serious unless this issue is specific to my system. The bug as it happens here not only makes gnudoku basically unusable/unenjoyable, but also quite frustrating, as I personnally don't abdicate quickly on a su doku (I feel lucky that the unsolvable part in the first puzzle came only 7 digits away from the end, at which point the problem was quite obvious). The presence of ksudoku and gnome-sudoku in testing also makes the transition of gnudoku to testing quite useless (at least until this bug is solved). -- System Information: Debian Release: testing/unstable APT prefers testing APT policy: (990, 'testing'), (500, 'unstable') Architecture: i386 (i686) Shell: /bin/sh linked to /bin/bash Kernel: Linux 2.6.12-1-386 Locale: LANG=fr_CA.UTF-8, LC_CTYPE=fr_CA.UTF-8 (charmap=UTF-8) Versions of packages gnudoku depends on: ii libatk1.0-0 1.10.3-1The ATK accessibility toolkit ii libc62.3.5-8 GNU C Library: Shared libraries an ii libcairo21.0.2-3 The Cairo 2D vector graphics libra ii libfontconfig1 2.3.2-1.1 generic font configuration library ii libgcc1 1:4.0.2-5 GCC support library ii libglib2.0-0 2.8.6-1 The GLib library of C routines ii libglibmm-2.4-1c2a 2.8.2-2 C++ wrapper for the GLib toolkit ( ii libgtk2.0-0 2.8.10-1The GTK+ graphical user interface ii libgtkmm-2.4-1c2a1:2.6.5-1 C++ wrappers for GTK+ 2.4 (shared ii libpango1.0-01.10.2-1Layout and rendering of internatio ii libsigc++-2.0-0c2a 2.0.16-2type-safe Signal Framework for C++ ii libstdc++6 4.0.2-5 The GNU Standard C++ Library v3 ii libx11-6 6.8.2.dfsg.1-11 X Window System protocol client li ii libxcursor1 1.1.3-1 X cursor management library ii libxext6 6.8.2.dfsg.1-11 X Window System miscellaneous exte ii libxi6 6.8.2.dfsg.1-11 X Window System Input extension li ii libxinerama1 6.8.2.dfsg.1-11 X Window System multi-head display ii libxrandr2 6.8.2.dfsg.1-11 X Window System Resize, Rotate and ii libxrender1 1:0.9.0.2-1 X Rendering Extension client libra gnudoku recommends no packages. -- no debconf information 718923456923456718456008293261589374347060589589347162132695847894000635675834921183649275452378961967152348724983516819465732536721489348596127691237854275814693
