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: 3082
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: 3082
Joined: 10 February 2008

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

Postby denis_berthier » Mon Oct 02, 2023 5:45 am

Hi eleven,

The link you gave to your 26370 high SER puzzles: https://sites.google.com/site/sudoeleven/ is broken. Have you moved it to another place or did it disappear into the Internet limbo?
I've mentioned and used this collection several times in my classification analyses and I'd like to update my references to it.
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby eleven » Tue Oct 03, 2023 10:31 am

Hi Denis,

the files were lost, when google closed the classic sites (only the text was converted). I don't have them either (would have to look into old backups). So sorry.
eleven
 
Posts: 3082
Joined: 10 February 2008

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

Postby denis_berthier » Tue Oct 03, 2023 11:10 am

eleven wrote:Hi Denis,
the files were lost, when google closed the classic sites (only the text was converted). I don't have them either (would have to look into old backups). So sorry.

Indeed, I have a copy of the whole file of puzzles. I used it in my books for classification purposes. I can send it to you if you want it ;)
I just wanted to give some reference to it.
I know it is somehow included in ph2010, but I used it separately because the way it was generated was clearly defined.

[Edit]: I've computed the complete BpB classification of your collection and I plan to publish the results on GitHub as I've done with my classifications of mith's T&E(3) puzzles (https://github.com/denis-berthier/Classifications-of-TE3-Sudokus). But these detailed results are not very interesting if I can't give any reference to the puzzles. Do you mind if I re-post your collection there (with your name, of course), at least until you decide to re-publish it somewhere? BTW, I also have a pdf copy of your document "Hardest Sudokus,May 27, 2011"; do you mind if I also put a copy of it there?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby eleven » Wed Oct 04, 2023 4:01 pm

I never missed the old files, but of course it would be nice, if you republish them.
eleven
 
Posts: 3082
Joined: 10 February 2008

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

Postby denis_berthier » Thu Oct 05, 2023 4:22 am

eleven wrote:I never missed the old files, but of course it would be nice, if you republish them.

Hi eleven,
Thanks for your answer.
it'll take a few days to create the GitHub repository and to write the README stuff necessary to present it.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Fri Oct 06, 2023 5:43 pm

.
done: https://github.com/denis-berthier/Classification-of-TE2-Sudokus

The BpB classifications reported there for the whole collection where done with the SHC:
(http://forum.enjoysudoku.com/the-sudoku-hierarchical-classifier-shc-t42075.html).
They are the basis for Table 2.2 of [HCCS] (an extension of Table 11.2 of [PBCS]):
(https://www.researchgate.net/publication/374508822_Hierarchical_Classifications_in_Constraint_Satisfaction)
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Previous

Return to General