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 m_b_metcalf » Fri Aug 25, 2017 4:49 pm

hkociemba wrote: I wonder what causes these differences between our opinions.

Just crossed-wires: by redundant I mean wrt to any solution method. Sorry for any confusion.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8238
Joined: 15 May 2006
Location: Berlin

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

Postby hkociemba » Sat Aug 26, 2017 5:59 pm

m_b_metcalf wrote: I could solve all the puzzles, but my impression is that they are harder (require more elaborate techniques) than you state in your comments.
Maybe we also should try to track down this issue. The first one (16x16, 93 givens) )is really solvable with pairs only, I append the verbose output, it is not too large and maybe you can see where you fail in the solving process.
Hidden Text: Show
hidden single in block: r1c8 = 1
hidden single in block: r8c2 = 8
hidden single in block: r5c10 = 8
hidden single in block: r12c12 = 15
Naked single: r3c12 = 16
Naked single: r3c5 = 10
Naked single: r3c7 = 9
Naked single: r4c8 = 6
Naked single: r5c8 = 2
Naked single: r11c8 = 5
block candidates in row: r3 c4 <> 5
block candidates in row: r6 c10c12 <> 3
block candidates in row: r7 c14c15c16 <> 4
block candidates in row: r6 c13 <> 5
block candidates in row: r8 c13c15c16 <> 9
block candidates in row: r8 c9 <> 12
block candidates in row: r10 c13c14c15 <> 4
block candidates in row: r9 c5c6c7c15 <> 11
block candidates in row: r13 c7c14c15 <> 5
block candidates in column: r9r11r13 c4 <> 12
block candidates in column: r7 c11 <> 12
block candidates in column: r14 c13 <> 6
block candidates in column: r13 c4 <> 9
block candidates in column: r11 c3 <> 8
row candidates in block: r9c13 r9c15 r10c13 r10c14 r10c15 <> 9
row candidates in block: r9c13 r9c15 r10c13 r10c14 r10c15 <> 10
row candidates in block: r14c13 r14c14 r14c16 r16c13 r16c14 r16c15 r16c16 <> 9
hidden single in block: r7c9 = 12
hidden tuple of size 2 in row: r16c9 <> 1 r16c3 <> 2 r16c9 <> 3 r16c3 <> 7 r16c3 <> 10 r16c9 <> 10 r16c9 <> 14 r16c3 <> 15 r16c9 <> 16
naked tuple of size 2 in row: r12c9 <> 14 r12c10 <> 2 r12c10 <> 14 r12c13 <> 14 r12c14 <> 14 r12c16 <> 14
naked tuple of size 2 in row: r12c13 <> 3 r12c13 <> 13 r12c14 <> 3 r12c16 <> 3 r12c16 <> 13
hidden single in block: r16c2 = 15
block candidates in row: r14 c5 <> 2
block candidates in column: r2r7 c11 <> 2
row candidates in block: r9c9 r9c10 r9c12 r10c9 <> 3
row candidates in block: r9c9 r9c10 r9c12 r11c9 <> 13
column candidates in block: r13c10 r15c9 r15c10 r16c10 <> 3
hidden single in block: r13c12 = 3
hidden single in column: r10c8 = 3
hidden single in column: r8c8 = 9
hidden single in column: r13c8 = 10
hidden single in block: r9c13 = 3
hidden single in block: r16c7 = 3
Naked single: r7c11 = 10
Naked single: r2c11 = 4
hidden single in block: r14c12 = 4
hidden single in block: r13c10 = 11
hidden single in row: r9c12 = 11
hidden single in row: r14c2 = 11
hidden single in column: r7c12 = 6
hidden single in block: r14c3 = 2
hidden single in block: r16c3 = 9
hidden single in block: r14c9 = 9
hidden single in row: r16c9 = 8
hidden single in column: r15c3 = 8
block candidates in row: r6 c1c3c7 <> 13
block candidates in row: r11 c1 <> 12
block candidates in row: r15 c9c10c14c16 <> 10
block candidates in row: r16 c13c14c15c16 <> 10
block candidates in column: r1r2 c10 <> 10
row candidates in block: r6c1 r6c2 r6c4 r8c1 <> 2
column candidates in block: r2c1 r4c1 r4c2 <> 10
hidden single in block: r2c9 = 10
hidden single in block: r16c10 = 10
hidden single in column: r1c3 = 10
hidden single in column: r12c9 = 13
hidden single in column: r15c10 = 7
hidden single in block: r12c10 = 3
hidden single in row: r8c9 = 3
hidden single in column: r7c3 = 4
hidden single in column: r11c3 = 13
hidden single in column: r2c3 = 15
hidden single in block: r1c5 = 15
hidden single in block: r9c15 = 13
hidden single in column: r3c3 = 7
hidden single in column: r6c3 = 3
block candidates in row: r2 c14c15 <> 11
block candidates in row: r10 c9c11 <> 1
block candidates in row: r10 c11 <> 5
block candidates in row: r11 c1 <> 7
block candidates in row: r13 c14c15c16 <> 7
block candidates in row: r15 c6c14 <> 16
block candidates in column: r9 c10 <> 6
block candidates in column: r9 c10 <> 16
block candidates in column: r4 c16 <> 13
row candidates in block: r2c13 r2c14 r2c15 r4c13 r4c14 r4c15 <> 16
row candidates in block: r13c14 r13c15 r13c16 r15c14 r15c16 <> 14
column candidates in block: r1c11 r3c11 <> 14
Naked single: r1c11 = 12
Naked single: r2c15 = 7
Naked single: r3c11 = 5
Naked single: r9c10 = 5
Naked single: r10c9 = 14
Naked single: r12c11 = 2
hidden single in block: r3c4 = 12
hidden single in row: r3c16 = 3
hidden single in row: r12c5 = 14
hidden single in row: r15c14 = 3
hidden single in column: r2c4 = 3
hidden single in column: r16c5 = 2
hidden single in block: r3c13 = 1
hidden single in row: r3c10 = 14
Naked single: r1c10 = 6
Naked single: r2c14 = 8
Naked single: r10c11 = 8
Naked single: r10c13 = 5
hidden single in block: r4c7 = 8
hidden single in block: r2c13 = 6
hidden single in block: r4c13 = 13
hidden single in block: r11c16 = 8
hidden single in row: r2c10 = 13
hidden single in row: r6c12 = 13
hidden single in row: r9c4 = 8
hidden single in row: r9c6 = 9
hidden single in row: r10c4 = 9
hidden single in column: r4c12 = 2
hidden single in block: r2c1 = 2
hidden single in block: r10c2 = 4
hidden single in row: r10c6 = 2
hidden single in row: r11c4 = 2
hidden single in column: r7c2 = 2
hidden single in column: r7c4 = 15
hidden single in column: r8c6 = 10
hidden single in column: r4c15 = 10
hidden single in block: r6c4 = 11
hidden single in column: r13c15 = 9
Naked single: r6c5 = 5
Naked single: r6c7 = 14
Naked single: r11c1 = 15
hidden single in block: r10c7 = 15
hidden single in block: r14c7 = 5
hidden single in row: r8c16 = 15
hidden single in row: r10c1 = 10
hidden single in row: r15c2 = 10
hidden single in row: r15c1 = 12
hidden single in row: r15c11 = 14
hidden single in row: r15c9 = 16
hidden single in column: r9c2 = 12
hidden single in column: r5c6 = 15
hidden single in column: r9c7 = 10
hidden single in column: r9c9 = 1
hidden single in column: r11c9 = 6
hidden single in column: r13c11 = 1
hidden single in column: r9c11 = 16
hidden single in block: r9c1 = 7
hidden single in block: r9c5 = 6
hidden single in block: r13c2 = 7
hidden single in row: r14c16 = 6
hidden single in column: r4c2 = 14
hidden single in column: r6c2 = 16
hidden single in column: r13c4 = 14
hidden single in column: r13c6 = 6
hidden single in column: r8c10 = 16
hidden single in block: r4c1 = 16
hidden single in block: r6c10 = 2
hidden single in block: r8c13 = 2
hidden single in block: r13c1 = 5
hidden single in row: r4c4 = 5
hidden single in column: r1c4 = 4
hidden single in column: r8c15 = 4
hidden single in block: r5c5 = 4
hidden single in row: r8c1 = 14
hidden single in column: r5c1 = 6
hidden single in column: r7c1 = 13
hidden single in column: r2c5 = 11
hidden single in column: r14c5 = 16
hidden single in column: r15c6 = 13
hidden single in column: r11c6 = 16
hidden single in column: r8c7 = 6
hidden single in column: r13c7 = 12
hidden single in column: r5c7 = 13
hidden single in column: r2c7 = 16
hidden single in column: r12c13 = 4
hidden single in column: r6c13 = 9
hidden single in column: r14c13 = 10
hidden single in column: r11c13 = 12
hidden single in column: r12c14 = 10
hidden single in column: r14c14 = 12
hidden single in column: r6c16 = 10
hidden single in column: r13c16 = 13
hidden single in block: r6c1 = 1
hidden single in block: r7c6 = 11
hidden single in block: r8c5 = 12
hidden single in block: r11c7 = 11
hidden single in block: r11c14 = 7
hidden single in block: r12c16 = 9
hidden single in block: r11c15 = 14
hidden single in block: r16c6 = 1
hidden single in block: r15c16 = 1
hidden single in block: r13c14 = 4
hidden single in row: r4c16 = 4
hidden single in row: r4c14 = 9
hidden single in row: r5c14 = 1
hidden single in row: r5c16 = 11
hidden single in row: r5c13 = 16
hidden single in row: r7c16 = 7
hidden single in row: r7c14 = 14
hidden single in row: r10c15 = 1
hidden single in row: r10c14 = 11
hidden single in row: r16c13 = 7
hidden single in row: r16c16 = 14
hidden single in column: r1c13 = 14
hidden single in column: r16c14 = 5
hidden single in column: r1c14 = 16
hidden single in column: r7c15 = 5
hidden single in column: r1c15 = 11
hidden single in column: r16c15 = 16
hkociemba
 
Posts: 63
Joined: 09 July 2017

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

Postby hkociemba » Sat Aug 26, 2017 7:31 pm

After quite a long search I now also found an interesting 9x9 example.

.5......2..15..968..........1...5...8..12......568.....4...91...72..345......6..7
Hidden Text: Show
hidden single in row: r8c4 = 8
Naked single: r8c5 = 1
hidden single in block: r9c1 = 1
hidden single in block: r7c1 = 5
hidden single in block: r9c5 = 5
hidden single in row: r9c4 = 4
hidden single in block: r7c4 = 2
hidden single in block: r7c5 = 7
block candidates in row: r4 c1c3c7c8c9 <> 3
block candidates in row: r4 c1c3c8c9 <> 9
block candidates in column: r4r5 c9 <> 6
Naked single: r4c9 = 4
block candidates in column: r1r2r3 c6 <> 4
hidden tuple of size 2 in block: r3c6 <> 2 r1c6 <> 7 r3c6 <> 7
hidden tuple of size 2 in block: r4c4 <> 7
naked tuple of size 2 in column: r2c6 <> 7
hidden single in block: r2c6 = 2
hidden single in row: r2c1 = 7
hidden single in row: r2c5 = 4
hidden single in row: r2c2 = 3
hidden single in column: r6c1 = 3
hidden single in block: r5c3 = 4
hidden single in block: r4c3 = 7
hidden single in block: r6c6 = 4
hidden single in block: r5c6 = 7
block candidates in column: r3r9 c2 <> 9
Naked single: r9c2 = 8
hidden single in block: r7c8 = 8
hidden single in row: r4c7 = 8
hidden single in column: r5c7 = 6
hidden single in block: r4c1 = 6
hidden single in block: r5c9 = 5
hidden single in block: r7c3 = 6
hidden single in block: r8c9 = 6
hidden single in block: r9c8 = 9
hidden single in row: r1c5 = 6
hidden single in row: r3c7 = 5
hidden single in row: r3c2 = 6
hidden single in row: r4c8 = 2
hidden single in row: r5c8 = 3
hidden single in row: r5c2 = 9
hidden single in row: r6c2 = 2
hidden single in row: r6c9 = 9
hidden single in row: r7c9 = 3
hidden single in row: r8c1 = 9
hidden single in row: r9c7 = 2
hidden single in row: r9c3 = 3
hidden single in column: r3c1 = 2
hidden single in column: r1c1 = 4
hidden single in column: r1c7 = 3
hidden single in column: r6c7 = 7
hidden single in column: r3c8 = 4
hidden single in column: r1c8 = 7
hidden single in column: r3c9 = 1
hidden single in block: r1c6 = 1
hidden single in block: r3c4 = 7
hidden single in block: r3c6 = 8
hidden single in block: r6c8 = 1
hidden single in row: r1c3 = 8
hidden single in row: r1c4 = 9
hidden single in row: r3c5 = 3
hidden single in row: r3c3 = 9
hidden single in row: r4c4 = 3
hidden single in row: r4c5 = 9

is pair-optimal and removing the 5 in r6c3 it gets triple-optimal and also overall optimal:

.5......2..15..968..........1...5...8..12.......68.....4...91...72..345......6..7
Hidden Text: Show
hidden single in row: r8c4 = 8
Naked single: r8c5 = 1
hidden single in block: r9c1 = 1
block candidates in row: r4 c1c3c7c8c9 <> 3
block candidates in row: r4 c1c3c8c9 <> 9
block candidates in column: r3 c4 <> 2
block candidates in column: r4r5 c9 <> 6
Naked single: r4c9 = 4
block candidates in column: r1r2r3 c6 <> 4
hidden tuple of size 2 in block: r3c6 <> 2 r1c6 <> 7 r3c6 <> 7
hidden tuple of size 2 in block: r4c4 <> 7 r4c5 <> 7
naked tuple of size 2 in column: r2c6 <> 7
hidden single in block: r2c6 = 2
Naked single: r2c2 = 3
hidden tuple of size 2 in column: r6c1 <> 2 r6c1 <> 4 r7c1 <> 6 r6c1 <> 7 r6c1 <> 9
block candidates in column: r1r3 c3 <> 4
hidden tuple of size 3 in block: r5c3 <> 6 r5c3 <> 7 r6c3 <> 7 r5c3 <> 9 r6c3 <> 9
hidden tuple of size 3 in column: r1c5 <> 4 r3c5 <> 4 r1c5 <> 7 r3c5 <> 7
block candidates in row: r4 c7c8 <> 7
block candidates in column: r3r9 c2 <> 9
Naked single: r9c2 = 8
hidden single in block: r7c8 = 8
hidden single in row: r4c7 = 8
hidden single in row: r7c4 = 2
hidden single in row: r7c5 = 7
hidden single in column: r9c5 = 5
hidden single in column: r5c7 = 6
hidden single in block: r9c4 = 4
hidden single in row: r2c1 = 7
hidden single in row: r4c3 = 7
hidden single in column: r3c2 = 6
hidden single in column: r7c3 = 6
hidden single in column: r2c5 = 4
hidden single in column: r1c5 = 6
hidden single in column: r8c9 = 6
hidden single in block: r3c1 = 2
hidden single in block: r1c1 = 4
hidden single in block: r3c8 = 4
hidden single in block: r6c2 = 2
hidden single in block: r4c1 = 6
hidden single in block: r5c2 = 9
hidden single in block: r4c8 = 2
hidden single in block: r7c1 = 5
hidden single in block: r9c7 = 2
hidden single in block: r9c8 = 9
hidden single in row: r6c9 = 9
hidden single in row: r7c9 = 3
hidden single in row: r8c1 = 9
hidden single in row: r9c3 = 3
hidden single in column: r6c1 = 3
hidden single in column: r3c9 = 1
hidden single in column: r5c9 = 5
hidden single in block: r1c6 = 1
hidden single in block: r3c6 = 8
hidden single in block: r3c7 = 5
hidden single in block: r6c3 = 5
hidden single in block: r6c8 = 1
hidden single in block: r5c8 = 3
hidden single in block: r6c7 = 7
hidden single in row: r1c3 = 8
hidden single in row: r1c4 = 9
hidden single in row: r3c4 = 7
hidden single in row: r3c3 = 9
hidden single in row: r4c5 = 9
hidden single in row: r5c6 = 7
hidden single in row: r6c6 = 4
hidden single in column: r5c3 = 4
hidden single in column: r4c4 = 3
hidden single in column: r3c5 = 3
hidden single in column: r1c7 = 3
hidden single in column: r1c8 = 7

I hope Mike that this helps to track down the problems.
hkociemba
 
Posts: 63
Joined: 09 July 2017

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

Postby m_b_metcalf » Sun Aug 27, 2017 10:37 am

m_b_metcalf wrote: In fact, it would perhaps help with my diagnostics if you could make a few 9x9 and 16x16 puzzles available.

Thanks for all those puzzles. I have now identified one silly reason that I thought that these were harder than you stated, namely that in my testing code I'd left a section activated that should not be. When I correct that, we agree on all the 9x9, 16x16 and 25x25 puzzles. That leaves the original problem I had with, for instance, your 144x144_triples.txt, and I will work on that next week. Sorry for any inconvenience.

Regards,

Mike

P.S. I had a bit of a problem with your terminology. You appear to use the term 'block' for a technique for what we commonly call pointing, as well as also for a region of a puzzle that we commonly call a box. Also, we usually call the attribute that you refer to as 'optimal' as minimal.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8238
Joined: 15 May 2006
Location: Berlin

re: terminology

Postby Pat » Sun Aug 27, 2017 10:45 am

m_b_metcalf wrote:

    You appear to use the term 'block' for a technique for what we commonly call pointing,
    as well as also for a region of a puzzle that we commonly call a box.

no, he uses block for box
-- that's fairly common

    "block_candidates_in_row"
    is b\r
    (the candidates for S in box B
    are all in row R)
User avatar
Pat
 
Posts: 3391
Joined: 18 July 2005

Re: re: terminology

Postby m_b_metcalf » Sun Aug 27, 2017 10:56 am

Pat wrote:block_candidates_in_row"
is b\r
(the candidates for S in box B
are all in row R)[/list]

... which is pointing (according to SE) rather than pairs or triplets.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8238
Joined: 15 May 2006
Location: Berlin

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

Postby hkociemba » Sun Aug 27, 2017 11:12 am

Since I deal with Sudoku just since a few month any comments from experienced "Sudokuers" about terminology are welcome. I did not like the term "pointing" and "claiming" because they give me no clue what they really mean. So I decided to use block_candidates_in_row and row_candidates_in_block for example. The first one is called pointing, the second is called "claiming" acoording to http://hodoku.sourceforge.net/en/tech_intersections.php. Eventually the second is called also "pointing" by some people. Of course it would be no problem to add the terminology in my program in brackets if this would reduce confusion.
I will use "minimal" instead of "optimal" in future and eventually edit my older posts.
hkociemba
 
Posts: 63
Joined: 09 July 2017

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

Postby m_b_metcalf » Fri Sep 01, 2017 12:38 pm

m_b_metcalf wrote:..., we agree on all the 9x9, 16x16 and 25x25 puzzles. That leaves the original problem I had with, for instance, your 144x144_triples.txt, and I will work on that next week. Sorry for any inconvenience.

I am now happy to report that new_100x100_5848__tripleOptimal now also yields to my solver, with its new hidden triplets code. However, it does not solve 144x144_triples, and before I investigate further could you please confirm that it requires only basic methods up to triples, just like the 100x100.

Thanks,

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

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

Postby hkociemba » Sat Sep 02, 2017 7:45 am

Yes I can confirm this, I reloaded the file from this forum to go sure that we use the same file. The solution is appended. It uses 131 times hidden triples and 112 times naked triples, the first time a triple is needed to continue the solving proceess is line 671. Btw. I still run the reduce program on the 225x225 and meanwhile there are only 35514 givens left. About 20% of the cells have been checked now...
Attachments
144x144triples_solution.zip
(84.07 KiB) Downloaded 8 times
hkociemba
 
Posts: 63
Joined: 09 July 2017

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

Postby m_b_metcalf » Sat Sep 02, 2017 8:57 am

hkociemba wrote:Yes I can confirm this, I reloaded the file from this forum to go sure that we use the same file. The solution is appended. It uses 131 times hidden triples and 112 times naked triples, the first time a triple is needed to continue the solving proceess is line 671.

Thanks. However, by the time the program stops it has performed 368 naked (candidate) eliminations and 165 hidden. There is an effect known from 9x9s whereby different solution paths can very occasionally have different maximum degrees of difficulty, and perhaps that is occurring in such monsters. I'll investigate further when I have time.

Regards,

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

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

Postby hkociemba » Sat Sep 02, 2017 12:59 pm

m_b_metcalf wrote:There is an effect known from 9x9s whereby different solution paths can very occasionally have different maximum degrees of difficulty

Thats really new for me. When does that happen? If I allow for example only singles it seems quite obvious for me that I always end up at the same point, no matter in which order I proceed. So which methods could have such an effect?
hkociemba
 
Posts: 63
Joined: 09 July 2017

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

Postby m_b_metcalf » Sat Sep 02, 2017 1:18 pm

hkociemba wrote:
m_b_metcalf wrote:There is an effect known from 9x9s whereby different solution paths can very occasionally have different maximum degrees of difficulty

Thats really new for me. When does that happen? If I allow for example only singles it seems quite obvious for me that I always end up at the same point, no matter in which order I proceed. So which methods could have such an effect?

I'll have to rely on pat's elephantine memory to find an answer to that. It was a long time ago, and maybe on the Programmers' Forum. Obviously, it was more complicated than just singles.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8238
Joined: 15 May 2006
Location: Berlin

re: 144-squared triples

Postby Pat » Sun Sep 03, 2017 7:46 am

m_b_metcalf wrote:There is an effect known from 9x9s
whereby different solution paths
can very occasionally have different maximum degrees of difficulty

sorry but the ONLY case i know
involves deducing-from-uniqueness-of-answer.

    after some cells have been solved,
    the "uniqueness" argument SEEMS to vanish,
    thus requiring some tougher methods.

      even then,
      one merely needs to remember the difference
      between solved cells and given cells,
      and the "uniqueness" argument re-appears.
User avatar
Pat
 
Posts: 3391
Joined: 18 July 2005

re: 144-squared triples

Postby Pat » Sun Sep 03, 2017 7:47 am

m_b_metcalf wrote:
hkociemba wrote:uses 131 times hidden triples
and 112 times naked triples

the first time a triple is needed is line 671

by the time the program stops
it has performed 368 naked (candidate) eliminations
and 165 hidden.

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---
User avatar
Pat
 
Posts: 3391
Joined: 18 July 2005

Re: re: 144-squared triples

Postby m_b_metcalf » Sun Sep 03, 2017 8:32 am

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

PreviousNext

Return to Sudoku variants