17-clue and 18-clue Sudoku update

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

Postby Havard » Sun Jun 03, 2007 3:15 pm

well, I think the 2-off, 2-on search is completed... The reason for the uncertainty is the fact that the search has been stopped for various reasons several times, but I think most sudoku in that list has had that treatment. However, I would not be surprised if a few more would pop up if someone did it again...

The main reason I have not been more thorough is that the 2-off, 2-on is so slow compared to my new favorite, the "make loads of 18's and search for 17's in them"-approach! It is quick, and it almost completely recreates the whole list of 17's every time it is ran! We are talking turning a few million 18's into over 30000 17's, and the whole thing takes less than one day to do!

The 3-off, 3-on is depressing. On the supercomputer I have been borrowing from Intel, an 8-core Clovertown, one sudoku completes in around 4 hours. And the two 17's I have done this search on, no new ones have popped out. On my laptop (pentium 4, 2.0 Ghz) the same search would take around 60 hours, with the whole list completing close to 300 years... I am sure a few hundered 17's would show up, but it hardly seems worth it, when you can create so many more 17's by making loads of 18's in a few days!:D

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby Havard » Mon Jun 04, 2007 12:01 am

wapati wrote:
coloin wrote:
Deanos 18 must be in a more remote area....is this effected by the lack of diagonal clues in 7/9 of the boxes ?

I am trying to think of ways to direct this.....

C


Good point. If so this rectangular 19 might be great grist.

http://forum.enjoysudoku.com/viewtopic.php?t=4147&start=459

:(3 off 1 on is pretty quick I hope?


I tried something similar to what you suggested here: http://forum.enjoysudoku.com/viewtopic.php?t=5461

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby ravel » Mon Jun 04, 2007 11:09 am

Sep 12, 2005 Gordon wrote:
gfroyle wrote:My techniques are purely based on perturbing existing solutions to get new ones - making small changes in a known 17 by altering or moving a couple of numbers and then hoping that the result will still be uniquely completable.

I do construct some 18s directly, and then hope that they will contain some 17s, which then go into the perturbation process themselves and so on..
This could be read also as description, what Havard does now.

To Coloin: I suspect, if dukuso would have thought in this direction at the beginning of the low clue search, he (and others then) would have found 17 clues with the same speed as Gordon. But we would'nt have this knowledge about solution grids now:)
ravel
 
Posts: 998
Joined: 21 February 2006

Re: Update...

Postby gfroyle » Mon Jun 04, 2007 12:52 pm

gsf wrote:when you get extra time could you enhance the Identify Me! field to treat a <<81 digit
entry as a puzzle id number
thanks


Done .. any number between 1 and MAXID is treated as an ID.

Please note that for all puzzles that I initially entered en masse (i.e. before the web submissions, the discoverer field is empty... ). Maybe we could try to retrofit the discoverers to them, but it would be a major effort and not currently at the top of the to-do list.

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby ravel » Tue Jun 05, 2007 3:35 pm

It is amazing, how easy it is with Havard's method to find 17 clues.
It took me an hour to implement 2off/2on and 2off/1on (with dukusos solver). Then i started with 20 21-clues (from my last hardest list), got 65 20-clues, 237 19-clues and 31 18-clues with 2off/1on, from those 3823 18-clues with 2off/2on (not repeated) and finally 38 17-clues from them (all counts for non isomorphic puzzles).
This took about 32 hours on a 1.5 GHz notebook. With a 2off/2on for the 17's i probably would find a couple more, but Havard already did it for the known list and only these 2 were new (and dont have non isomorphic 2off/2ons):
Code: Select all
.....6.8..571....3........4...7....5.........8......9...1...5.7.........9.2..8...
..34.........8.2...9....1.....3......1....8..5..7............7..8..2..9....5...3.
(i accidently checked in the first as Anonymous, when i wanted to check if its really new)

So i wonder, if this method was too trivial or too ingenious for the heroes of the minimum clue thread (except for Gordon):)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Tue Jun 05, 2007 4:13 pm

I think the feeling at the time was that since Gordon had probably got most of them there wasnt much point in trying very hard [possibly fair]

But since Gordon has been proceeding up to 40000, and now Haverd powering in with more optimized software and hardware I suppose the challange that Gordon and us have now is to understand/complete the proceess of what makes these 17clue puzzles.

I am of the opion that the 17puzzles occur because of the vast number of puzzles per essentially different grid. Almost all grids have a 19 in them somewhere.....because of the number of grids, hitting all the unavoidables in a grid with 17 clues happens - but not that often.

Well done on 2 more !

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Havard » Tue Jun 05, 2007 4:24 pm

excellent! I am very happy that someone else can confirm the almost too easy way to find more 17's! Great work ravel!:)

Havard
Havard
 
Posts: 377
Joined: 25 December 2005

Postby kjellfp » Mon Jun 18, 2007 7:01 pm

I have been reading this thread now and then, and thought I might start to contribute to the Sudoku discussions again. I wonder about ways to exhaustively find all 17s in a grid, and have some questions to those more experienced than me.

:?:How long time does it takt to get all 17s in a grid (or prove they don't exist)?

:?:In case you use the method with unavoidables, how many unavoidable sets do you find, and how? What size are they (number of symbols, number of fields, number of boxes)?

:?:For the set U of unavoidables you find, are they alone enough to prove that there is no 17, or does it happen that you end up with a set of 17 fields covering all elements of U, but where they all miss some (big) unavoidable not in U?

:?:Does it ever happen for a grid G and a (minimal) unavoidable U that G-U has more than two solutions?

I have some ideas both on finding unavoidables, as well as how to do exhaustive searches, but they are not fully implemented yet (so I can't tell if my ideas are good or bad). I can mention them later, but I'd like to know now whether my ideas are new or old thoughts.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby coloin » Mon Jun 18, 2007 7:15 pm

See"checker"

It answers many of your questions quite nicely....if all unavoidables are hit by the given clues then the grid is defined.

Some grids with high MCN can now be checked rather quickly

Your mission ....Speed it up 100 times !!!!

My thought some time ago.......except that Havard can now do this 3on search !!!!! [but not the slightly more time consuming 4on]

coloin wrote:Given the SF grid and these 14 common clues - a program can find the 29 17-clue soduku puzzles in around 10 seconds.
Code:
....4.7...8........1..........8....67........4.....2..3...7..................6.18

This subpuzzle has 621862 grid solutions which would prohibit a search for other 17s.

However a program [as yet unwritten] which could easily identify 4 or more unavoidable sets in any of these grid solutions would immediatly rule that grid out - so speeding up any search......
.....just a thought


C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby kjellfp » Mon Jun 18, 2007 7:50 pm

Thanks for the link, it was interresting. I see that checker does not fully use the algorithm I'm thinking about, but there's no need to believe that I have a faster method.

I've read Håvards posts. They're very interresting when it comes to finding new 17s, but I'm currently most interrested in how to find all of a given gird.
kjellfp
 
Posts: 140
Joined: 04 October 2005

Postby coloin » Mon Jun 18, 2007 7:57 pm

kjellfp wrote:.....when it comes to finding new 17s, but I'm currently most interrested in how to find all of a given gird.

Checker does just that

Initially it took days to check a grid for 17s but they optimized it so it doesnt repeat searches - it speeds up towards the end of its run......

I would be interested to see how your algorythm differs ?

C
coloin
 
Posts: 1633
Joined: 05 May 2005

Postby Red Ed » Tue Jun 19, 2007 6:23 am

kjellfp wrote::?:Does it ever happen for a grid G and a (minimal) unavoidable U that G-U has more than two solutions?
Yes, I've seen as many as six solutions.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Mon Jul 09, 2007 9:41 am

Havard wrote:well, I think the 2-off, 2-on search is completed... The reason for the uncertainty is the fact that the search has been stopped for various reasons several times, but I think most sudoku in that list has had that treatment. However, I would not be surprised if a few more would pop up if someone did it again...


I can now confirm that the 2-off 2-on has not been completed succesfully. On a 2-off 2-on on 9 new puzzles I stumbled upon several puzzles already in the list, for example:
Code: Select all
103000009007080000000020040000000200000000860005003000080060000000007003040000000 #35800
103000009007080000000020040000001000000040860005003000080060000000000003040000000 #40788

15 clues in common.

Most of the old puzzles I found had ID# > 30000.

Btw. Here's a few new 17s that I haven't completed a {-2+2} on and I won't be able to do that for the next month, so maybe someone else wants to do that:
Code: Select all
100006700000000000008200000000031000000000008009000025000000060802500000000070100 #40789
000400080010009000600070000200060000000000090000000840040000007090000000000230006 #40793
000001000400080700000002500705300000000000028090000000000900004000500000002000010 #40798


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

Postby JPF » Mon Jul 09, 2007 8:57 pm

RW wrote:Btw. Here's a few new 17s that I haven't completed a {-2+2} on and I won't be able to do that for the next month, so maybe someone else wants to do that:
Code: Select all
100006700000000000008200000000031000000000008009000025000000060802500000000070100 #40789
000400080010009000600070000200060000000000090000000840040000007090000000000230006 #40793
000001000400080700000002500705300000000000028090000000000900004000500000002000010 #40798

a {-2+2} on these 3 puzzles gives 4 other 17s but already posted by you : #40790, #40794, #40795, #40799.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Fri Jul 20, 2007 11:14 am

JPF, I see a consistent stream of 17's added by you in Gordon's catalog
I've got something going in the background too

here's what I've been doing
I use the hardest puzzle formula (encoded by -gH in my solver) to generate a stream of { 20 21 22 23 } clue puzzles
and pass those to
Code: Select all
{-2+1}x3    {-2+1}x4    {-2+1}x5    {-3+1}{-2+1}x5

off on sequences respectively to derive 17's

every ~20th 21 and every ~10th 22 produces one or more 17
this hits a new 17 ~1/day
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to General

cron