## giant sudoku's (16x16, 25x25, 36x36 .... 100x100)

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Re: re: 144-squared triples

Pat wrote:for diagnostics, could you please post the known cells at the point that your program stops? then hkociemba could run his program
starting at that point---

This is a very good idea. If Mike gives me the partially solved puzzle in the standard format it would just take seconds to see how my program proceeds. In principle it would be only necessary to analyze the lines of the solving process of my program until a new cell is filled to see what Mikes program misses in this situation (or what my program does wrong - what I do not hope of course).
hkociemba

Posts: 66
Joined: 09 July 2017

### re: 144-squared triples

hkociemba wrote:
the first time a triple is needed is line 671:

hidden tuple of size 3 in block:
r39c76 <> 117,136
r39c78 <> 136

makes me wish i had a detailed view of that box---

• r39c76 had the 3 possibilities of the trio
PLUS just these 2 -- 117,136
• r39c78 had the 3 possibilities of the trio
PLUS just this 1 -- 136
• and the 3rd cell of the trio is not even mentioned
-- it had the 3 possibilities of the trio
PLUS NONE !!

Pat

Posts: 3920
Joined: 18 July 2005

### Re: re: 144-squared triples

Pat wrote:
• r39c76 had the 3 possibilities of the trio
PLUS just these 2 -- 117,136
• r39c78 had the 3 possibilities of the trio
PLUS just this 1 -- 136
• and the 3rd cell of the trio is not even mentioned
-- it had the 3 possibilities of the trio
PLUS NONE !!
I checked it with the debugger, the triple consists of the numbers 17, 37 and 69 and yes, the corresponding cells in block 43 have almost no candidates left to be excluded. Everything looks ok.
hkociemba

Posts: 66
Joined: 09 July 2017

### Re: re: 144-squared triples

m_b_metcalf wrote:
Pat wrote:for diagnostics,
could you please post the known cells
at the point that your program stops?

then hkociemba could run his program
starting at that point---

That's a good idea that I'll come back to if my investigation gets no further.

In the Patterns Game, there have been 408 submissions with Sudoku Explainer ratings of the form 4.0/x/y or 4.2/4.0/z; they are in the first file below. My program solves them all, using the hidden triplets code each time. However, it fails to complete the 144x144_triples puzzle, stopping at the point as shown in the second attachment. I'd be glad for any enlightenment. The puzzle does get solved by other methods, just not by hidden triplets.

Thanks,

Mike Metcalf

P.S. There is a curious anomaly: the puzzle no. 66, from Game 17,
Code: Select all
`009000600000301000800050002050708030008000700070503040200030009000407000006000100 # 138    4.0/4.0/3.2 - m_b_metcalf `

is now rated as 7.2/7.2/3.2 (but has two hidden triplets as found by Sudoku Explainer in its third and fifth steps, as well as by my own program).

Edit: File attachments deleted.
Last edited by m_b_metcalf on Sat Jun 30, 2018 5:49 am, edited 4 times in total.

m_b_metcalf
2017 Supporter

Posts: 12441
Joined: 15 May 2006
Location: Berlin

### Re: re: 144-squared triples

m_b_metcalf wrote:In the Patterns Game, there have been 408 submissions of the form 4.0/x/y or 4.2/4.0/z; they are in the first file below. My program solves them all, using the hidden triplets code each time. However, it fails to complete the 144x144_triples puzzle, stopping at the point as shown in the second attachment. I'd be glad for any enlightenment.

First of all I do not understand the terms "form 4.0/x/y or 4.2/4.0/z". Maybe you can explain this or give me a link where these terms are explained.
Feeding problem144.txt to my solver I copied the solving progress until one new entry was found. With 381 steps this is much more than what I would have expected! I rewrote some of my code to make the output for hidden and naked tuples more compact and added also more information. Hope you reach this hiddens single in column 15 somehow!

P.S: I entered 009000600000301000800050002050708030008000700070503040200030009000407000006000100 # 138

In my opinion it has no hidden triplets. It cannot be solved with basic methods, even worse my solver cannot apply any basic method at all here.
Attachments
continuation144.txt
hkociemba

Posts: 66
Joined: 09 July 2017

### Re: re: 144-squared triples

hkociemba wrote:First of all I do not understand the terms "form 4.0/x/y or 4.2/4.0/z". Maybe you can explain this or give me a link where these terms are explained.
[snip]
P.S: I entered 009000600000301000800050002050708030008000700070503040200030009000407000006000100 # 138

In my opinion it has no hidden triplets. It cannot be solved with basic methods, even worse my solver cannot apply any basic method at all here.

Sorry for being too terse. I have edited my post to add more explanation. I'll look into searching for the hidden single.

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 12441
Joined: 15 May 2006
Location: Berlin

### re: 144-squared triples

hkociemba wrote:
Feeding problem144.txt to my solver
I copied the solving progress until one new entry was found.

With 381 steps this is much more than what I would have expected!

Hope you reach this hidden single in column 15 somehow!

steps 1-369 are singles,intersections,duos
-- we can assume those are all found

at this point,
you found two "hidden" trios
(steps 370+371)
of which the 2nd

hidden tuple of size 3 with numbers 37, 63, 71 in block 17:
r13c57 <> 97,121, r16c49 <> 53, r___c___ <> NONE,
is again of that un-usual type mentioned in my previous post --
one of the 3 cells of the trio
un-usual -- presents an opportunity for software to fail.

Pat

Posts: 3920
Joined: 18 July 2005

### re: 144-squared triples

and a little later
(step 375)

hidden tuple of size 3 with numbers 35, 55, 118 in block 74:
r76c22 <> 114, r___c___ <> NONE, r___c___ <> NONE,
is even more un-usual,
two of the 3 cells of the trio
have NO exclusions

Pat

Posts: 3920
Joined: 18 July 2005

### Re: re: 144-squared triples

Pat wrote:
hidden tuple of size 3 with numbers 35, 55, 118 in block 74:
r76c22 <> 114, r___c___ <> NONE, r___c___ <> NONE,
is even more un-usual,
two of the 3 cells of the trio
have NO exclusions

Well, yes, that all has to be foreseen in the hidden triple algorithm. This is the minimal case of, e.g., 1,2/1,3/2,3,4, where the triplet values each appear twice only and there is just one alien value. That's why testing with the ht.txt file was necessary.

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 12441
Joined: 15 May 2006
Location: Berlin

### re: a 7.2 was previously rated 4.0 ??

hkociemba wrote:
I do not understand the terms "form 4.0/x/y or 4.2/4.0/z"

the Patterns Game
uses the triple rating x/y/z

hkociemba wrote:
I entered
009000600000301000800050002050708030008000700070503040200030009000407000006000100 # 138
it has no hidden triplets

It cannot be solved with basic methods

even worse my solver cannot apply any basic method at all here

right.
it starts with 2 X-wings.
trios follow,
but solving this puzzle requires tougher methods
("forcing chains" rated 7.2)

Pat

Posts: 3920
Joined: 18 July 2005

### re: "hidden" triples

m_b_metcalf wrote:

In the Patterns Game, there have been 408 submissions with Sudoku Explainer ratings of the form 4.0/x/y or 4.2/4.0/z; they are in the first file below.

My program solves them all,
using the hidden triplets code each time.

{ EXCEPT: }
a curious anomaly: the puzzle no. 66, from Game 17,
009000600000301000800050002050708030008000700070503040200030009000407000006000100 # 138 4.0/4.0/3.2 - m_b_metcalf
is now rated as 7.2/7.2/3.2

re 4.2 i would re-phrase,
you can find the triplets but they CANNOT solve the puzzle.

even those rated 4.0
may occasionally require X-wing
(in which case,
again you can find the triplets but they CANNOT solve the puzzle).

and i can probably find a test-case rated 3.2
which you CAN solve with triplets
(the X-wing being replaced by subsets).

Pat

Posts: 3920
Joined: 18 July 2005

### re: 144-squared triples

m_b_metcalf wrote:Well, yes, that all has to be foreseen in the hidden triple algorithm. This is the minimal case of, e.g., 1,2/1,3/2,3,4, where the triplet values each appear twice only and there is just one alien value.

so this leaves you to review continuation144.txt
step by step

including steps 1-369
(singles,intersections,duos)

Pat

Posts: 3920
Joined: 18 July 2005

### re: triples

Pat wrote:
i can probably find a test-case rated 3.2
which you CAN solve with triplets
(the X-wing being replaced by subsets).

well the 3.2 i found
uses a "naked" triplet
(thus irrelevant to discussion of "hidden" triplets)

1.......2.3.4..5....2....6..5.31.......7.8..4....95....7....4....6....8.9...2...6

champagne # 205 # (36210) # (discussion)

(Layout 205 of the Patterns Game)

Pat

Posts: 3920
Joined: 18 July 2005

### Re: giant sudoku's (16x16, 25x25, 36x36 .... 100x100)

I solved the 144x144triples.txt with the SAT-solver only without applying any basic methods before and it gave me a unique solution which was identical to the basic method solver. So I really do not believe that there is something going wrong with my code. I additionally give you 4 triplet-minimal examples for 16x16 below (since I now see that the SE rating of Swordfish and X-wing is lower than for hidden triplets I explicitely state that these are not included in the set of used methods here) which all need triplets to be solved and you can check if there is a problem with these with your solver:

Hidden Text: Show
Code: Select all
`  . 13 10  .  .  .  .  1  .  . 12  .  . 16 11  5  .  .  .  . 11  5  . 14  . 13  .  9  6  8  7  .  .  .  7 12  .  .  9  .  .  .  . 16  .  .  .  .  . 14  .  .  . 12  .  . 15  .  3  2  .  . 10  .  .  . 12  .  4  .  .  .  .  .  . 14  .  .  . 11  1 16  .  .  .  7  .  .  .  2 15  .  .  6  .  . 13  .  . 15  .  .  1 16 12  9  .  .  8 14  .  .  .  .  5  .  . 10  6  .  . 16  .  .  .  .  4  .  7  . 14  .  .  9 10  4  1  .  .  .  .  .  .  . 10  4  6  . 13  . 15  .  .  .  8  .  .  .  1  .  .  3  .  .  . 16  .  .  .  .  .  . 12  7  .  8  .  5  . 16  .  .  . 12 13  .  .  .  .  .  .  .  .  7 16  .  8  6  .  .  .  .  1  .  .  .  .  .  . 11  .  .  .  .  .  .  . 15 13  . 10 12  8  .  . 10  8  6  9  .  4  .  .  7  .  5  .  .  .  .  .  .  9  .  .  .  3  .  . 10  .  .  .  5  . 14      9 13  .  .  .  3  .  .  .  .  .  .  . 16  .  .  2  .  .  . 11  5  . 14  .  .  .  .  6  8  .  .  8  .  . 12  .  4  . 13 11  .  . 16  .  . 15  .  .  .  .  5  7  .  8  .  .  1  3  .  .  9 10  .  6  9 12  .  .  . 13  2  .  .  .  .  .  .  . 11  .  .  . 11  .  .  .  .  4  . 15  .  .  .  . 10  .  2  . 15  3 11  . 16 12  9  .  6  .  .  .  . 14  8  .  7 12 10  .  .  .  .  .  1  .  .  4  .  .  .  .  8  .  .  .  4  1  . 16  .  3  . 13  . 10  .  .  . 13  . 15  3 14  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  4  . 10  .  7 14  8  .  5  1  .  .  8  . 12 13  .  . 15  .  .  .  9  .  7 16 14  8  6  .  .  2 11  .  3  .  4  . 13  3  .  2  . 16 14  5  7  .  .  .  4  . 12  .  .  . 10  .  .  9  .  .  .  .  .  .  .  .  .  .  1  4  .  9  .  .  .  . 11  .  .  .  .  .  5  .  .      . 13  .  .  .  3  2  .  7  .  .  8  . 16  .  .  .  1  .  3  .  .  .  . 10  .  .  .  .  8  7  .  .  .  . 12  .  .  9  .  . 14  5  .  1  .  .  .  .  . 11  5  .  .  8  6  .  .  3  .  .  .  .  .  .  .  .  .  . 15 13  .  .  8  .  . 16  .  3 11  1  .  .  .  5  7  .  8  .  .  .  .  .  .  . 10 13  2  4 15  . 11  . 16 12  .  .  6  .  .  .  . 14  .  .  . 12  .  6  .  .  .  .  .  .  .  . 15  .  . 14  8  .  9 10  4  1  5  .  .  .  .  .  .  .  .  6  9 13  .  .  .  .  .  8  7  5 11  .  .  .  .  .  .  .  .  .  5  .  .  .  . 12  7 14  8  .  .  . 16  .  .  . 12  .  .  .  .  .  .  6  .  5  7 16  .  .  6  .  .  .  .  .  .  .  4  9 13  . 11  .  1  . 14  .  .  . 15  .  .  . 12  8  .  . 10  8  .  9  .  4 15  .  . 14  .  .  .  .  .  .  .  9 13  2  .  3 11  .  .  . 12  .  .  .  .    . 13  .  .  .  .  2  .  .  6  .  . 14  . 11  5  .  1 15  3  .  5 16  . 10  .  4  9  .  .  .  .  .  .  7  .  .  .  9  .  . 14  5  .  .  2  .  . 16  . 11  .  7 12  .  .  .  .  .  . 13  .  .  .  6  .  .  .  .  .  .  .  5  .  .  .  .  1  .  .  . 16  3  .  .  7  .  .  .  2  . 13  .  . 12 10  .  .  4 15  .  .  1  .  .  .  .  .  8  .  .  7  .  .  .  . 12 10  .  .  . 16  .  .  . 13  . 15  7 12  .  .  .  .  .  4  .  .  . 11  .  .  .  2  .  .  6  .  .  .  .  .  .  .  .  .  . 11  1  . 15  3  .  .  . 16  .  5  6  .  9 10 12  . 14  .  .  .  . 16 14  8  7 12  .  .  .  .  4  .  6  .  5  .  . 14  8  .  . 10  2 11  .  .  .  .  9  .  .  .  .  .  . 14  .  7  .  .  .  .  . 12  .  .  . 10  8  6  9  .  .  . 16  .  .  5 11  .  .  .  4 15  9  .  2  1  .  .  8  .  6 12  .  .  .  .`

Mike, trying your 408 9x9 examples left 100 unsolved using the basic set including triplets. This motivated me to add basic fish methods for arbitrary size n (n=2: X-Wing, n=3: Swordfish, n=4: Jellyfish, n=5: ??? etc.) to my solver and now only 28/408 stay unsolved with this new method set.

The routines for Hidden n-tuples, Naked n-tuples and Basic fishs of size n are almost identical. They only interchange the terms column, row and candidate.
Hidden n-tuple in row: Fix a row and and find a subset of n candidates in this row such that the union of the column positions of these candidates in this row has order <=n.
Naked n-tuple in row: Fix a row and and find a subset of n column positions in this row such that the union of the candidates at these column positions in this row has order <=n.
Basic fish of order n with rows as basesets: Fix a candidate and find a subset of n rows such that the union of the column positions of the candidate in these rows has order <=n.

To find such a set of n objects I do a recursive search of depth n, so the code also is the same for all n. The search is pretty fast since I use tables like (row,column)->bitvector for candidates, (row,candidate)->bitvector for columns and (column, candidate)->bitvector for rows. Oring and anding these bitvectors does most of the job.
hkociemba

Posts: 66
Joined: 09 July 2017

### Re: giant sudoku's (16x16, 25x25, 36x36 .... 100x100)

hkociemba wrote: I additionally give you 4 triplet-minimal examples for 16x16 below (since I now see that the SE rating of Swordfish and X-wing is lower than for hidden triplets I explicitely state that these are not included in the set of used methods here) which all need triplets to be solved and you can check if there is a problem with these with your solver:

Herbert, thanks for these. If I switch off fish in my solver, it still solves all four with no problem (only one has hidden as opposed to naked triplets). When trying to solve problem144.txt, my solver finds many triplet eliminations before having to move to a higher plane, so I'm inclined to think that the problem lies elsewhere.

Thanks anyway,

Mike

P.S. Seems that you're slowly becoming equipped to play in the Patterns Game!

m_b_metcalf
2017 Supporter

Posts: 12441
Joined: 15 May 2006
Location: Berlin

PreviousNext