The New Sudoku Players' Forum

[GouinJP]

I was surprised to find this puzzle:

Code: Select all

3........4.......8...2..1...1...56...2............4.3.95.....4....7........1....9

 3 . . . . . . . .
 4 . . . . . . . 8
 . . . 2 . . 1 . .
 . 1 . . . 5 6 . .
 . 2 . . . . . . .
 . . . . . 4 . 3 .
 9 5 . . . . . 4 .
 . . . 7 . . . . .
 . . . 1 . . . . 9  ED=2.6/1.5/1.5


in yesterday's edition of Die Welt (Hamburg). I assume it's a morph of a known puzzle, but maybe someone could check?

Thanks,

Mike Metcalf

Hi

# 8598
000000000000000012003045000000000000000100340260700000000200006004000080900070000

It is a morph of 8598.

JPS

[dukuso2]

49152=2^14*3 , strange coincidence

[blue]

As 49157 is prime ...

Code: Select all

........1.......23..4..5..........6.....4.....1..78..9...6...4..3.9.....8.....7.. # 49153
........1.......2..34.56...........3..5...1..7.82..........9.8.....3....1.......2 # 49154
........1.....2.....3....4.....4.......5...3.26......7...6.7.....51.....82....5.. # 49155
..............1.23..4.5...1......4......6..7..3..........7.3.....8.....62.71..... # 49156
........1.......2...3.45...........3......4.216.7..........48...5..3....2......7. # 49157


(found around the time that Gary McGuire made his "no 16s" announcement)

[Afmob]

Nice! Did you post them elsewhere before or were they just forgotten?

[blue]

I didn't post them, and for a long time I thought I had lost them.
A few weeks ago, I found them at the bottom of an old source code file.

[eleven]

Congratulations on these, blue.
It was already hard to find a 17, when i had tried it for some time, years ago. And mine turned out to be part of the big {-1+1} cluster

Maybe OT: I read in wikipedia: "A few 17-clue puzzles with diagonal symmetry were provided by Ed Russell, after a search through equivalence transformations of Gordon Royle's database of 17-clue puzzles.[citation needed]". Is that true ? I don't remember 17's with diagonal symmetry.
[Edit:]Oh, please forget it. I did not mind the newby rule "first search then ask": Maybe someone wants to add the citation in wikipedia: http://forum.enjoysudoku.com/symmetrically-clued-17s-t3570.html

[Serg]

Hi, blue!

Code: Select all

........1.......23..4..5..........6.....4.....1..78..9...6...4..3.9.....8.....7.. # 49153
........1.......2..34.56...........3..5...1..7.82..........9.8.....3....1.......2 # 49154
........1.....2.....3....4.....4.......5...3.26......7...6.7.....51.....82....5.. # 49155
..............1.23..4.5...1......4......6..7..3..........7.3.....8.....62.71..... # 49156
........1.......2...3.45...........3......4.216.7..........48...5..3....2......7. # 49157


I confirm you have found 5 new 17-clue puzzles. Fantastic result! What method did you use?

Serg

[dobrichev]

Hi blue,

Congratulations! Great result!

Solution grids of these 5 17-s are different from each other and from the old ones. The patterns are new too.

BTW I immediately looked at the bottom of my old source files and found no new 17s there.

[blue]

The patterns are new too.

Interesting.

BTW I immediately looked at the bottom of my old source files and found no new 17s there.

Be sure to double check the directory with the 0-byte "new17s.txt" file

What method did you use?

The "usual method (?)" ... {-1,+1} changes and removing redundant clues ... but with a twist, to try to avoid the large {-1,+1}-connected class of 18's. I'ld use that method for as long as it took to produce a few hundred 18's -- collecting them, but not checking them yet. Then I'ld throw out everything but the 18's, and run {-1,+1} code on those, trying to collect the old and new puzzles into {-1,+1}-connected classes. When a class size reached some threshold (200? 400?), I'ld stop testing puzzles from the class, but let it continue to grow by class merging. When the small classes had been completely tested, I'ld throw everything out, and start over. Puzzles to be tested "next", were selected at random from the (union of the) small classes. I also experimented with running {-2,+1} code on the small/closed classes, and in the initial (18-producing) phase.

Running 4 cores, it was still days between new 17 hits. It was a little disappointing, from what I recall. I'ld make some change to the code, get a lucky hit in the first 24 (?) hours or so ... and then go another week without finding anything.

[champagne]

Hi Blue and others,


Interesting result.

To change slightly my mind in the sudoku area, I was wondering whether it would be possible to make an exhaustive (or nearly exhaustive) search of the 17 clues puzzles.
The fact that blue found new ones is positive.

Who knows what has been done in that direction.

I have my own idea to test if that is feasible, but I don't want to redo what is already existing

[dobrichev]

Hi Chanpagne,

You can read the Gary McGuire's article and the blue's post just before yours.

Also blue's observation that I have plenty of empty files named new17s is correct.
I doubt the 17s exhaustive search would take only 10x resources compared to 16s without further algorithm improvements. I have some points in mind.

[champagne]

Hi Chanpagne,

You can read the Gary McGuire's article and the blue's post just before yours.

Also blue's observation that I have plenty of empty files named new17s is correct.
I doubt the 17s exhaustive search would take only 10x resources compared to 16s without further algorithm improvements. I have some points in mind.

Hi mladen,

Thanks for the link. My first impression is that I have in mind something different, but I have to read carefully the article.

I intend to work in 2 steps

a) finding all max text patterns to scan
b) scanning these patterns.



My impression is that filtering morphs on patterns with all constraints should not give huge volumes of patterns (currently, we have nearly one pattern per puzzle in the 17 clues file). It should not be too long with the appropriate process.

I have seen only 2 different patterns whose max text form start with 1..1... This is a good field for experimentation. We have not so many ED patterns with that start.

On the other side of the field, only one pattern starting with 1111..1.. produced puzzles, but the generation of patterns is easier in the form 222222221 (2 clues per row except one), the only possibility with the start 1..1..

[dobrichev]

so you have 5E+4 patterns with known 17s out of 1E+17 possible 17-clue patterns reducible to 4E+9 after VPT; you managed to do search within the known ones thinking you are doing "nearly exhaustive" search? In my standards testing one of 1E+5 patterns is far not exhaustive.

BTW there is only one pattern with 30+ puzzles and somewhere I read it has been searched and no new puzzles have been found.

[edit: corrected the number of all possible patterns, the reduced number and the portion]

[blue]

I intend to work in 2 steps

a) finding all max text patterns to scan
b) scanning these patterns.

This won't be the best approach. The number of patterns to scan (after filtering out impossible patterns), will be larger than the number of canonical grids by small factor ... 3-5 range (?). With effort, you might me able to scan a pattern in under an hour, but Gary McGuire's code, suitably modified, can check a grid for 17's, in well under a minute.

Re: Gary McGuires code

I doubt the 17s exhaustive search would take only 10x resources compared to 16s without further algorithm improvements. I have some points in mind.

This is true. The code to generate the puzzles, takes ~8 times as long for 17's, but the number of puzzles that it produces, goes up by a factor ~150, and the fraction of time spent in the solver, becomes significant (but not unreasonable). I tried something along the lines of what I suggested at the bottom of this post<broken link>, but without "feedback", and was able to get the time per grid down to ~22 seconds -vs- 2.8 for 16's.

Best Regards,
Blue.

P.S.

so you have 5E+4 patterns with known 17s out of 4E+31 possible 17-clue patterns reducible to 1E+25 after VPT;

I see we're posting at ~ the same time here.
I get a much smaller pattern count, after VPTs ... ~38e9.

[dobrichev]

The search possibly could be improved by

• Checking whether "dead clues" entirely cover a known UA set
• Checking for redundant clues at earlier stages
• Partial reusing of the intermediate search results for "neghbour" grids - those that differ in permutation of digits within a single UA

I played with dynamic addition of UA after unsuccessful check for a single solution and found it unproductive. Large UA sets don't add value.