help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] extremely difficult sudoku puzzle


From: Andrew Makhorin
Subject: Re: [Help-glpk] extremely difficult sudoku puzzle
Date: Sun, 7 Feb 2010 21:44:27 +0300

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





reply via email to

[Prev in Thread] Current Thread [Next in Thread]