The New Sudoku Players' Forum

[eleven]

Hi dukuso,

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.

[dukuso]

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]

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=

[eleven]

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.

[denis_berthier]

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

[eleven]

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.

[denis_berthier]

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?

[eleven]

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

[denis_berthier]

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]

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