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

[Inge Wallin]

On Friday, July 29, 2011 10:47:02 Ian Wadham wrote:
> 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 ...

Yeah, one of the pitfalls of not developing features in a branch...  What do 
you think would be best?  To try to revert the changes, keep it as they are or 
try to find out what the changes were supposed to lead and finish them?

> 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?

As an avid sudoku solver myself I have often wondered how they create the 
puzzles.  I guess there are articles about the subject...

	-Inge