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

For fans of Killer Sudoku, Samurai Sudoku and other variants

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

Postby hkociemba » Sat Sep 16, 2017 2:05 pm

I found a smaller and easy to solve fully symmetric 25x25 example which shows similar behaviour:

Code: Select all
  .  .  . 24  9  . 19 11  . 12 18  .  7  .  3 13  . 14 10  . 20 22  .  .  .
  .  . 14 13 10  .  2  .  . 24  . 11  . 25  . 15 17  . 20  .  3 18  8  .  .
  . 18  8  .  . 20  .  . 17  .  . 14  .  4  .  . 25  .  . 19  .  . 21 24  .
 25 19  .  .  .  3 18  .  .  7 22  .  .  . 20 24  .  .  9  2  .  .  . 13  4
 17 22  .  .  .  .  .  .  4  .  . 21 24 23  .  . 16  .  .  .  .  .  . 12 25
  .  .  5 16  7 15  6  3 18  .  . 20  4 22  .  .  2  9 12 11  . 21 10  .  .
 18  6  . 17  . 13  .  . 22  4 21 10 23  1 24 16 19  .  .  8  . 11  . 25  2
  2  .  . 25  .  7  .  .  . 16  .  3  . 18  . 23  .  .  . 21  .  .  .  . 22
  .  . 20  . 13 24 21  .  1  .  .  9 25  2  .  . 18  . 15  6  7  .  5  .  .
  1 21  . 23  .  . 11  9  .  .  .  . 16  .  .  .  . 20 13  .  .  6  . 17 18
 10  .  . 21  .  . 12  .  .  .  . 16  8  5  .  .  .  4  1  . 22 15  .  .  3
  .  7 16  . 18 22 15 17  3  . 13  .  .  .  1  .  9 25 19 12  2  . 23 21  .
  3  .  .  . 22  . 13  . 20 14 24  .  .  .  2  8  5  .  .  . 19  .  .  .  9
  . 13  4  .  1  2 24 23 10  . 12  .  .  . 19  .  3 17 22 15 18  . 16  8  .
  9  .  . 11  .  .  7  .  .  .  . 17  6  3  .  .  .  .  2  .  . 13  .  . 20
 14 10  .  1  .  .  9 24  .  .  .  . 19  .  .  .  . 15  4  .  .  3  . 18  8
  .  3  7  . 17  4 20  .  6  .  . 13  1 14  .  . 11  . 16  5 25  . 24  .  .
  6  .  .  .  . 23  .  .  .  1  . 24  . 21  . 18  .  .  .  3  .  .  .  . 11
 21  9  .  2  . 16  .  . 11 19  3  7 18  8 17  1 14  .  . 10  . 20  . 22  6
  .  . 12 19  . 17  3  7  8  .  . 15 22  6  .  . 21 24 25  9  . 10 13  .  .
  7 17  .  .  .  .  .  . 15  .  .  1 10 13  .  . 12  .  . 16  . 25  .  9 24
 13 23  .  .  . 11 25  .  .  9 16  .  .  .  8 20  .  . 14  4  . 17  .  3  7
  . 25  2  .  .  8  .  . 12  .  . 18  .  7  .  . 13  .  . 23  .  . 22 20  .
  .  . 22 20 14  . 23  .  . 10  .  2  . 24  .  3  .  .  6  .  8 16 19  .  .
  .  .  .  5  8  . 17 18  .  3  4  . 20  . 14  9  .  2 11  . 21 23  .  .  .

310 givens, 1588 candidates(pencilmarks).


With using only pointing/claiming + hidden+naked pairs I get 310 givens, 315 candidates. All 315 empty cells have one candidate left.
When applying pointing/claiming + hidden+naked pairs + naked singles I get 360 givens, 1155 candidates!
If you cannot reproduce this result we should switch to this example for further investigations of the differences of our programs.
I try to find a 16x16 example now...
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Sat Sep 16, 2017 2:32 pm

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


I will look at the 25x25 later. In the meantime, I had made the following test with my program:

    read in the puzzle problem144

    read in the solution

    a)for each empty cell add the correct value for that cell to the candidate list as the only candidate (only naked singles)
    OR
    b)for each empty cell add the correct value for that cell to the candidate list as one candidate and a spurious value as a second (only hidden singles)

    try to solve use only pointing/claiming
In both case a ) and b) the program took less than a second before stopping.

HTH

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

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

Postby m_b_metcalf » Sat Sep 16, 2017 2:59 pm

I've made a quick test on the 25x25:
    with hidden and naked pairs and triplets plus pointing/claiming (in my order) I find 1454 candidates left;

    with hidden and naked pairs and triplets plus pointing/claiming and naked singles I find 1367 candidates left;

    with hidden and naked pairs and triplets plus pointing/claiming and hidden singles I find that the puzzle is solved, but with hidden triplets not seen in the previous tests.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

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

Postby hkociemba » Sat Sep 16, 2017 4:02 pm

So we should try to get the same results with this example first. It does not need triplets at all to get solved. It can be completely solved using only hidden singles, pointing/claiming and naked+hidden pairs. I append the output for using only pointing/claiming and naked+hidden pairs which leaves the 315 candidates left (I think in the order you use, I deleted the triplets part):

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;

block_candidates_in_row;
block_candidates_in_col;
row_candidates_in_block;
col_candidates_in_block;
if n_cand_set > progress then
goto restart;

Exactly 1276 candidates are deleted here.

Edit: This takes just a fraction of a second. So though Mike made plausible that my explanation for the >30 min running time with the 144x144 was wrong I will not try to find the reason in the moment. Its more interesting why Mike gets a different result with the 25x25 and without singles.
Attachments
25x25nosingles.txt
(58.84 KiB) Downloaded 9 times
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby hkociemba » Sat Sep 16, 2017 9:33 pm

I now found a 16x16 with the same strange behaviour. Only if the results are different between the two solvers here too we could switch to this even simpler example.

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

95 givens, 774 candidates(pencilmarks).

Pointing/claiming and naked+hidden pairs leaves 95 givens and 161 candidates, one candidate for each empty cell.
Pointing/claiming and naked+hidden pairs + naked singles leaves 137 givens and 386 candidates.
In case of different results a can append the output.
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Sun Sep 17, 2017 7:45 am

hkociemba wrote:I now found a 16x16 with the same strange behaviour. Only if the results are different between the two solvers here too we could switch to this even simpler example.
[snip]
Pointing/claiming and naked+hidden pairs leaves 95 givens and 161 candidates, one candidate for each empty cell.
Pointing/claiming and naked+hidden pairs + naked singles leaves 137 givens and 386 candidates.
In case of different results a can append the output.

They are different: 733 candidates in both cases. Also, for a complete solution I find a naked triplet.
Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Postby Pat » Sun Sep 17, 2017 7:55 am

Pat wrote:
hkociemba wrote:
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.

amazing but right. took me a while to see how this happens

imagine a "naked" duo ={1,2}
AND one of these cells
is a "hidden single" 1 (in another house)

in case 8,
the "hidden single" is recognized,
taking it out of play

==> the "naked" duo VANISHES.

    the other cell is a "naked single" =2
    -- which is un-recognized,
    leaving us no way to exclude the 2
User avatar
Pat
 
Posts: 3424
Joined: 18 July 2005

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

Postby hkociemba » Sun Sep 17, 2017 9:18 am

m_b_metcalf wrote:
hkociemba wrote:They are different: 733 candidates in both cases. Also, for a complete solution I find a naked triplet.

I am sure we are close to find the cause of the differences because this example is small enough. 25x25nosingles.txt is the debug output in the order you compute and here is the output of my solver for the complete solution without any triplets.

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

95 givens, 774 candidates(pencilmarks).


hidden single in block 2: r1c6 = 3
hidden single in block 5: r5c2 = 9
hidden single in block 7: r6c10 = 2
hidden single in block 7: r6c11 = 15
hidden single in block 8: r8c14 = 13
hidden single in block 16: r14c16 = 6
hidden single in block 16: r13c16 = 13
hidden single in row: r4c4 = 5
hidden single in block 1: r1c4 = 4
hidden single in block 3: r2c11 = 4
hidden single in block 3: r2c12 = 9
hidden single in block 3: r1c9 = 7
hidden single in block 11: r10c12 = 7
hidden single in column 6: r15c6 = 13
block 2 candidates for number 6 all in column 8 (pointing): r5r7 c8 <> 6
block 2 candidates for number 10 all in column 5 (pointing): r5r8r12 c5 <> 10
block 2 candidates for number 11 all in column 5 (pointing): r11 c5 <> 11
block 2 candidates for number 15 all in column 5 (pointing): r5r11 c5 <> 15
hidden single in block 6: r5c6 = 15
block 6 candidates for number 2 all in column 8 (pointing): r9r11 c8 <> 2
block 13 candidates for number 15 all in column 2 (pointing): r9r11 c2 <> 15
block 14 candidates for number 9 all in column 5 (pointing): r11r12 c5 <> 9
block 15 candidates for number 14 all in column 11 (pointing): r9r10r11 c11 <> 14
block 16 candidates for number 2 all in column 15 (pointing): r11 c15 <> 2
row 5 candidates for number 6 all in block 5 (claiming): r7c1 r7c2 r8c1 r8c2 r8c3 r8c4 <> 6
row 5 candidates for number 10 all in block 5 (claiming): r7c1 r7c2 r8c1 r8c2 r8c3 r8c4 <> 10
row 11 candidates for number 2 all in block 9 (claiming): r9c2 r9c3 r10c1 r10c3 <> 2
row 16 candidates for number 16 all in block 16 (claiming): r13c13 r13c14 r13c15 r14c13 r14c15 <> 16
hidden tuple of size 2 with numbers 10, 15 in block 2: r1c5 <> 1,11,14 r3c5 <> 1,11
hidden single in block 2: r2c5 = 11
Naked single: r2c16 = 12
hidden single in block 8: r6c15 = 12
hidden single in block 8: r6c13 = 9
hidden single in block 8: r5c16 = 11
Naked single: r5c9 = 5
hidden single in block 5: r8c3 = 5
block 8 candidates for number 8 all in row 7 (pointing): r7 c2c8 <> 8
hidden single in block 5: r8c2 = 8
block 3 candidates for number 12 all in column 11 (pointing): r9r10 c11 <> 12
block 5 candidates for number 7 all in column 4 (pointing): r13 c4 <> 7
block 5 candidates for number 11 all in column 4 (pointing): r13 c4 <> 11
hidden tuple of size 2 with numbers 4, 9 in block 4: r4c14 <> 1,7,16 r4c16 <> 16
hidden tuple of size 2 with numbers 7, 8 in block 4: r2c14 <> 1 r2c15 <> 14
block 4 candidates for number 7 all in row 2 (pointing): r2 c8 <> 7
block 4 candidates for number 14 all in row 1 (pointing): r1 c3c8 <> 14
Naked single: r1c8 = 1
hidden single in block 4: r3c13 = 1
hidden single in block 4: r3c16 = 3
hidden single in block 8: r5c14 = 1
Naked single: r5c13 = 16
block 3 candidates for number 1 all in column 10 (pointing): r12r13r16 c10 <> 1
Naked single: r16c10 = 10
column 16 candidates for number 16 all in block 12 (claiming): r9c14 r12c14 <> 16
hidden tuple of size 2 with numbers 7, 11 in block 5: r6c4 <> 14 r8c4 <> 12,14
hidden tuple of size 2 with numbers 7, 11 in block 13: r13c2 <> 3,12,14,15 r14c2 <> 2,3,10
hidden single in block 13: r16c2 = 15
hidden single in row: r16c11 = 6
hidden single in block 7: r7c12 = 6
hidden single in block 6: r8c7 = 6
row 16 candidates for number 5 all in block 16 (claiming): r14c13 r14c15 r15c14 r15c15 <> 5
hidden tuple of size 2 with numbers 5, 16 in block 16: r16c14 <> 8 r16c15 <> 8
hidden tuple of size 2 with numbers 12, 14 in row 8: r8c1 <> 3 r8c5 <> 7,16
hidden single in block 6: r7c8 = 16
hidden single in block 6: r5c8 = 2
hidden single in block 6: r5c5 = 4
hidden single in block 6: r8c5 = 12
hidden single in row: r8c1 = 14
Naked single: r15c5 = 9
Naked single: r15c15 = 2
hidden single in column 4: r11c4 = 2
hidden single in column 3: r14c3 = 2
block 5 candidates for number 3 all in row 6 (pointing): r6 c12 <> 3
block 1 candidates for number 14 all in column 2 (pointing): r9r11r15 c2 <> 14
block 14 candidates for number 4 all in column 7 (pointing): r9r12 c7 <> 4
block 14 candidates for number 12 all in column 7 (pointing): r9r10r12 c7 <> 12
hidden tuple of size 2 with numbers 4, 12 in block 10: r9c8 <> 14 r12c8 <> 7,8,14
hidden tuple of size 2 with numbers 4, 12 in block 14: r13c7 <> 1,7 r15c7 <> 5
block 14 candidates for number 5 all in row 14 (pointing): r14 c11 <> 5
naked tuple of size 2 at block positions 2, 4 in block 15: r14c9 r15c12 <> 3 r13c11 r14c9 r14c11 <> 11
naked tuple of size 2 at block positions 11, 12 in block 15: r13c11 <> 14
hidden single in block 15: r15c11 = 14
hidden single in block 15: r15c12 = 5
hidden single in block 3: r3c11 = 5
hidden single in block 3: r1c11 = 12
hidden single in row: r1c15 = 11
hidden single in block 4: r1c13 = 14
hidden single in block 12: r11c15 = 14
hidden single in row: r14c2 = 11
hidden single in block 13: r13c2 = 7
hidden single in column 15: r2c15 = 7
hidden single in block 4: r2c14 = 8
block 15 candidates for number 3 all in row 13 (pointing): r13 c3c13c14 <> 3
column 15 candidates for number 9 all in block 16 (claiming): r13c14 <> 9
hidden tuple of size 2 with numbers 3, 10 in block 16: r14c13 <> 8 r15c14 <> 4
hidden single in row: r15c7 = 4
hidden single in block 14: r13c7 = 12
hidden tuple of size 2 with numbers 3, 10 in row 14: r14c1 <> 16
hidden single in row: r14c5 = 16
hidden tuple of size 2 with numbers 5, 7 in block 14: r14c8 <> 8
hidden single in column 8: r6c8 = 8
hidden single in block 6: r6c7 = 14
hidden single in block 10: r12c5 = 14
hidden single in column 4: r13c4 = 14
hidden single in block 13: r13c3 = 16
hidden single in row: r1c14 = 16
hidden single in block 4: r3c15 = 15
hidden single in block 16: r16c15 = 16
hidden single in block 2: r1c5 = 15
hidden single in block 16: r16c14 = 5
hidden single in block 2: r3c5 = 10
hidden single in block 12: r10c13 = 5
hidden single in block 1: r1c3 = 10
hidden single in block 8: r7c15 = 5
hidden single in block 8: r7c13 = 8
hidden single in column 5: r13c5 = 8
hidden single in block 14: r16c6 = 1
hidden single in block 15: r13c11 = 1
hidden single in block 16: r14c15 = 8
hidden single in block 16: r13c15 = 9
hidden single in block 6: r7c7 = 1
hidden single in block 6: r8c6 = 10
hidden single in block 7: r7c11 = 10
hidden single in block 7: r6c12 = 13
hidden single in block 10: r11c5 = 1
hidden single in block 15: r16c9 = 8
hidden single in block 5: r7c1 = 13
hidden single in block 6: r6c6 = 7
hidden single in block 11: r10c11 = 8
hidden single in block 5: r7c2 = 2
hidden single in block 5: r8c4 = 7
hidden single in block 5: r6c4 = 11
hidden single in block 10: r12c6 = 8
hidden single in block 10: r9c6 = 9
hidden single in block 1: r2c1 = 2
hidden single in block 10: r10c6 = 2
hidden single in block 12: r9c16 = 2
hidden single in column 5: r4c5 = 7
Naked single: r10c9 = 14
hidden single in block 9: r9c3 = 14
Naked single: r10c16 = 16
hidden single in block 9: r12c4 = 16
hidden single in block 1: r4c1 = 16
hidden single in block 3: r3c12 = 16
hidden single in block 11: r9c11 = 16
hidden single in block 3: r3c9 = 11
hidden single in block 3: r2c10 = 13
hidden single in block 7: r8c10 = 16
hidden single in block 2: r3c8 = 13
hidden single in block 3: r4c10 = 1
hidden single in block 7: r8c9 = 3
hidden single in block 7: r8c11 = 11
hidden single in block 11: r9c12 = 11
hidden single in block 15: r13c10 = 11
hidden single in block 1: r2c2 = 1
hidden single in block 1: r4c2 = 14
hidden single in block 2: r4c8 = 6
hidden single in block 2: r2c8 = 14
hidden single in block 9: r12c3 = 1
hidden single in block 9: r11c3 = 13
hidden single in block 10: r11c7 = 11
hidden single in block 11: r9c9 = 1
hidden single in block 11: r12c10 = 3
hidden single in block 11: r10c10 = 12
hidden single in block 11: r12c9 = 13
hidden single in block 15: r13c12 = 3
hidden single in block 15: r14c11 = 13
hidden single in block 5: r6c1 = 1
hidden single in block 5: r6c3 = 3
hidden single in block 9: r9c2 = 12
hidden single in block 10: r11c8 = 5
hidden single in block 10: r12c7 = 7
hidden single in block 10: r12c8 = 12
hidden single in block 11: r11c11 = 9
hidden single in block 12: r11c14 = 7
hidden single in block 14: r14c7 = 5
hidden single in block 14: r14c8 = 7
hidden single in block 15: r14c9 = 9
hidden single in block 1: r3c4 = 12
hidden single in block 9: r10c1 = 10
hidden single in block 9: r11c1 = 15
hidden single in block 10: r9c8 = 4
hidden single in block 10: r9c7 = 10
hidden single in block 10: r10c7 = 15
hidden single in block 13: r15c1 = 12
hidden single in block 1: r3c2 = 6
hidden single in block 5: r5c4 = 10
hidden single in block 5: r5c3 = 12
hidden single in block 9: r11c2 = 3
hidden single in block 9: r10c3 = 6
hidden single in block 13: r14c1 = 3
hidden single in block 13: r15c4 = 6
hidden single in block 13: r15c2 = 10
hidden single in block 16: r15c14 = 3
hidden single in block 16: r14c13 = 10
hidden single in block 5: r5c1 = 6
hidden single in block 12: r9c13 = 3
hidden single in block 12: r12c14 = 10
hidden single in block 12: r9c14 = 15
hidden single in block 16: r13c13 = 15
hidden single in block 12: r12c16 = 9
hidden single in block 16: r13c14 = 4
hidden single in block 4: r4c16 = 4
hidden single in block 4: r4c14 = 9
hidden single in block 12: r12c13 = 4

Code: Select all
 +-------------+-------------+-------------+-------------+
 |  9 13 10  4 | 15  3  2  1 |  7  6 12  8 | 14 16 11  5 |
 |  2  1 15  3 | 11  5 16 14 | 10 13  4  9 |  6  8  7 12 |
 |  8  6  7 12 | 10  4  9 13 | 11 14  5 16 |  1  2 15  3 |
 | 16 14 11  5 |  7 12  8  6 | 15  1  3  2 | 13  9 10  4 |
 +-------------+-------------+-------------+-------------+
 |  6  9 12 10 |  4 15 13  2 |  5  8  7 14 | 16  1  3 11 |
 |  1 16  3 11 |  5  7 14  8 |  4  2 15 13 |  9  6 12 10 |
 | 13  2  4 15 |  3 11  1 16 | 12  9 10  6 |  8 14  5  7 |
 | 14  8  5  7 | 12 10  6  9 |  3 16 11  1 |  2 13  4 15 |
 +-------------+-------------+-------------+-------------+
 |  7 12 14  8 |  6  9 10  4 |  1  5 16 11 |  3 15 13  2 |
 | 10  4  6  9 | 13  2 15  3 | 14 12  8  7 |  5 11  1 16 |
 | 15  3 13  2 |  1 16 11  5 |  6  4  9 10 | 12  7 14  8 |
 | 11  5  1 16 | 14  8  7 12 | 13  3  2 15 |  4 10  6  9 |
 +-------------+-------------+-------------+-------------+
 |  5  7 16 14 |  8  6 12 10 |  2 11  1  3 | 15  4  9 13 |
 |  3 11  2  1 | 16 14  5  7 |  9 15 13  4 | 10 12  8  6 |
 | 12 10  8  6 |  9 13  4 15 | 16  7 14  5 | 11  3  2  1 |
 |  4 15  9 13 |  2  1  3 11 |  8 10  6 12 |  7  5 16 14 |
 +-------------+-------------+-------------+-------------+


Puzzle solved!

Or did you mean complete solving without using naked singles?
I hope (a part of) the differences do not result from a misunderstanding. A naked tuple of size n for example consists of n cells which contain n numbers but of course not each cell has to contain all n numbers. So in the case n=2 my program deals something like cell1_candidates= 4, 6 and cell2_candidates= 6 as a naked pair. Since usually naked singles are eliminated, in the case of a naked pair it is imaginable that you define a naked pair only as two cells which exactly have two candidates. This would of course exclude many cases I still deal when naked singles are not allowed.
Attachments
16x16nosingles.txt
(28.32 KiB) Downloaded 6 times
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Sun Sep 17, 2017 9:35 am

hkociemba wrote:Since usually naked singles are eliminated, in the case of a naked pair it is imaginable that you define a naked pair only as two cells which exactly have two candidates. This would of course exclude many cases I still deal when naked singles are not allowed.

Quite. In the normal order of processing in my program, I look for singles before pairs, so the case you cite I don't look for in the naked pair code as it cannot occur.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re:

Postby hkociemba » Sun Sep 17, 2017 9:39 am

Pat wrote:
Pat wrote:
hkociemba wrote:
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.

amazing but right. took me a while to see how this happens

imagine a "naked" duo ={1,2}
AND one of these cells
is a "hidden single" 1 (in another house)

in case 8,
the "hidden single" is recognized,
taking it out of play

==> the "naked" duo VANISHES.

    the other cell is a "naked single" =2
    -- which is un-recognized,
    leaving us no way to exclude the 2

Thanks -but sorry, my fault - I meant not case 8 but case 9 and indeed wonder why we can delete much more candidates without applying *naked singles* than with applying naked singles. Hiddens singles are excluded in both cases...
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby hkociemba » Sun Sep 17, 2017 10:05 am

m_b_metcalf wrote:
hkociemba wrote:Since usually naked singles are eliminated, in the case of a naked pair it is imaginable that you define a naked pair only as two cells which exactly have two candidates. This would of course exclude many cases I still deal when naked singles are not allowed.

Quite. In the normal order of processing in my program, I look for singles before pairs, so the case you cite I don't look for in the naked pair code as it cannot occur.

So you think all differences can be explained with that? Then it really was a big misunderstanding...
hkociemba
 
Posts: 66
Joined: 09 July 2017

Postby Pat » Sun Sep 17, 2017 10:19 am

case 7 vs 8 -- as above
case 7 vs 9 -- just swap the roles of "naked" and "hidden":

imagine a "hidden" duo {3,4}
AND one of these cells
is a "naked single" =4

in case 9,
the "naked single" is recognized,
taking it out of play

==> the "hidden" duo VANISHES.

    the other cell is a "hidden single" 3
    -- which is un-recognized,
    leaving us no way to exclude various possibilities in that cell
User avatar
Pat
 
Posts: 3424
Joined: 18 July 2005

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

Postby m_b_metcalf » Sun Sep 17, 2017 10:26 am

hkociemba wrote:
m_b_metcalf wrote:Quite. In the normal order of processing in my program, I look for singles before pairs, so the case you cite I don't look for in the naked pair code as it cannot occur.

So you think all differences can be explained with that? Then it really was a big misunderstanding...

I don't think that explains everything as even with naked singles switched on I have many more candidates left than you. And there's still the timing problem to clear up. Note that subsuming some naked singles into naked pairs would not allow use of that code as a filter in the Patterns Game.

I'll try to find time to look at your solution sequence later.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

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

Postby hkociemba » Sun Sep 17, 2017 11:09 am

m_b_metcalf wrote:
hkociemba wrote:So you think all differences can be explained with that? Then it really was a big misunderstanding...

I don't think that explains everything as even with naked singles switched on I have many more candidates left than you.

This may be caused by the same argumentation concerning hidden pairs. If number 4 has two possibilites in a house and number 5 has only one, my code considers this as a hidden pair...
Only if you need some triplet to solve this puzzle (while using all other lower rated methods) there is definitely something different. Try to find some time later to patch my code to exclude these potentially hidden or naked singles in the n-tuples.
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Sun Sep 17, 2017 1:03 pm

hkociemba wrote:Only if you need some triplet to solve this puzzle (while using all other lower rated methods) there is definitely something different. Try to find some time later to patch my code to exclude these potentially hidden or naked singles in the n-tuples.

If I alter the order of processing I don't need triples (my usual order reflects the SE ratings' order).

If you patch your code in that way we can certainly make more meaningful comparisons.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to Sudoku variants