[Kde-games-devel] Killer Sudoku / Mathdoku

[Ian Wadham]

On 08/07/2015, at 7:52 AM, Richard Llom wrote:

> Ian Wadham wrote:
>> You will be pleased to hear that I have added Mathdoku and Killer Sudoku
>> to KSudoku, with a DLX (Dancing Links) solver.
>> 
> Cool :-)
> 
>> The Mathdoku is working
>> quite well, with sizes 3x3 up to 9x9, selected in the Settings dialog. It
>> still needs some user-friendly messages to be added, plus a little
>> "tuning" to ensure that the puzzle generator always behaves itself.
>> 
>> There is a 4x4 Tiny Killer, but the full 9x9 Killer Sudoku is on hold
>> until I  can get it to generate more realistic and interesting puzzles. 
>> They are far too hard ATM - too many possibilities and not enough leads,
>> even when using "rule of 45", "innies", "outies" and other tips.
>> 
> Not so sure about this, I think 9x9 is supposed to be incredibly hard.

9x9 Mathdoku is very hard, but 9x9 Killer Sudoku has the usual 3x3 blocks
to help you (unlike Mathdoku) and you cannot repeat a digit in a cage either.
These facts are a great help once you get a few values out.  The puzzle is
then more like a regular Sudoku.  Also there are some special techniques
for 9x9 Killer Sudoku, which do not usually work on Mathdoku.  For example,
if you have a column containing (thin) cages with totals 15, 16 and 18, but one
cage has a cell poking out into the next column (this is called an "outie"), you
can deduce that the outie contains a 4, because the whole column must add
up to 45 (called the "rule of 45"), 15 + 16 + 18 = 49 and 49 - 45 = 4.

> The difficulty rises with the grid size and I don't think its linear.

No, it is not. The difficulty also rises with the cage-size.  A large cage is likely
to have several possible sets of digits to reach its value.  Also, those digits
have N factorial possible arrangements (2! = 2, but 5! = 120, and so on).

> From my 
> Androip app for mathdoku[1] the new game / difficulty settings reads like 
> this:
> 4x4 easy
> 5x5 medium
> 6x6 hard
> 7x7 harder
> 8x8 hardest
> 9x9 ultimate

KSudoku will have a setting for the Mathdoku size (from 3x3 to 9x9) and the
Difficulty button will give you different maximum cage sizes, from 2 to 7 ATM.

> I mostly play 5x5 (around 8min) and 6x6 (~17 min) never went above…

That's good to hear. It is in line with what I am finding with KSudoku's version
of Mathdoku. 7x7 is not too hard, especially if you get multiplies with factor 7...

>> Nobody seems to have a good
>> algorithm for predicting the difficulty of a generated Mathdoku or Killer
>> Sudoku puzzle - or if they do, they are not publishing it… ;-)
>> 
> See above, maybe there isn't such and they just get harder by size.

With Mathdoku, grid size and maximum cage-size seem to be good
indicators of difficulty.  Also the the number of adds and subtracts vs.
the number of multiplies and divides and the number of single-cell
cages appear to be indicators too.  Adds and subtracts often have
more possibilities.

> But below is also another source to checkout ;-).
> [1]
> https://code.google.com/p/holoken/

Thanks, again.  I am also looking at http://www.killersudokuonline.com/.
But ATM I have just 3 days till the release freeze…

Cheers, Ian W.