[Kde-games-devel] New generator for KSudoku puzzles

[Ian Wadham]

Hi guys,

Back in July/August Inge Wallin and I were talking about Sudoku generators, see
      http://lists.kde.org/?l=kde-games-devel&m=131218747229985&w=2
I decided to follow his suggestion and search the web for algorithms.  I also wrote
to Johannes Bergmeier, the listed maintainer of KSudoku, both directly and via
this list, but have received no reply from him, see
     http://lists.kde.org/?l=kde-games-devel&m=131241631226930&w=2

I found a nice algorithm, written in Python and published on the Web, so I set
about transcribing it into C++, using the Qt library, and generalizing it to support
all the shapes and sizes of Sudoku puzzles in KSudoku, rather than just the
classic 9x9 puzzle.  My wife and I are particularly fond of Samurai puzzles,
but we get only one per week in our local newspaper.  My algorithm can be
extended to other shapes and sizes fairly easily by inheriting from one of the
classes and re-defining one or two short methods as required.

As I mentioned in my earlier emails (see above) there are some problems
with KSudoku that badly need fixing:
    - It mostly generates easy puzzles and the difficulty slider has no effect.
    - It takes an indefinite time to generate 16x16 and 25x25 puzzles and
      I usually have to kill it.
    - Several features seem to have quietly disappeared or ceased working,
      such as printing a puzzle or saving and restoring a puzzle.
I went back to the KSudoku code of 2 years ago, before the engine was
replaced.  It did generate better puzzles then, but many were a tedious
slog and got the thumbs-down from my chief tester (my wife).

After spending many days trying to understand both the existing and the
earlier code, in the hopes that their puzzle-generation methods might be
improved, I finally gave up on that.  There are thousands of lines of code,
piling abstraction upon abstraction and mostly uncommented, and I have
not been able to discover how and where it actually generates a puzzle.

So I redoubled my efforts on my own generator, trying out the results on
my wife as I went along.  The results were rather surprising and some of
my earlier efforts met with wifely scorn.  Words like "crap" were bandied
about.  And they talk about users hurting our feelings on kde-devel ... :-)

It is actually rather tricky to generate a difficult puzzle that is what one
might call "human" in scope and is really fun to solve, rather than some
mind-boggling wilderness of fragmented deductions and guesses.  My
wife described these as having no "theme" or "pattern" and being rather
boring to solve or attempt to solve.  So she gave up for lack of interest.
I guess computers are better at iterating over bitmaps to deduce values
and then guessing and backtracking when they are stuck --- and they
do not get bored.

Although the published algorithm I am using works by inserting clues
until a point where the solution can be entirely deduced and then removing
clues until one step before the puzzle becomes insoluble or has multiple
solutions, it seems that number of clues (filled in cells at the start) does not
have a lot to do with underlying difficulty, except for distinguishing Easy
and Very Easy puzzles.  I have examples of easy puzzles with a small
number of clues and hard ones with a larger number.   The published
algorithm uses number of guesses required as a measure of difficulty
(and indeed it is), but I have run dozens of published puzzles through
my solver and collected statistics from the algorithm, and it seems there
are many difficult puzzles that require no guessing at all.

My current difficulty measure is a weighted sum of number of guesses,
number of iterations over the entire board by the deducer method and
fraction of clues within the board size.  The algorithm is also in some
cases excluding guessing from the solution or excluding guessing
until a definite proportion of the board has been solved.  These mods
seem to make the puzzles more "human".  One of my recent puzzles
required guessing after only 11 moves, leaving nearly two thirds of
the board still to be filled in.  The computer had found about 50
pair-choices where a guess could be made and was quite happy
to start guessing and backtracking --- not so my wife!  That was
when I introduced the limits on guessing.

Anyway, the question is where to go next?  I have managed, after
a bit of unashamed hacking, to integrate my new generator (roughly)
into KSudoku and to be able to use the old and the new generators
side by side, but I am still tinkering with difficulty-setting approaches.

Should I just commit my changes to KSudoku SVN and record them
on the Feature List?  In a sense, I am fixing bugs, but the commit
would be about 3000 lines.  However I would be expecting to
remove more lines than that eventually, if the current engine is
superseded and deleted.

Or should I go via Review Board (which I am reluctant to do as I know
almost nothing about Review Board)?

OTOH should I just keep the new generator at home for my wife and
I to use and enjoy for years to come (it is Qt only and running on
a Macbook Pro at the moment)?

It seems to me that a direct commit is the way to go and would have
the least administrative overhead.  It could always be reverted.

Ideas anyone?
All the best, Ian W.