The making of a gotchi, a simple way to find extreme sudokus

Everything about Sudoku that doesn't fit in one of the other sections

Re: The making of a gotchi, a simple way to find extreme sud

Postby eleven » Wed Jan 19, 2011 3:39 pm

Hi dukuso,

dukuso wrote:These results are unexpected to me ... did eleven expect it when he/she started ?

After my results in the high clue search i was optimistic. But i did not expect to find so much.
Is the same method maybe useful to find hard exact-cover problems or hard
SAT-problems in general ?

A google search showed, that the genetic algorithm heuristic has been used several times to solve exact cover problems and other SAT problems like TSP.
E.g. i had a look at the sketchy article A New Genetic Algorithm for Set Covering Problems, which shows some similarities to what i have done.

Not being an expert, i dont know, how they perform compared to other methods, but i guess that there is a niche of special problems, where they give competitive results.
Of course all depends on one's choices, how the selection (fitness/filter) and mutation/crossover (expand) is defined.
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: The making of a gotchi, a simple way to find extreme sud

Postby dukuso » Thu Jan 20, 2011 11:22 am

this paper is for solving set cover problems not for creating hard instances, as I understand ?

I forgot to mention QWH-problems , "quasigroup with hole" , which is almost sudoku
and where your methods should also be useful and which are of some mathematical,
theoretical interest with lots of papers.

Maybe there is already a "movement" to create hard QWHs of given size ?!?
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: The making of a gotchi, a simple way to find extreme sud

Postby dukuso » Thu Jan 20, 2011 11:25 am

no google hits for "creating qwh" or "creating hard qwh" , 2 results for "creating hard sat" :

http://www.google.com/search?hl=en&q=%2 ... =&aql=&oq=
dukuso
 
Posts: 479
Joined: 25 June 2005

Re: The making of a gotchi, a simple way to find extreme sud

Postby eleven » Thu Jan 20, 2011 8:47 pm

Thanks for the link, dukuso.

I had no time to look closer yet, but i like the 3SAT problem, because its the most basic and concetrated NP complete one. So it might be interesting for me to try to create "hard" examples.
eleven
 
Posts: 1534
Joined: 10 February 2008

Previous

Return to General