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

For fans of Killer Sudoku, Samurai Sudoku and other variants

### re: 144-squared "hidden" triples

Pat wrote:
step 371
hidden tuple of size 3 with numbers 37, 63, 71 in block 17:
r13c57 <> 97,121, r16c49 <> 53, r___c___ <> NONE,
is of that un-usual type --
one of the 3 cells of the trio
has NO exclusions

un-usual -- presents an opportunity for software to fail.

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

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.

we all agree that this situation is a legitimate "hidden" trio,
and as you said this "has to be foreseen in the hidden triple algorithm"

but in the world of 9-squared,
this un-usual situation is rather rare --
so you tested hundreds of puzzles
but did you find even one of these "NONE"?

i see no explicit statement on this point

{/nag}

Pat

Posts: 3964
Joined: 18 July 2005

### Re: re: 144-squared "hidden" triples

Pat wrote:so you tested hundreds of puzzles
but did you find even one of these "NONE"? {/nag}

Is this what you mean?
Hidden Text: Show
Code: Select all
` . 1 . 2 3 4 . . . . . 3 5 6 7 . 1 . 6 . . 8 9 1 7 . . . 8 . . 7 . . . . . . 9 4 5 3 2 . . . 3 . . 8 . . 7 . . . 8 . 2 5 . . 9 3 5 . 6 1 9 4 . . . . . . 4 8 . 5 .   ED=4.0/4.0/2.8  8 values + 1 alien, 2 'nones' . 1 . . 2 . . 3 4 5 . 6 . 1 . 7 2 8 . 4 2 . . . . 6 . . . . 3 . . . . . 4 . . . 8 . . . 2 . . . . . 1 . . . . 5 . . . . . 9 . 2 . 9 1 6 . 4 . 7 . 6 4 . 7 . . 1 .   ED=4.0/4.0/2.8   7 + 1, 2 'nones' . 1 . . . 2 . . 3 4 . . 5 . . . 6 . . . 5 . . . . . . . 2 . . . 7 . . 1 . . . . . . . . . 6 . . 4 . . . 8 . . . . . . . 3 . . . 3 . . . 1 . . 2 8 . . 6 . . . 4 .   ED=4.0/4.0/3.4  6+2 (2 'nones'), 6+4 (1 'none'),                                      6+3 (1 'none'), 6+2 (1 'none') . 1 . 2 3 4 . . . . . 3 5 6 7 . 1 . 6 . . 8 9 1 7 . . . 8 . . 7 . . . . . . 9 4 5 3 2 . . . 3 . . 8 . . 7 . . . 8 . 2 5 . . 9 3 5 . 6 1 9 4 . . . . . . 4 8 . 5 .   ED=4.0/4.0/2.8   7 + 1, 2 'nones' . 1 . . 2 . . 3 4 5 . 6 . 1 . 7 2 8 . 4 2 . . . . 6 . . . . 3 . . . . . 4 . . . 8 . . . 2 . . . . . 1 . . . . 5 . . . . . 9 . 2 . 9 1 6 . 4 . 7 . 6 4 . 7 . . 1 .  ED=4.0/4.0/2.8   7 + 1, 2 'nones' . . . 1 . . . . . . . 2 . . 3 . . 4 . 5 . . 2 . . 1 . 6 . . 7 . . 8 . . . . 3 . . 4 . . 7 . 9 . . 5 . . 6 . . . . 2 . . . . . . . 4 . . 7 . . 3 . 6 . . 9 . . 8 .  ED=4.0/4.0/3.4   6 + 4, 1 'none'`

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

### re: 144-squared "hidden" triples

m_b_metcalf wrote:Is this what you mean?

Code: Select all
` . 1 . 2 3 4 . . . . . 3 5 6 7 . 1 . 6 . . 8 9 1 7 . . . 8 . . 7 . . . . . . 9 4 5 3 2 . . . 3 . . 8 . . 7 . . . 8 . 2 5 . . 9 3 5 . 6 1 9 4 . . . . . . 4 8 . 5 .`

ED=4.0/4.0/2.8
8 values + 1 alien, 2 'nones'

yes !!
thanks.

now i'm left to wonder
if such strange cases happen with "hidden" duos too---

Pat

Posts: 3964
Joined: 18 July 2005

### re: 144-squared

Pat wrote:
now i'm left to wonder
if such strange cases happen with "hidden" duos too---

step 309
hidden tuple of size 2 with numbers 105, 109 in block 2:
r12c22 <> 101, r__c__ <> NONE,

Pat

Posts: 3964
Joined: 18 July 2005

### Re: re: 144-squared triples

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

I did some other test which was quite interesting. I took your second attachment problem144.txt with its 14657 givens and fed it again into my solver, disallowed singles and used only pointing, claiming, hidden/naked pairs and triplets.
Of course the puzzle cannot be solved without using singles but after 14314 steps there where only 6079 from the 144^3 candidates left - this is exactly one candidate for the 144^2 - 14657 = 6079 unsolved cells. So in principle the puzzle was solved. I append the verbose output (really weird) and @Pat: Again there are lots of hidden triplets which eliminate just one candidate...

P.S: It is not obvious that omitting singles always leads to exactly one left candidate for the unfilled cells. This does not seem to work for every puzzle.
Attachments
continuation_nosingles.zip
hkociemba

Posts: 66
Joined: 09 July 2017

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

@Mike: Maybe it is possible to track down the problem if we compare the number candidates left when applying some basic methods to problem144.txt.

problem144.txt: 14657 givens, 54442 candidates
applying only:
1. pointing/claiming: 14657 givens, 53265 candidates
2. hidden pairs: 14657 givens, 54400 candidates
3. hidden pairs/triplets: 14657 givens, 54348 candidates
4. naked pairs: 14657 givens, 54298 candidates
5. naked pairs/triplets: 14657 givens, 54201 candidates
6. naked+hidden pairs + pointing/claiming: 14657 givens, 53055 candidates
7. naked+hidden pairs/triples + pointing/claiming (after a 30 min computation!): 14657 givens, 6079 (!) candidates
8. naked+hidden pairs/triplets + pointing/claiming+ hidden singles: 15070 givens, 47079 candidates
9. naked+hidden pairs/triplets + pointing/claiming+ naked singles: 14708 givens, 52335 candidates
10. naked+hidden pairs/triplets + pointing/claiming+ naked/hidden singles: solved

What is a bit strange and interesting but I think not impossible or a reference to a program error is case 7 where you can delete much more candidates than in case 8 though in case 8 you additional apply naked singles. The candidates left in case 7 are exactly one for each unfilled cell with exactly the right value, so this seems ok. Nevertheless it would be great if we could get the same numbers with two totally independent written programs which would considerably increase the confidence in the code. Computation time except for case 7 is at most a few seconds/case.
hkociemba

Posts: 66
Joined: 09 July 2017

hkociemba wrote:problem144.txt: 14657 givens, 54442 candidates
applying only:

7.
naked+hidden pairs/triples
+ pointing/claiming
(after a 30 min computation!):

14657 givens, 6079 (!) candidates

8.
naked+hidden pairs/triplets
+ pointing/claiming
+ hidden singles:

15070 givens, 47079 candidates
What is a bit strange and interesting
but I think not impossible or a reference to a program error
is case 7 where you can delete much more candidates than in case 8
though in case 8 you additional apply naked {correct to: hidden} singles.

{edit:} amazing but right. took me a while to see how this happens
Last edited by Pat on Thu Sep 14, 2017 8:35 am, edited 1 time in total.

Pat

Posts: 3964
Joined: 18 July 2005

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

hkociemba wrote:@Mike: Maybe it is possible to track down the problem if we compare the number candidates left when applying some basic methods to problem144.txt.

Herbert, a brilliant idea and so easy and fast to perform. Here is your list with my results added in red:

problem144.txt: 14657 givens, 54442 candidates

applying only:
1. pointing/claiming: 14657 givens, 53265 candidates [same]

2. hidden pairs: 14657 givens, 54400 candidates [same]

3. hidden pairs/triplets: 14657 givens, 54348 candidates [54354]

4. naked pairs: 14657 givens, 54298 candidates [same]

5. naked pairs/triplets: 14657 givens, 54201 candidates [same]

6. naked+hidden pairs + pointing/claiming: 14657 givens, 53055 candidates [same]

7. naked+hidden pairs/triples + pointing/claiming (after a 30 min computation!): 14657 givens, 6079 (!) candidates [52965 in 11s.]

8. naked+hidden pairs/triplets + pointing/claiming+ hidden singles: 15070 givens, 47079 candidates [52965]

9. naked+hidden pairs/triplets + pointing/claiming+ naked singles: 14708 givens, 52335 candidates [52965]

10. naked+hidden pairs/triplets + pointing/claiming+ naked/hidden singles: solved [52965]
So, there are some interesting differences. Your result no. 7 really does appear odd! We still have a bit more work to do.

HTH

Mike Metcalf

P.S. In 8 and 9 the number of givens is no longer 14657(?).

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

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

Nr. 3 seems to be a good candidate to see the what is the difference since there are not many steps involved. I add the verbose output together with the 94 candidates. There should be 6 candidates which were not deleted by your program...

Hidden Text: Show
r12 c22 n101
hidden tuple of size 2 with numbers 105, 109 in block 2: r12c22 <> 101
r10 c41 n10
hidden tuple of size 2 with numbers 56, 67 in block 4: r10c41 <> 10
r5 c37 n55
r5 c37 n80
r5 c39 n55
r5 c39 n62
hidden tuple of size 2 with numbers 10, 124 in block 4: r5c37 <> 55,80 r5c39 <> 55,62
r6 c41 n73
hidden tuple of size 2 with numbers 55, 80 in block 4: r6c41 <> 73
r24 c24 n122
hidden tuple of size 2 with numbers 17, 142 in block 14: r24c24 <> 122
r47 c87 n47
r47 c87 n78
hidden tuple of size 2 with numbers 95, 136 in block 44: r47c87 <> 47,78
r63 c75 n83
r71 c75 n83
hidden tuple of size 2 with numbers 18, 26 in block 67: r63c75 <> 83 r71c75 <> 83
r74 c103 n24
r74 c103 n42
r79 c103 n10
hidden tuple of size 2 with numbers 58, 113 in block 81: r74c103 <> 24,42 r79c103 <> 10
r84 c109 n124
r84 c118 n85
r84 c118 n103
r84 c118 n124
hidden tuple of size 2 with numbers 107, 143 in block 82: r84c109 <> 124 r84c118 <> 85,103,124
r10 c138 n58
hidden tuple of size 2 with numbers 10, 19 in row 10: r10c138 <> 58
r80 c87 n57
r80 c127 n33
hidden tuple of size 2 with numbers 53, 134 in row 80: r80c87 <> 57 r80c127 <> 33
r53 c14 n116
r53 c14 n130
r57 c14 n13
hidden tuple of size 2 with numbers 30, 131 in column 14: r53c14 <> 116,130 r57c14 <> 13
r133 c50 n3
r133 c50 n72
r133 c50 n79
r133 c50 n107
r142 c50 n3
r142 c50 n8
r142 c50 n52
r142 c50 n60
r142 c50 n87
r142 c50 n102
r142 c50 n107
hidden tuple of size 2 with numbers 62, 90 in column 50: r133c50 <> 3,72,79,107 r142c50 <> 3,8,52,60,87,102,107
r28 c111 n27
r28 c111 n40
r28 c111 n44
r32 c111 n27
r32 c111 n46
r32 c111 n84
hidden tuple of size 2 with numbers 108, 129 in column 111: r28c111 <> 27,40,44 r32c111 <> 27,46,84
r16 c48 n3
r16 c48 n21
r16 c48 n37
r16 c48 n48
r16 c48 n59
r16 c48 n70
r16 c48 n140
r17 c39 n9
r17 c39 n18
r17 c39 n46
r17 c39 n70
r17 c40 n3
r17 c40 n14
r17 c40 n42
r17 c40 n46
r17 c40 n84
r17 c40 n89
r17 c40 n123
hidden tuple of size 3 with numbers 31, 136, 141 in block 16: r16c48 <> 3,21,37,48,59,70,140 r17c39 <> 9,18,46,70 r17c40 <> 3,14,42,46,84,89,123
r25 c84 n81
hidden tuple of size 3 with numbers 2, 61, 133 in block 31: r25c84 <> 81
r45 c109 n8
r45 c115 n104
r45 c116 n55
hidden tuple of size 3 with numbers 2, 4, 94 in block 46: r45c109 <> 8 r45c115 <> 104 r45c116 <> 55
r57 c79 n38
r58 c79 n38
hidden tuple of size 3 with numbers 21, 85, 101 in block 55: r57c79 <> 38 r58c79 <> 38
r72 c20 n14
hidden tuple of size 3 with numbers 68, 74, 83 in block 62: r72c20 <> 14
r71 c22 n13
hidden tuple of size 2 with numbers 1, 14 in block 62: r71c22 <> 13
r76 c22 n14
r76 c22 n114
hidden tuple of size 3 with numbers 35, 55, 118 in block 74: r76c22 <> 14,114
r122 c13 n12
r123 c13 n12
hidden tuple of size 3 with numbers 3, 70, 75 in block 122: r122c13 <> 12 r123c13 <> 12
r127 c16 n104
r127 c16 n122
r127 c23 n50
r127 c23 n68
r127 c23 n104
r132 c16 n114
hidden tuple of size 3 with numbers 29, 98, 126 in block 122: r127c16 <> 104,122 r127c23 <> 50,68,104 r132c16 <> 114
r126 c15 n13
r128 c15 n13
r128 c15 n30
r128 c15 n116
hidden tuple of size 3 with numbers 40, 50, 104 in block 122: r126c15 <> 13 r128c15 <> 13,30,116
r73 c136 n56
r73 c136 n68
r73 c141 n68
r73 c141 n94
r73 c141 n105
r73 c143 n56
r73 c143 n61
hidden tuple of size 3 with numbers 3, 31, 116 in row 73: r73c136 <> 56,68 r73c141 <> 68,94,105 r73c143 <> 56,61
r135 c22 n12
r135 c22 n13
r135 c22 n14
r135 c22 n19
r144 c22 n19
hidden tuple of size 3 with numbers 35, 101, 118 in column 22: r135c22 <> 12,13,14,19 r144c22 <> 19

P.S. Yes in 8. and 9. there are some hidden and naked singles, so the number of givens changes.
hkociemba

Posts: 66
Joined: 09 July 2017

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

hkociemba wrote:Nr. 3 seems to be a good candidate to see the what is the difference since there are not many steps involved. I add the verbose output together with the 94 candidates. There should be 6 candidates which were not deleted by your program...
[snip]

P.S. Yes in 8. and 9. there are some hidden and naked singles, so the number of givens changes.

Yes, thanks, that was very useful. I discovered that a premature exit from the code can be taken on rare occasions in a misguided effort to improve efficiency. When this is corrected, the table becomes (changes only)
3. same

7. 52890

8. 52462

9. 52619

10. 0, solved!
So, the problem seems to be solved, but there are discrepancies in cases 7, 8 and 9 which I cannot explain. Especially 7!

Regards,

Mike Metcalf

P.S. I haven't understood your point about singles. Are you saying that some cells in problem144 can be solved only with singles?

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

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

m_b_metcalf wrote:P.S. I haven't understood your point about singles. Are you saying that some cells in problem144 can be solved only with singles?

I mean that for example in Nr. 9 we use naked+hidden pairs/triplets + pointing/claiming + naked singles . At some point(s) we can apply this method and hence increase the number of givens. That's why I get 14708 instead of 14657 givens here. The first time a naked single appears is in step 385 with my solver. If for your solver naked singles never appear here I suppose something is wrong.

I realized another problem. It is not very intuitive but the order of the computation indeed has an influence on the result. If we for example take the result of Nr.7 everything what is left are naked singles - there is only one candidate left for each cell. So if we apply naked singles in the end the puzzle is solved. This differs from the result of Nr. 9 where the same methods are used but where naked singles is the method of first choice. I also observed that with Nr. 8 I got 15070 or 15069 givens depending on the order I use for the basic methods. So it will be difficult to compare the results unless we use exactly the same logic in which order the basic methods are applied.
hkociemba

Posts: 66
Joined: 09 July 2017

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

hkociemba wrote:I realized another problem. It is not very intuitive but the order of the computation indeed has an influence on the result. If we for example take the result of Nr.7 everything what is left are naked singles - there is only one candidate left for each cell. So if we apply naked singles in the end the puzzle is solved.

I agree that it is plausible that the order of processing can make a difference, but 7. is dramatic.

My order of processing for this test was:
Code: Select all
`do until no more progress   find naked pairs in rows/columns/boxes   find hidden pairs in rows/columns/boxes       if any found cycle   find naked triplets in rows       if any found cycle   find naked triplets in columns       if any found cycle   find naked triplets in boxes       if any found cycle      find hidden triplets in rows       if any found cycle   find hidden triplets in columns       if any found cycle   find hidden triplets in boxes       if any found cycle   pointing/claimingend do `

and that gives the figure of 52980 after no further progress. I have then altered the sequence to what I think you do, namely
Code: Select all
`do until no more progress   find naked pairs in boxes/rows/columns   find hidden pairs in boxes/rows/columns   find naked triplets in boxes/rows/columns   find hidden triplets in boxes/rows/columns   pointing/claimingend do `

and find 52878 candidates left, a small change but not as dramatic as what you report. Maybe you could look into what your program spends 30 minutes doing?

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

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

The output in the attachment was produced by this code which is I hope exactly what your program does. I dod not know if the order of the 4 kinds of pointing/claiming is important.:
Hidden Text: Show
naked_tuple_row(2);
naked_tuple_col(2);
naked_tuple_block(2);
hidden_tuple_row(2);
hidden_tuple_col(2);
hidden_tuple_block(2);
if n_cand_set > progress then
goto restart;
naked_tuple_row(3);
if n_cand_set > progress then
goto restart;
naked_tuple_col(3);
if n_cand_set > progress then
goto restart;
naked_tuple_block(3);
if n_cand_set > progress then
goto restart;

hidden_tuple_row(3);
if n_cand_set > progress then
goto restart;
hidden_tuple_col(3);
if n_cand_set > progress then
goto restart;
hidden_tuple_block(3);
if n_cand_set > progress then
goto restart;

block_candidates_in_row;
block_candidates_in_col;
row_candidates_in_block;
col_candidates_in_block;

if n_cand_set > progress then
goto restart;

The complete process takes more than 14000 lines and in this order even takes an hour to complete. I only add the output until there are less than 52000 candidates left. Hope that helps
Attachments
output52000.txt
hkociemba

Posts: 66
Joined: 09 July 2017

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

hkociemba wrote:The output in the attachment was produced by this code which is I hope exactly what your program does. I dod not know if the order of the 4 kinds of pointing/claiming is important.:
Hidden Text: Show
naked_tuple_row(2);
naked_tuple_col(2);
naked_tuple_block(2);
hidden_tuple_row(2);
hidden_tuple_col(2);
hidden_tuple_block(2);
if n_cand_set > progress then
goto restart;
naked_tuple_row(3);
if n_cand_set > progress then
goto restart;
naked_tuple_col(3);
if n_cand_set > progress then
goto restart;
naked_tuple_block(3);
if n_cand_set > progress then
goto restart;

hidden_tuple_row(3);
if n_cand_set > progress then
goto restart;
hidden_tuple_col(3);
if n_cand_set > progress then
goto restart;
hidden_tuple_block(3);
if n_cand_set > progress then
goto restart;

block_candidates_in_row;
block_candidates_in_col;
row_candidates_in_block;
col_candidates_in_block;

if n_cand_set > progress then
goto restart;

The complete process takes more than 14000 lines and in this order even takes an hour to complete. I only add the output until there are less than 52000 candidates left. Hope that helps

Thanks for that. I'll have a look at it later. In the meantime, however, I have two questions:

1) If case 7 ends with 6079 naked singles, why doesn't the puzzle get fully solved in case 9? (pat seems to understand why this can happen, but I don't.)

2) Your program appears to be otherwise very fast, solving massive puzzles that yield to basic techniques in just a few seconds. So how is it possible that it spends 30 minutes running in case 6? Can you instrument the code somehow to see where the bulk of the time is spent?

Thanks,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 13173
Joined: 15 May 2006
Location: Berlin

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

m_b_metcalf wrote:1) If case 7 ends with 6079 naked singles, why doesn't the puzzle get fully solved in case 9? (pat seems to understand why this can happen, but I don't.)

2) Your program appears to be otherwise very fast, solving massive puzzles that yield to basic techniques in just a few seconds. So how is it possible that it spends 30 minutes running in case 6? Can you instrument the code somehow to see where the bulk of the time is spent?

Q2: I suppose you mean case 7. I don't know the reason yet (but I also did not try to track this down yet). I just observe that while solving at the beginning as usual the verbose output scrolls down the screen very fast but after some time occasionally for seconds or even longer hangs. It seems that the program has tot test lots of cases without getting a positive result back. I will try to find out why this happens in case 7, where naked singles are not "cleared".

Q1: I am also puzzled by this fact and if Pat can explain it, it would be great. I tried to reproduce this with some 9x9 puzzles but in this case the puzzles in case 9 always got solved.

So I cannot answer any of your questions satisfactorily in the moment...

Edit: Concerning Q2 I see a bit clearer. The long times result from times for more than a minute if hidden/naked triples are checked and also with pointing/claiming. I think the long times result because there are lots of hidden singles around and a hidden single n in a block for example is a candidate for pointing (because n occurs only once in the block and hence all occurences (=1 occurrence) are within one row and also within one column. So much has to be checked. A similar argumentations works for the triplets.
hkociemba

Posts: 66
Joined: 09 July 2017

PreviousNext