No new 17s within {-2+2}

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

Re: No new 17s within {-2+2}

Postby GouinJP » Wed Nov 27, 2013 9:46 am

m_b_metcalf wrote: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
GouinJP
 
Posts: 285
Joined: 06 April 2013
Location: Montreal

Re: No new 17s within {-2+2}

Postby dukuso2 » Thu Nov 28, 2013 2:52 am

49152=2^14*3 , strange coincidence
dukuso2
 
Posts: 13
Joined: 28 November 2013

49157

Postby blue » Fri Nov 29, 2013 2:43 am

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)
blue
 
Posts: 573
Joined: 11 March 2013

Postby Afmob » Fri Nov 29, 2013 6:23 am

Nice! Did you post them elsewhere before or were they just forgotten?
Afmob
 
Posts: 130
Joined: 28 June 2011

Re: No new 17s within {-2+2}

Postby blue » Fri Nov 29, 2013 7:35 am

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.
blue
 
Posts: 573
Joined: 11 March 2013

Re: No new 17s within {-2+2}

Postby eleven » Fri Nov 29, 2013 8:48 pm

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
eleven
 
Posts: 1564
Joined: 10 February 2008

Re: 49157

Postby Serg » Fri Nov 29, 2013 10:22 pm

Hi, blue!
blue wrote:
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
Serg
2017 Supporter
 
Posts: 513
Joined: 01 June 2010
Location: Russia

Re: No new 17s within {-2+2}

Postby dobrichev » Fri Nov 29, 2013 10:54 pm

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.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: No new 17s within {-2+2}

Postby blue » Sat Nov 30, 2013 12:42 am

dobrichev wrote:The patterns are new too.

Interesting.

dobrichev wrote: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 :!:

Serg wrote: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.
blue
 
Posts: 573
Joined: 11 March 2013

Re: No new 17s within {-2+2}

Postby champagne » Thu Mar 27, 2014 11:10 am

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
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: No new 17s within {-2+2}

Postby dobrichev » Thu Mar 27, 2014 4:38 pm

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.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: No new 17s within {-2+2}

Postby champagne » Thu Mar 27, 2014 5:13 pm

dobrichev wrote: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..
champagne
2017 Supporter
 
Posts: 5680
Joined: 02 August 2007
Location: France Brittany

Re: No new 17s within {-2+2}

Postby dobrichev » Thu Mar 27, 2014 7:10 pm

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]
Last edited by dobrichev on Thu Mar 27, 2014 8:58 pm, edited 1 time in total.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: No new 17s within {-2+2}

Postby blue » Thu Mar 27, 2014 7:28 pm

champagne wrote: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

dobrichev wrote: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.

dobrichev wrote: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.
Last edited by blue on Fri Nov 18, 2016 6:52 pm, edited 1 time in total.
blue
 
Posts: 573
Joined: 11 March 2013

Re: No new 17s within {-2+2}

Postby dobrichev » Thu Mar 27, 2014 8:16 pm

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.
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

PreviousNext

Return to General