[Kde-games-devel] Re: KSudoku (was KDE games strategy)

[Ian Wadham]

On 29/07/2011, at 5:04 PM, Inge Wallin wrote:

> On Friday, July 29, 2011 01:15:29 Ian Wadham wrote:
>> On 29/07/2011, at 6:02 AM, Inge Wallin wrote:
>>> On Wednesday, July 27, 2011 01:07:49 Ian Wadham wrote:
>>>> I don't know if this qualifies as an "AI" but something bad happened to
>>>> the puzzle generator in KSudoku a while back and now the puzzles are
>>>> all too easy, no matter what difficulty level you choose.  It makes the
>>>> game far too easy for all but a raw beginner.  There are bug reports on
>>>> this and it certainly needs attention.  I had a quick look at it, but
>>>> am having trouble understanding the code ...
>> 
>> My apologies for posting twice: I am having trouble configuring my mailer.
>> 
>>> I don't really think that puzzle generation qualifies as AI...
>> 
>> OK.  It was just a thought.  The generation of good-quality Sudokus with
>> predictable difficulty appears to require a non-trivial algorithm and I
>> thought you might be interested ... :-)
> 
> Well...  I might be, but I have absolutely no idea how it's done.  But 
> wouldn't it be simple to just check if there were any strange commits during 
> the time when it broke?  Perhaps it's a trivial thing.

Thanks, Inge.  Actually I can tell exactly what happened.  When I said "something
bad", that was just a private opinion, I hasten to say.  FAIK it might have been the
beginning of some really great new development in KSudoku, but it is certainly
not complete.  On 25 November 2009 KSudoku's current author and maintainer
made a huge commit that was a major rewrite of the game engine and a complete
change of the puzzle-generation method.  Unfortunately I cannot understand much
of this new code and we have not heard from the author/maintainer for over a
year, but I could try writing to him ...

I have retrieved the KDE 4.3 branch version of KSudoku from SVN (from just
before the big change) and built it with a KDE 4.6.5 library and it works.  I am
currently "market-testing" the puzzles it generates with our family Sudoku
expert (my wife) ... :-)  This all arose a week ago when she saw I had a Samurai
Sudoku on the screen and said, "Can you make one of those?  I wannit !
I wannit !", but she cooled off when I explained that KSudoku generates mainly
easy puzzles.  She has lots of sources of 9x9 puzzles: daily paper, iPad,
iPhone and even a new network-aware H-P printer which downloads and
prints the H-P Sudoku of the day, but she gets only one Samurai Sudoku per
week, in Saturday's paper (it's five interlocking 9x9 grids).  KSudoku's great
strength IMO is that it can handle several kinds of Sudoku layout, including
Samurai.

What interests me are the differences in quality and difficulty of the Sudokus
from different sources.  All are computer-generated AFAIK.  By "quality"
I mean interest to the person solving it.  Does it have branch points?  Does
it yield to sophisticated thought (like Chess) or is it, as my wife says, "a hard
slog" (tedious and repetitive evaluation of alternatives?)?  What is it in the
puzzle generation algorithms that makes the difference?  Why is it that even
the best puzzle sources sometimes seem to throw up an easier problem
but call it Tough or a harder one and call it Gentle?  Is this just a subjective
thing or are there objective (algorithmic) reasons behind it?

Cheers, Ian W.