The New Sudoku Players' Forum

[Havard]

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!

Havard

[Havard]

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

[ravel]

Sep 12, 2005 Gordon 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

[gfroyle]

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

[ravel]

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)

[coloin]

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

[Havard]

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

Havard

[kjellfp]

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.

[coloin]

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]

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

[kjellfp]

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.

[coloin]

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

[Red Ed]

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.

[RW]

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

[JPF]

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

[gsf]

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