The New Sudoku Players' Forum

by **dobrichev** » Mon Oct 14, 2019 6:00 am

Once blue discovered

Code: Select all: ........1.....2.3...4..5..6........3.1..7....87.............8.....81..7.52....... #49158 in minlex

one can apply

{-2,+3} finding 100 18s
{-2,+2} finding 358 new 18s
{-2,+2} finding 4547 new 18s
{-2,+2} finding 79509 new 18s + 34 new non-minimal 18s that are supersets of 20 known 17s

Clustering these 20 together with the new one, at {-4,+4}, ~~as coloin said,~~ the #49158 is in its own cluster

Hidden Text: Show

Code: Select all: pass {-4}, src=21, children=47504 10 clusters. ...................................1......23...4.56......4.7.8..2.......51.....9. =9 .................1..2..3..4.......5.....32.6.14....7.....17......8.....97....5... .................1..2..3..4.....2.5..6.....7.41....8......87.....9.....6.8.1..... .................1..2..3..4.....5..6.1..7.....78..........6..8....14.7....5....9. ................12..3..4.......1..56.34.2.....7...........87......3.....5.....4.9 ..............1..2..3...45.........1......67..82.4.......1.8......6.....4.5....9. ........1........2..3..4........3..5.1..6....6.7.........21..6....5..7....8...9.. ........1........2..3..4........3..5.1..6....7.6.........1...7....2..6..4.8....9. ........1........2..3..4........3..5.1..6....76..........1...7....2..6..4.8....9. ........1........2..3..4........3..5.1..6....76..........1...7....2..6..8.4....9. ...................................1.....2..3.14..5.6.....7.4..2.....5..3...1.... =1 ................12..3.45........1.....5..3....2....46......7......16....8.....5.3 ...................................1.....2.3..45..6.......4.7.....23......1....68 =1 ................12..3..4........5....1....32..6..7........185....29.....6.7...... ...................................1....23....45..6..........4..2.7...5.7..18.... =2 ................12..3..4.........3.5.6....4..78..1.........35..1...7...62........ ................12..3.45.........4.....6..3.758.2.........3.74..1........2....... ...................................1....23.4...5..6.2......78...1....9..24....... =1 ..............1.23..4.56.......12......7......38...6......9.5..1........27....... ..........................1..............2..3..4.5..6.....71.8..3.8.....29....... =1 ..............1..2..3.4..5.........6......2.7..5.3........87.9..2.9.....16....... ..........................1..............2..3..4.56..7...1......2.....8.6.....25. =1 ..............1..2..3..4.56......7...2..8....6..25.........7....1....8..58....... ..........................1........2.....3.....4.51..6.......14.2.7.....87....... =3 ................12..3.45.........4.......1.....6..35.7...5.6....1.....8.28....... ................12..3.45.........4.......1.....6..75.8...5.6....1.....9.29....... ................12..3.45.........4.......1.....63..5.7...68.....1.....9.29....... ..........................1........2.....3..4.15..6........7.1...4.8.....2....9.. =1 ................12..3.45........6..7.3.1.....4.....5.....8..3.9..5........72..... ..........................1........2.....3.1...4..5..6......7.....27..8.35....... =1 ........1.....2.3...4..5..6........3.1..7....87.............8.....81..7.52....... <=== #49158 #clust #puz 7 1 1 2 1 3 1 9

Clustering at {-5,+5} joins the new one to the large cluster, together with 10 other 17s

Code: Select all: pass {-5}, src=21, children=120978 8 clusters. ...........................................12....34..5...6..78...3........4.1.6.. =2 ................12..3..4.........3.5.6....4..78..1.........35..1...7...62........ ................12..3.45.........4.....6..3.758.2.........3.74..1........2....... ...........................................12..3.45......3.6..7.1.......48......9 =11 .................1..2..3..4.......5.....32.6.14....7.....17......8.....97....5... .................1..2..3..4.....2.5..6.....7.41....8......87.....9.....6.8.1..... .................1..2..3..4.....5..6.1..7.....78..........6..8....14.7....5....9. ................12..3..4.......1..56.34.2.....7...........87......3.....5.....4.9 ..............1..2..3...45.........1......67..82.4.......1.8......6.....4.5....9. ..............1..2..3.4..5.........6......2.7..5.3........87.9..2.9.....16....... ........1........2..3..4........3..5.1..6....6.7.........21..6....5..7....8...9.. ........1........2..3..4........3..5.1..6....7.6.........1...7....2..6..4.8....9. ........1........2..3..4........3..5.1..6....76..........1...7....2..6..4.8....9. ........1........2..3..4........3..5.1..6....76..........1...7....2..6..8.4....9. ........1.....2.3...4..5..6........3.1..7....87.............8.....81..7.52....... <=== #49158 .........................................1..2..3..4.56......7...2..8....6..25.... =1 ..............1..2..3..4.56......7...2..8....6..25.........7....1....8..58....... .........................................1..2.34.....5......12.....6.3....78.5... =1 ................12..3..4........5....1....32..6..7........185....29.....6.7...... .........................................1..2.34..5.6.....7.3..1.....5..2...4.... =1 ................12..3.45........1.....5..3....2....46......7......16....8.....5.3 .........................................1.23..4..2..5....6...7.8..9....21....... =1 ..............1.23..4.56.......12......7......38...6......9.5..1........27....... ...................................1.....2.....3..4.56....63....2....7..87....... =3 ................12..3.45.........4.......1.....6..35.7...5.6....1.....8.28....... ................12..3.45.........4.......1.....6..75.8...5.6....1.....9.29....... ................12..3.45.........4.......1.....63..5.7...68.....1.....9.29....... ...................................1.....2..3.45..6........7.4...3.8.....1....9.. =1 ................12..3.45........6..7.3.1.....4.....5.....8..3.9..5........72..... #clust #puz 5 1 1 2 1 3 1 11

~~For the 9 17s in the above cluster that aren't in coloin's cluster something wrong happens - either I am associating them wrongly, or coloin doesn't associate them wrongly. Here they are~~

Code: Select all: .................1..2..3..4.......5.....32.6.14....7.....17......8.....97....5... .................1..2..3..4.....2.5..6.....7.41....8......87.....9.....6.8.1..... .................1..2..3..4.....5..6.1..7.....78..........6..8....14.7....5....9. ..............1..2..3...45.........1......67..82.4.......1.8......6.....4.5....9. ..............1..2..3.4..5.........6......2.7..5.3........87.9..2.9.....16....... ........1........2..3..4........3..5.1..6....6.7.........21..6....5..7....8...9.. ........1........2..3..4........3..5.1..6....7.6.........1...7....2..6..4.8....9. ........1........2..3..4........3..5.1..6....76..........1...7....2..6..4.8....9. ........1........2..3..4........3..5.1..6....76..........1...7....2..6..8.4....9.

EDIT: Coloin doesn't use the same definition for clustering, no discrepancies there.

by **champagne** » Mon Oct 14, 2019 7:54 am

coloin wrote:Yes, very well done blue.....
dobrichev wrote:I am confirming that blue's puzzle is new, and that it is lone on its {-3,+3} island.

even a {-4+4} on the 49157 wouldnt have found it !
there are only 8 puzzles from the 49157 which share 12 common clues [and no puzzle sharing 13 clues]
Code: Select all
........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... # 49158 ... similarity 11 438 similarity 12 8 similarity 17 1 of note maybe for any 2 puzzles its difficult to not share at least 8 clues ?

at any rate #49158 is so remote a puzzle that we never found it !

Hi coloin,

So many work has been done in vicinity mode that your results could have been announced (assuming a possible new 17).
Mladen did a full -3+3 vicinity search. I have no idea how long would be a full -5+5 and we can not exclude to have a deeper exploration needed to cover all the field.

by **coloin** » Mon Oct 14, 2019 7:55 am

I have repeated the scan with gsf's program, and there may well be a clitch in it !

Code: Select all: output of sudoku-64 -CSf test1.txt similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ..............2.3..45............91.........237..6.......1........2.34...86...5.. similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ........1.....2..3.4.5........8..41...6......37.......1....6......2.35...8....... similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ........1.....2..3.45..........4....3.....1.2.7..6........9.46......35...8....... similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ........1.....2..3.45..........9..1.2.6......3.............64..7..2.35.........9. similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .......21.........94.............91...6......372.6.......1..4.....2.3....8....5.. similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ..2...6.1....8.....4..............1...6...9.237..6.......1........2.3....8....7.. similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .7......1.....2..3.45.........74......6......3...6.....9....4.....2.35.......1... similarity 12 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .9......1.....2..3.45..........8.5....6......37..6.....8....4.....2.3........1... similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ........7.....2..3.4..8..........91.........237..6.....5...14.....2..5.....3..... similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ........7.....2.63.4..5..........81.........237..6.....9.1..4.......3......2..... similarity 10 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ....8...1..2..5....45.......................2.7..6...3.....1.4....2.35...8.....9. similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ..............2..7.4....86.......91.........237..6.......1........2.3....86...5.. similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .........1....2....4..9.8.........15..6.....237..6.........5......2.3....8....9.. similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... ....7...13....5....45..............3........2.7..6.......1..4.....2.3.5..8....9.. similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .....1..........73..5.9...........1.......8.237..6......91..4.....2..5.......3... similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .......35.....2....4..8..........71.........23.5.6.......1..4.....2.3....8....9.. similarity 11 ........1.....2..3.45.............1...6.....237..6.......1..4.....2.35...8....... .......37.....2.....5.9..........81.........237..6.......1..4.....2.3.....9...5..

by **dobrichev** » Mon Oct 14, 2019 8:33 am

For gsf's tool there was discussion what "similarity" should mean. The differences could be due to different definitions, or of course due to a glitch.
EDIT:
~~My definition is that puzzles A and B belong to a same cluster of size N iif there exist subgrid AN of puzzle A and size N that matches any morph of any subgrid BN of puzzle B and size N.~~
~~Is there a third opinion?~~
My definition is that two puzzles A and B belong to a same cluster {-X,+X} if after applying {-X,+X} to A we reach a puzzle in the given set, and recursively applying {-X,+X} we finally can move to puzzle B.

The difference is that if we can indirectly move from A to B, then we are still in the same cluster.

This resolves the discrepancy - definitions differ.

by **coloin** » Mon Oct 14, 2019 8:38 am

champagne wrote:So many work has been done in vicinity mode that your results could have been announced (assuming a possible new 17).
Mladen did a full -3+3 vicinity search. I have no idea how long would be a full -5+5 and we can not exclude to have a deeper exploration needed to cover all the field.

The complete {-3+3} I believe took a period of months ... so I estimate a single {-3+3} on a 17 takes less than an hour ?
a single {-4+4} on a 17C even with optimizing it must take a day .....
Probably there are other remote 17C who exist on their own {-4+4} islands ...
But a aingle {-5+5} on a 17C must take a week perhaps

It might be possible to do a partial deep search if we fix clues in 4 boxes [B1245] [8 clues] and iterate 5 of 9 clues in B36789 [3 possibilities max per clue] but we are clutching at straws here !

by **coloin** » Mon Oct 14, 2019 8:43 am

dobrichev wrote:For gsf's tool there was discussion what "similarity" should mean. The differences could be due to different definitions, or of course due to a glitch.
My definition is that puzzles A and B belong to a same cluster of size N iif there exist subgrid AN of puzzle A and size N that matches any morph of any subgrid BN of puzzle B and size N.

Is there a third opinion?

I understand it did just that too !
Perhaps you could show clearly the 12 common clues in your puzzles

by **dobrichev** » Mon Oct 14, 2019 9:57 am

Right, I am applying different process - definitions differ and discrepancies are expected. Edited my posts.

by **coloin** » Mon Oct 14, 2019 10:17 am

Ok .... i see .... yes different definition ....
So theoretically working the other way, could you go easily from one of those 20 C17 puzzles to the #49158 ?

by **dobrichev** » Mon Oct 14, 2019 12:25 pm

Yes, going back and applying {-0,+1}, {-2,+2}, {-2,+2}, {-2,+2}, and finally {-3,+2}.

The forward process took more than a day using 4 CPU in parallel. Taking into account that the new 17 is expected to have much less than average 18s in its vicinity, the opposite process could take orders of magnitude more resources. Having no idea which 20 17s to start from, adds several orders of magnitude too.

The {-3,+3} on 17s took no months but 49 CPU years. A systematic search of, and around of all 18's, would take longer.

by **champagne** » Mon Oct 14, 2019 3:26 pm

dobrichev wrote:The {-3,+3} on 17s took no months but 49 CPU years.

This seems to be the order of magnitude of a full scan for the 665 distribution using the best process derived from blue's findings.

by **champagne** » Mon Oct 14, 2019 7:54 pm

champagne wrote:
dobrichev wrote:The {-3,+3} on 17s took no months but 49 CPU years.

This seems to be the order of magnitude of a full scan for the 665 distribution using the best process derived from blue's findings.

And if I am right, a depth -4+4 could be about 50 times longer

by **Mathimagics** » Tue Oct 15, 2019 12:24 am

champagne wrote:
dobrichev wrote:The {-3,+3} on 17s took no months but 49 CPU years.

And if I am right, a depth -4+4 could be about 50 times longer

If that is so, that's about 2500 CPU-years, and it extends the vicinity search space, but might miss some ...

Just to put that in perspective, blue's latest 18C functions (which are, I understand, rigorous) would allow, by my back-of-the envelope calculations, a definitive identification of all outstanding 17's in about 1000 CPU-years.

We identify every ED grid that has an 18C and enumerate all of its 18C puzzles (for a 4Ghz cpu, blue estimates avg 6s per grid). Any, and all, unknown 17C's would be found as a by-product of this process.

And, of course, a grid by grid treatment is a perfect candidate for a distributed-processing approach. 250 PC's with 4 cores devoted might knock it off in less than a year ... imagine if we could get 1000 PC's onto it! 8-)

(BTW: I have the flu right now, so please do allow for some level of fever-driven delirium on my part ... :lol:

)

by **champagne** » Tue Oct 15, 2019 5:35 am

Mathimagics wrote:
champagne wrote:Just to put that in perspective, blue's latest 18C functions (which are, I understand, rigorous) would allow, by my back-of-the envelope calculations, a definitive identification of all outstanding 17's in about 1000 CPU-years.

As blue's code is close in performance to the code in use on my side, there is some consistency in the figures;
I am planning about 40/50 core*years for the direct 17 search
You say 1000 core*years using the 18 search
I would expect a ratio closer to 50/60, but this is not so far.

by **Mathimagics** » Tue Oct 15, 2019 5:49 am

Ok, I am not exactly sure what you mean, Gerard ...

What do you mean by "direct search"?

And what ratio are you referring to?

I realise this probably just demonstrates my ignorance of your own code/project(s), and apologise in advance! :oops:

by **champagne** » Tue Oct 15, 2019 8:48 am

Mathimagics wrote:Ok, I am not exactly sure what you mean, Gerard ...

What do you mean by "direct search"?

And what ratio are you referring to?

I realise this probably just demonstrates my ignorance of your own code/project(s), and apologise in advance!

Direct search means that you limit the scan to 17 clues puzzles. This is the original code of blue.
Extending the search to 18 clues increases significantly the number of puzzles to explore.
Something similar to what happens when you compare a -3+3 vicinity to a -4+4 vicinity.

The 1:50 ratio is not too hard to forecast in the vicinity comparison. I assume that a similar ratio exists in a scan for 17 clues compared to a scan for 18 clues, but I am sure that blue has the right figure.

The New Sudoku Players' Forum

scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue

Re: scan solution grids for 17 clues as of blue