The hardest sudokus

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

Postby ravel » Tue Nov 28, 2006 12:45 pm

tarek wrote:By the way, where is ravel........He must be on annual leave:D
I am sorry, i am really too busy in the moment:(

The Explainer update is great, thanx to RW i could add the ER top ten now.

I would be happy, if my program could rate the hard puzzles in 20 minutes. But i am still not finished with Tarek's lists (also cant run the program all the time), still 20 puzzles missing.

So i decided to try to rewrite it after Christmas. In the moment i only have some vague ideas for the algorithm inspired by gsf's program and also the nice solutions with single's subnets by Leon.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby merallas » Tue Nov 28, 2006 9:17 pm

Your program needs 20 minutes!!??
The longest time I need for one of the 20 puzzles is 450 s, but most of them are solves in less tha 60 s.
merallas
 
Posts: 39
Joined: 26 September 2006

Postby Karlson » Wed Nov 29, 2006 12:22 am

thats because the program uses many techniques instead of brute force to solve a puzzle
the recently implemented search for 'nested chains' consumes a huge timespan
Karlson
 
Posts: 26
Joined: 14 May 2006

Postby merallas » Wed Nov 29, 2006 1:27 am

Ok, I understand. On the other hand I also see a challence in optimizing the so called brute force techniques.

Another point which have my interest is the clones of sudoku's. With a rather simple program clones can be generated. Of a particular sudoku, I have generated more than 14000! clones. One of them is shown below.

007004003200900000080010060009003004500100300060070080000005007000700100000020050

Is it realy possible to find puzzle, from which this clone is made.
merallas
 
Posts: 39
Joined: 26 September 2006

Postby m_b_metcalf » Wed Nov 29, 2006 1:45 am

merallas wrote:Another point which have my interest is the clones of sudoku's. With a rather simple program clones can be generated. Of a particular sudoku, I have generated more than 14000! clones. One of them is shown below.


Do you really mean 14000!, or rather 14000(!)?

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Postby RW » Wed Nov 29, 2006 1:48 am

merallas wrote:Ok, I understand. On the other hand I also see a challence in optimizing the so called brute force techniques.

There's several brute force solvers around (like gsf's solver or dukuso's) that can solve all puzzles in fractions of a second, you still need to improve your 450 seconds a bit...

merallas wrote:Another point which have my interest is the clones of sudoku's.
...
Is it realy possible to find puzzle, from which this clone is made.

If you're talking about basic permutations to form equivalent puzzles, then there's billions of puzzles from which it could have been made, none of them more original than the other, so which one are we supposed to pick?

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ronk » Wed Nov 29, 2006 1:58 am

merallas wrote:Another point which have my interest is the clones of sudoku's. With a rather simple program clones can be generated. Of a particular sudoku, I have generated more than 14000! clones.

What is a "clone" of sudoku:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Ocean » Wed Nov 29, 2006 3:35 am

merallas wrote:Another point which have my interest is the clones of sudoku's. With a rather simple program clones can be generated. Of a particular sudoku, I have generated more than 14000! clones. One of them is shown below.

007004003200900000080010060009003004500100300060070080000005007000700100000020050

Is it realy possible to find puzzle, from which this clone is made.


It's no problem at all to identify the originals from "clones", or "scrambled versions" of previously published sudokus. Like this one, the "Escargot".
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby merallas » Wed Nov 29, 2006 8:37 am

Ok, thanks for the replies. I thought I was finished now, but I see that there is still some work to do.

My scrambling program did not count sudokus which has the same empty field pattern. But anyway, if there are so many versions of a particular puzzle, than the amount of realy original puzzles must be reduced dramatically. Is there in the meantime a view how many there are.

merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby RW » Wed Nov 29, 2006 9:02 am

merallas wrote:Is there in the meantime a view how many there are.

In this thread the amount of minimal puzzles in an average grid was estimated to be something between 10^15 and 10^17. Multiply that by the amount of essentially different grids (5472730538) and you get a rough estimate of how many essentially different minimal puzzles there is.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby merallas » Thu Nov 30, 2006 12:25 am

RW wrote:There's several brute force solvers around (like gsf's solver or dukuso's) that can solve all puzzles in fractions of a second, you still need to improve your 450 seconds a bit...
[RW


Hi RW,
When I was reading p29 of this site, I understood that e.g. gsf was not able to solve all puzzles. Furthermore I understand you need to enter all kind of codes dependent on the difficulty of the puzzle. My program is not so fast, but I am quite sure now that it solves any sudoku and finds out by itself if a more brute force is required.

Merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby gsf » Thu Nov 30, 2006 7:30 am

merallas wrote:When I was reading p29 of this site, I understood that e.g. gsf was not able to solve all puzzles. Furthermore I understand you need to enter all kind of codes dependent on the difficulty of the puzzle. My program is not so fast, but I am quite sure now that it solves any sudoku and finds out by itself if a more brute force is required.

there's been some confusion in this and other threads on this forum between solving and rating

in a rating context it should be "foo solver failed to rate puzzle bar" instead of
"foo solver failed to solve puzzle bar"

the problems alluded to above have been fixed in the latest release of my solver and I believe SE too

also, the extra options for the previous release to solve the recent hardest
were workarounds until the solver could be updated -- the workarounds
allowed users to use the old solver on unexpected puzzle variations until
the updated solver could be posted
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby merallas » Thu Nov 30, 2006 7:08 pm

gsf wrote:also, the extra options for the previous release to solve the recent hardest


Does this means, that each time when a harder sudoku is discovered you have to modify your program

merallas
merallas
 
Posts: 39
Joined: 26 September 2006

Postby gsf » Thu Nov 30, 2006 7:40 pm

merallas wrote:Does this means, that each time when a harder sudoku is discovered you have to modify your program

when the next level of hard is posted:
for rating -- yes
for solving -- no

remember that rating is based on techniques
sure one could base rating on backtrack tree search behaviour (like suexrate)
but that's missing the point of the current rating trends

my solver doesn't implement all known non-guessing constraints
so it is definitely possible that there exists a puzzle than can foil
the current proposition constraint logic used to rate the hardest
due to the missing constraint technique(s)
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby merallas » Thu Nov 30, 2006 10:25 pm

Thanks, it's more clear now. Looks quite complicate to me to find all those patterns by a program. However, it is still difficult for me to make a difference in guessing and non-guessing techniques. Also in the so called logical methods assumption are made in my opinion.

merallas
merallas
 
Posts: 39
Joined: 26 September 2006

PreviousNext

Return to General