No new 17s within {-2+2}

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

No new 17s within {-2+2}

Postby dobrichev » Wed May 16, 2012 5:01 pm

Here in 2007 Havard reported he did exhaustive search for new 17-clue puzzles by removing 2 and adding 2 clues in all possible ways on the known at this time 17s.
I am confirming that there is no any unknown puzzle at {-2+2} around the currently known 49152 puzzles.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

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

Postby Serg » Wed May 23, 2012 10:30 pm

Hi, Mladen!
Are you sure are there 49152 currently known 17-clue valid puzzles? I loaded 49151 17-clue puzzles from Gordon Royle site several months ago. Has anybody really found new 17-clue valid puzzle last time?

I'd like to propose nuclear phisycs analogy for {-n+n} search. I think it is amusingly.

You know some nuclei of chemical elements are stable, but others - not stable. If a nucleus is not stable, it can decay to another nucleus and elementary particles. This process is called as radioactivity.

When we talk about sudoku we can imagine that collection of valid puzzle's cells forms nucleus. If puzzle is not minimal, we can subtract several cells containing clues from original puzzle, but transformed puzzle will still have unique solution only. We can treat such cells subtraction as radioactive decay - original nucleus emits another simple nucleus having several nucleons (cells). The final state of the nucleus (puzzle) is stable, because no nucleons (cells) can be emited (subtracted).

Searching for other valid puzzles within {-2+2} resembles me nuclear reactions, when 2 nuclei are colliding each other. If there is 1 way only to get minimal valid puzzle after adding 2 cells with clues - to subtract these extra cells, we can talk about elastic scattering. A nucleon hits another nucleon and they form common nucleon "cloud". Subtracting extra cells implies emitting of colliding nucleus. Elastic scattering is not interesting. But if it is possible to subtract some cells (not extra cells) of original puzzle preserving its validity, we can talk about inelastic scattering, i.e. about nuclear reactions.

Your search results imply that known 17-clue nuclei (puzzles) are very stable (minimal). No inelastic scattering was observed.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Postby Afmob » Thu May 24, 2012 4:58 am

You can find the 49152th 17 puzzle here.

Code: Select all
........1.....2.....3....45....463....5.......4...1......7...3..1.5.....8.....2.. # 49152
Afmob
 
Posts: 130
Joined: 28 June 2011

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

Postby dobrichev » Thu May 24, 2012 5:40 am

Check for this puzzle in you DB
Code: Select all
........1.....2.....3....45....463....5.......4...1......7...3..1.5.....8.....2.. # 49152

Edit: Afmob is faster than me.

I like your analogy with nucleus but there is one weak point - in the nature simple nucleus (hydrogen) are stable. Analogy is still applicable for high-clue puzzles. In order to get a stable configuration you need huge energy and the rest is matter of chance.
It is known that the most stable configuration is iron (Fe) but for some reason the portion of iron nucleus in the universe is extremely small. Maybe it is the same for the published puzzles since anomalies are always more attractive.

Back to the topic.
The existence of a black list with fruitless subgrids of size 15 hypothetically could help in some degree in some generation methods. For example if you do {-/+} at final stage, then knowing that your puzzle contains some of the blacklisted subgrids you know that you must touch this area, else you will eventually find already known puzzles traversing this "promising" and therefore large subtree. I have no idea how this can be done in computationally efficient manner.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

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

Postby champagne » Thu May 24, 2012 6:41 am

I would like to update my old list of the known 17 clues puzzles.

what is the link for downloading

thanks

champagne
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

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

Postby dobrichev » Thu May 24, 2012 7:21 am

I uploaded the 17's list here.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

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

Postby Serg » Thu May 24, 2012 7:40 am

Hi, Afmob, dobrichev!
Thank you for news in 17-clue puzzles area.

For dobrichev.
Thanks for updated 17-clue puzzles list.
About idea of using {+n-m} search results in exhaustive search. The idea looks like crazy, but perhaps it has sense...

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

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

Postby champagne » Thu May 24, 2012 8:18 am

dobrichev wrote:I uploaded the 17's list here.

thank you, I got it
champagne
2017 Supporter
 
Posts: 5614
Joined: 02 August 2007
Location: France Brittany

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

Postby coloin » Fri Jun 01, 2012 12:03 am

From a recent post here

Serg wrote:
Code: Select all
2 2 2
2 2 2
2 2 2
............
If we filter out patterns having 2 empty rows (columns) in a band (stack), than we'll get 17,429,658 essentially different patterns.
Serg


thanks
some of those maybe wont have puzzles too ...... maybe not that many though

im not sure of the following with respect to 222222222-18s

and my guestimate is
average number of puzzles per pattern = maybe 50 -100
proportion of all 18-puzzles with this configuration - ? 5 - 10 % [cant see how to get a random sample easily]

1.6 billion 18s estimated total
80 - 160 million 18s with 222222222 box config. pattern

its pretty easy to generate these {-2+2} keeping within the box
either of
1. { -2 from one box +2 back in the box}
2. {-1 from 2 different boxes + 1 back in each box}

given the number of puzzles ......its too difficult for me to program and file :(

any non-minimals [17-puzzles] are easily found [they will be associated with 8 different 222222222-18s]

if you generated the total 2084 17-puzzles with 222222221 box config without a new one then i would say all have been found.

i generated over 300000 222222222-18s
in these there were over a 1200 222222221-17s
unfortunately none were new

C
coloin
 
Posts: 1629
Joined: 05 May 2005

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

Postby dobrichev » Fri Jun 01, 2012 2:01 pm

Code: Select all
givens per digit
222222221   10
322222211   5299
322222220   963
332222111   16123
332222210   12009
333221111   3694
333222110   9945
333311111   24
333321110   307
422222111   37
422222210   33
432221111   181
432222110   497
433221110   30

givens per box
222222221   2084
322222211   16764
322222220   302
332222111   17048
332222210   1543
333221111   4957
333222110   1530
333222200   21
333311111   200
333321110   195
333322100   23
333331100   1
422222111   899
422222210   115
432221111   1901
432222110   525
432222200   4
433211111   670
433221110   265
433222100   19
433311110   13
442211111   32
442221110   24
443211110   8
443221100   3
522222110   2
532211111   1
532221110   2
533211110   1


It sounds more promising to target the following two distributions
Code: Select all
322222211   16764
332222111   17048
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

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

Postby coloin » Fri Jun 01, 2012 10:58 pm

Indeed

It would be a useful tool to be able to filter puzzles with {xxxxxxxxx} digit or [xxxxxxxxx} box distributions.

I was surprised that i got so many ~ half of the 17-puzzles with Box {22222221}.

I think i generated them with alternating {-1+1} and then a gridchecker --similar 2 on the new ones.

Would be a lot easier with the filter.

On the 300000 222222222-18s I am doing a complete {-2+1} {It will take 3 days} all the puzzles will be either
222222221
322222220
322222211

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby Afmob » Mon Dec 03, 2012 9:22 am

I claim #49153 :D.

Code: Select all
........1.......23..4..5........6..5.4....7..12...........8.......12......63..4..   #49153

I haven't done a {-n+n} search on it, so you might find other new ones.

Edit: As dobrichev pointed out this is not a new puzzle.
Last edited by Afmob on Mon Dec 03, 2012 1:13 pm, edited 1 time in total.
Afmob
 
Posts: 130
Joined: 28 June 2011

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

Postby dobrichev » Mon Dec 03, 2012 12:59 pm

Hi Afmob,

Unfortunately, your puzzle is a morph of this one, which is #38534 in rowminlex ordered collection of 49152.
Code: Select all
........1.......23..2..4........2.5..3.......16....7......16......83......7...4..
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

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

Postby Afmob » Mon Dec 03, 2012 1:13 pm

You're right, dobrichev. There were some errors in my 17 database file.
Afmob
 
Posts: 130
Joined: 28 June 2011

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

Postby m_b_metcalf » Wed Nov 27, 2013 8:14 am

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
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Next

Return to General