Re: [Help-glpk] extremely difficult sudoku puzzle

[Diamantini Maurice]

Le 7 févr. 2010 à 19:44, Andrew Makhorin a écrit :

>> Just some remarks about complexity of sudoku
>> 1 - The difficulty of a sudoku grid is just for a human which has
>>    to build cell by cell the missing elements **without**
>>    enumerate (backtracking in difficult for an human :-).
>> 2 - A valid grid sudoku probleme has to had one and only once
>>    solution.
>> 3 - The difficulty of a grid is mesured from the rules the human
>>    has to use for filling the missing elements (without enumeration)
>> 4 - this grid is false because it has many solutions!
> 
> I cannot judge about the difficulty for a human, because I don't know
> how it could be measured.

The difficulty for a programm, is more to be able generate a suduko grid
with a given "difficulty" for a human to solve.
A book is available (some chapter are free)
  http://njussien.e-constraints.net/sudoku/eng-index.html


> However, the book, where I encountered the
> puzzle, is titled "Programming Sudoku" that assumes computer solution.
> Besides, inappropriate formulation may make the sudoku puzzle
> intractable even for electronic brain; see an eloquent example on p.5
> in the article "Rapid Mathematical Programming or How to Solve Sudoku
> Puzzles in a few Seconds" by Thorsten Koch:
> http://opus.kobv.de/zib/volltexte/2005/884/ps/ZR-05-51.ps.

Thank you, this is an excellent example.

-- Maurice