GNOME Bugzilla – Bug 599867
rejects valid solutions, bug in hitori_check_rule3
Last modified: 2009-11-06 20:41:30 UTC
Created attachment 146394 [details] screenshot of the puzzle [ This was originally reported in the Debian bug tracking system: http://bugs.debian.org/552510 ] See the attached screenshot for the board and a solution that Hitori accepted. An alternative solution uses the lower '8' in the 7th column. But hitori_check_rule3 rejects this, it doesn't realize all unpainted cells are connected. From the debug output: 1 1 1 1 1 1 1 1 X 1 1 X 1 1 1 1 2 X 1 1 X 1 1 1 2 2 X 1 1 X 1 1 2 2 2 1 1 1 1 1 2 2 2 1 X 1 X 1 2 2 2 X 3 X 4 1 2 2 2 2 3 3 X 1 group 1 base is 4 group 2 base is 2 group 3 base is 2 group 4 base is 4 ** (hitori:24378): DEBUG: Rule 3 failed I'm not sure exactly where the current algorithm goes wrong. If you want, I can whip up a patch which replaces it with a simple and stupid floodfill, which should be good enough for this game.
Created attachment 146395 [details] [review] hardcodes this particular puzzle I don't know which seed generated this puzzle, so here's a patch which hardcodes it.
Created attachment 146955 [details] [review] Alternative rule3 implementation This patch replaces hitori_check_rule3 with a simple flood fill based algorithm. This new code works fine.
(Sorry to take so long to reply. I'm really busy with work, but this is flagged in my mail queue, and I will get to it sometime soon. Thanks for waiting.)
Thanks. Committed with a few minor changes. commit a45262e4be1ade9c1737d01a5dd7af3b876fd95a Author: Philip Withnall <philip@tecnocode.co.uk> Date: Fri Nov 6 20:39:10 2009 +0000 Bug 599867 — rejects valid solutions, bug in hitori_check_rule3 Patch from Peter De Wachter <pdewacht@gmail.com> to reimplement the rule 3 check as a simple floodfill algorithm, to fix cases where it was incorrectly failing. Closes: bgo#599867 Also rename a variable so it doesn't conflict with the time() function. src/generator.c | 6 +- src/rules.c | 142 ++++++++++++++++++++++++------------------------------ 2 files changed, 66 insertions(+), 82 deletions(-)