RE: [Help-glpk] extremely difficult sudoku puzzle

[Meketon, Marc]

I believe the most people use the "Dancing Links" algorithm that Donald Knuth 
publicized (he didn't claim he invented it, rather he made it better known and 
showed how to solve exact-cover problems with it).  The algorithm is basically 
an exhaustive search algorithm using clever linked-list structures that works 
very quickly for Sudoku.

See, for example, http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/

I first learned about it from:

http://www.c-sharpcorner.com/UploadFile/dumbledor/Sudoku11202005164648PM/Sudoku.aspx

In the above article, the author shows how generate Sudoku that are guaranteed 
to have exactly one solution.

A quick search shows that many other sudoku solvers and creation engines use 
the Dancing Links algorithm.


-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Diamantini Maurice
Sent: Monday, February 08, 2010 6:18 AM
To: address@hidden
Subject: Re: [Help-glpk] extremely difficult sudoku puzzle


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
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
---------------------------------------------------------------------------- 
This e-mail and any attachments may be confidential or legally privileged.  If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 

Thank you for your cooperation.
----------------------------------------------------------------------------