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 _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
