Debian Bug report logs - #351043
gnudoku: generates puzzles with multiple solutions

version graph

Package: gnudoku; Maintainer for gnudoku is (unknown);

Reported by: Filipus Klutiero <cheal@hotpop.com>

Date: Thu, 2 Feb 2006 13:33:04 UTC

Severity: serious

Tags: help, upstream

Merged with 375201

Found in version gnudoku/0.93-1

Done: Lucas Nussbaum <lucas@lucas-nussbaum.net>

Bug is archived. No further changes may be made.

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to Filipus Klutiero <cheal@hotpop.com>:
New Bug report received and forwarded. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #5 received at submit@bugs.debian.org (full text, mbox):

From: Filipus Klutiero <cheal@hotpop.com>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: gnudoku: generates puzzles with multiple solutions
Date: Thu, 02 Feb 2006 08:27:59 -0500
[Message part 1 (text/plain, inline)]
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-1        The ATK accessibility toolkit
ii  libc6                    2.3.5-8         GNU C Library: Shared libraries an
ii  libcairo2                1.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-1        The GTK+ graphical user interface 
ii  libgtkmm-2.4-1c2a        1:2.6.5-1       C++ wrappers for GTK+ 2.4 (shared 
ii  libpango1.0-0            1.10.2-1        Layout and rendering of internatio
ii  libsigc++-2.0-0c2a       2.0.16-2        type-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
[gnudoku.sudoku (text/plain, attachment)]
[invalid2complete.sudoku (text/plain, attachment)]

Information forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to Filipus Klutiero <chealer@vif.ca>:
Extra info received and forwarded to list. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #10 received at 351043@bugs.debian.org (full text, mbox):

From: Filipus Klutiero <chealer@vif.ca>
To: Debian Bug Tracking System <351043@bugs.debian.org>
Subject: gnudoku: Reproduced
Date: Fri, 10 Feb 2006 09:24:42 -0500
[Message part 1 (text/plain, inline)]
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-1        The ATK accessibility toolkit
ii  libc6                    2.3.5-8         GNU C Library: Shared libraries an
ii  libcairo2                1.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-1c2a        1:2.6.5-1       C++ wrappers for GTK+ 2.4 (shared 
ii  libpango1.0-0            1.10.2-1        Layout and rendering of internatio
ii  libsigc++-2.0-0c2a       2.0.16-2        type-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
[tocheck.sudoku (text/plain, attachment)]
[tocheck_solved_by_gnudoku.sudoku (text/plain, attachment)]
[tocheck_solved_by_gnudoku_with_hint.sudoku (text/plain, attachment)]

Information forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to Filipus Klutiero <chealer@vif.ca>:
Extra info received and forwarded to list. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #15 received at 351043@bugs.debian.org (full text, mbox):

From: Filipus Klutiero <chealer@vif.ca>
To: Debian Bug Tracking System <351043@bugs.debian.org>
Subject: gnudoku: Reproduced
Date: Fri, 10 Feb 2006 10:20:55 -0500
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-1        The ATK accessibility toolkit
ii  libc6                    2.3.5-8         GNU C Library: Shared libraries an
ii  libcairo2                1.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-1c2a        1:2.6.5-1       C++ wrappers for GTK+ 2.4 (shared 
ii  libpango1.0-0            1.10.2-1        Layout and rendering of internatio
ii  libsigc++-2.0-0c2a       2.0.16-2        type-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-1        The ATK accessibility toolkit
ii  libc6                    2.3.5-8         GNU C Library: Shared libraries an
ii  libcairo2                1.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-1        The GTK+ graphical user interface 
ii  libgtkmm-2.4-1c2a        1:2.6.5-1       C++ wrappers for GTK+ 2.4 (shared 
ii  libpango1.0-0            1.10.2-1        Layout and rendering of internatio
ii  libsigc++-2.0-0c2a       2.0.16-2        type-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



Information forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to Filipus Klutiero <ido@vif.com>:
Extra info received and forwarded to list. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #20 received at 351043@bugs.debian.org (full text, mbox):

From: Filipus Klutiero <ido@vif.com>
To: 351043@bugs.debian.org
Cc: control@bugs.debian.org
Subject: Serious
Date: Fri, 10 Feb 2006 11:14:55 -0500
severity 351043 serious
thanks

Sorry for the spam in the last mail, my reportbug/exim setup needs 
polishing on the other machine.



Information forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to "John C. Spray" <jcs116@york.ac.uk>:
Extra info received and forwarded to list. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #25 received at 351043@bugs.debian.org (full text, mbox):

From: "John C. Spray" <jcs116@york.ac.uk>
To: 351043@bugs.debian.org
Subject: gnudoku
Date: Fri, 10 Feb 2006 16:40:12 +0000
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.




Severity set to `serious'. Request was from Filipus Klutiero <ido@vif.com> to control@bugs.debian.org. Full text and rfc822 format available.

Information forwarded to debian-bugs-dist@lists.debian.org:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to David Gil <dgil@telefonica.net>:
Extra info received and forwarded to list. Full text and rfc822 format available.

Message #32 received at 351043@bugs.debian.org (full text, mbox):

From: David Gil <dgil@telefonica.net>
To: "John C. Spray" <jcs116@york.ac.uk>, 351043@bugs.debian.org, Filipus Klutiero <ido@vif.com>
Subject: Re: Bug#351043: gnudoku
Date: Fri, 10 Feb 2006 19:16:36 +0100
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.
> 
> 




Tags added: help Request was from David Gil <dgil@telefonica.net> to control@bugs.debian.org. Full text and rfc822 format available.

Tags added: upstream Request was from Filipus Klutiero <chealer@vif.com> to control@bugs.debian.org. Full text and rfc822 format available.

Information forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to Filipus Klutiero <ido@vif.com>:
Extra info received and forwarded to list. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #41 received at 351043@bugs.debian.org (full text, mbox):

From: Filipus Klutiero <ido@vif.com>
To: 351043@bugs.debian.org
Subject: Determining severity
Date: Sat, 11 Feb 2006 16:21:21 -0500
>
>
>The generation of ambiguous puzzles is a known bug.  None of the authors
>has the time to do anything about it at this time.
>  
>
OK, well, at least that simplifies determining this bug's severity.

>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.
>  
>
From http://en.wikipedia.org/wiki/Sudoku : "It is possible to set 
starting grids with more than one solution and to set grids with no 
solution, but such are not considered proper /Sudoku/ puzzles; as in 
most other pure-logic puzzles, a unique solution is expected."

>     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.
>
A new application's usefullness is obviously relative to the existing 
applications, but this isn't really the problem here. Before gnudoku 
enters testing, the question is more whether gnudoku's usefullness 
compensates the frustration this bug would cause to users.



>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.
>
Hi David, I'm happy to see your reply. IMO this bug is important. I 
don't know whether it should be serious. This is mostly why I opened 
this last week and asked to consider bumping the bug to serious. I was 
expecting feedback from you, but this didn't happen until I upgraded the 
bug, so I thought you were missing and not aware of the bug. I chose to 
upgrade this to serious because I wanted you to judge this bug's 
severity before gnudoku enters testing. Now that you're clearly aware of 
it, it's your call to downgrade this bug or not. It's theorically your 
privilege to make a bug serious, so I won't infringe this once more and 
there won't be any severity war. This bug isn't RC according to any 
Debian policy, so it's your privilege to set it's severity.

I'll still precise why I think this is serious since I'm the only one 
that seems to think that. As John says, generating puzzles is only one 
of gnudoku's features. Let's start by analyzing puzzle generation. I 
don't know how you play sudoku, but I progress by filling 1 case for 
which I deducted the content at a time. If I can't fill a single case, I 
try more or abdicate. It's certainly possible to complete puzzles with 
multiple solutions, but I'd have to use a different solving method, and 
I don't think I'd enjoy. The problem is that if gnudoku generates 
puzzles with multiple solutions sometimes, I have to either put the 
initial puzzle in a different solver like logicgamesonline.com's, check 
whether it has multiple solutions and generate a new puzzle if it does 
(then repeat) or try puzzles anyway and always wonder whether the 
solving method I use is ineffective or if I should just try harder. The 
level of uncertainty caused by this issue depends on the proportion of 
puzzles with multiple solutions generated by gnudoku. In my case this 
proportion is 1 up to now. I may have that proportion wrong (hopefully 
it's actually lower :) ) but I'm already sure that I won't ever enjoy 
solving a puzzle generated by current gnudoku again without making sure 
it has a unique solution first. And doing that is also painful (and 
relies on other software being available anyway). Also, this description 
is only valid once the user is aware of the bug. In my case, I said to 
Josh Metzler that I was unable to solve the first puzzle generated by 
gnudoku only 7 digits away from completion and thought I was getting 
dumb, and he replied that the puzzle had multiple solutions. But most 
people probably don't know authors of Sudoku websites and are not so 
lucky :) Probably that someone would try a first puzzle, abdicate after 
a long time, try again, abdicate, lower the difficulty. Then if gnudoku 
generates one puzzle with a single solution, people are probably only 
going to take more time to realize that the bug isn't in their brain and 
look at the BTS.

And then there are the other uses of gnudoku. IMHO gnudoku is reasonably 
useful to solve puzzles obtained elsewhere. It's certainly not as good 
as ksudoku, but it will at least warn about direct conflicts and be a 
bit more useful than paper. gnudoku can also compute solutions. AFAIK it 
does that well. gnudoku should also be rather useful to verify solutions.

So gnudoku does at least three things well. However, here it can be 
noted that there is already software in Etch that does that. I haven't 
tried gnome-sudoku. I know that ksudoku does all three, usually better. 
gnudoku does have the merit of doing it without depending on either 
libgnome or kdelibs. Now, does this compensate the frustration users 
will most likely experience before learning about the bug? IMO, no, but 
I would understand the maintainer to disagree about this. I note that 
the description reads "A program for creating and solving SuDoku 
puzzles", so "creating" comes first. This order may be random, but 
solving puzzles created by gnudoku is the first use for me (and only, 
until I try using it to debug a fourth sudoku program ;) ).

I think there's still a simple thing that could be done to avoid 
frustrating users...just mention the bug in the software. This is of 
course ugly, but used sometimes in special cases. I remember gnome-apt 
issuing a big warning that it was buggy or something like that at 
startup. I never really tried it past this point, but I'm not 
frustrated/ashamed that it's in Debian stable.

Aside from that, and this is more for upstream than for an immediate 
handling of this bug, John didn't give much details about solving the 
issue for good. gnudoku appears to be C++, and ksudoku does the 
generation well and has a function to determine if a puzzle has multiple 
solutions. Is stealing this code realistic, or would it still be too 
much time-expensive? Maybe also make a libsudoku? :-P

Hum, sorry for the long mail :/



Information forwarded to debian-bugs-dist@lists.debian.org:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to David Gil <dgil@telefonica.net>:
Extra info received and forwarded to list. Full text and rfc822 format available.

Message #46 received at 351043@bugs.debian.org (full text, mbox):

From: David Gil <dgil@telefonica.net>
To: Filipus Klutiero <ido@vif.com>, 351043@bugs.debian.org
Subject: Re: Bug#351043: Determining severity
Date: Sun, 19 Feb 2006 12:13:17 +0100
Thank you for explaining in deep the problem Filipus. Though I think
this is not an RC bug, you have gave me good reasons to keep the
severity as serious. I am convinced that this would frustrate other
users like you.

Just one more note, from http://www.sudoku.com/rule.htm:
Every puzzle has just one correct solution.

Greetings,
David.





Merged 351043 375201. Request was from David Gil <dgil@telefonica.net> to control@bugs.debian.org. Full text and rfc822 format available.

Information forwarded to debian-bugs-dist@lists.debian.org, David Gil <dgil@telefonica.net>:
Bug#351043; Package gnudoku. Full text and rfc822 format available.

Acknowledgement sent to "David Hall (coding)" <hacking@gringer.dis.org.nz>:
Extra info received and forwarded to list. Copy sent to David Gil <dgil@telefonica.net>. Full text and rfc822 format available.

Message #53 received at 351043@bugs.debian.org (full text, mbox):

From: "David Hall (coding)" <hacking@gringer.dis.org.nz>
To: 351043@bugs.debian.org
Subject: Bug#351043 [gnudoku]: Puzzle generation, reasons for ambiguous behaviour
Date: Sat, 16 Dec 2006 23:53:36 +1300
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<move>& 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



Bug closed, send any further explanations to Anand Kumria <wildfire@progsoc.org> Request was from Lucas Nussbaum <lucas@lucas-nussbaum.net> to control@bugs.debian.org. (Wed, 17 Oct 2007 23:15:11 GMT) Full text and rfc822 format available.

Bug archived. Request was from Debbugs Internal Request <owner@bugs.debian.org> to internal_control@bugs.debian.org. (Thu, 15 Nov 2007 07:25:15 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Sun Apr 20 22:08:17 2014; Machine Name: beach.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.