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

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re:

Postby hkociemba » Sun Sep 17, 2017 5:36 pm

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

Nice, I understand. And it is even more interesting since it directly has touches the discussion with Mike about what is a pair. If really both cells must have two candidates for a pair it is independent of the order impossible to delete the other various possibilities from the cell which initially contains {3,4}. Lets call this a regular pair. On the other hand if we first allow to handle the irregular pair we can delete all other candidates in the {3,4} cell. Of course the problem only arises because we forbid to take out the hidden singles.
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby hkociemba » Sun Sep 17, 2017 6:21 pm

m_b_metcalf wrote:If you patch your code in that way we can certainly make more meaningful comparisons.

Since you disallow pairs with the structure {1,2}, {2} do you also disallow triplets for example with the structure {1,2},{2,3},{3} ?
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 pm

hkociemba wrote:
m_b_metcalf wrote:If you patch your code in that way we can certainly make more meaningful comparisons.

Since you disallow pairs with the structure {1,2}, {2} do you also disallow triplets for example with the structure {1,2},{2,3},{3} ?

It looks as though this is allowed as a naked triplet, but not as part of a hidden triplet (because 1 appears only once). In the normal course of events it would be detected as a two singles.
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 8:41 pm

m_b_metcalf wrote:
hkociemba wrote:
m_b_metcalf wrote:If you patch your code in that way we can certainly make more meaningful comparisons.

Since you disallow pairs with the structure {1,2}, {2} do you also disallow triplets for example with the structure {1,2},{2,3},{3} ?

It looks as though this is allowed as a naked triplet, but not as part of a hidden triplet (because 1 appears only once). In the normal course of events it would be detected as a two singles.

I really do not understand why this should be a valid naked triplet but not part of a valid hidden triplet. As a naked triplet there is one number (3) which appears in only one cell and two numbers (1,2) which appear in two cells. As part of a hidden triplet there is one number (1) which appears at one position and two numbers (2,3) which appear in two positions. So this is totally equivalent.

Edit: Not totally equivalent. As a naked triplet it resolves to three naked singles, as a hidden triplet only one hidden single can be removed.

So I am unsure what to do exactly to make our programs comparable. Of course I would prefer to keep the more general definition for pairs, triplets etc. because in this case there is no discussion what is valid and what not. And the program logic to dectect pairs, triplets,... is very simple: You just OR for example three bitvectors (naked: bitvector for a certain row and column position describes the numbers(candidates) in the corresponding cell, hidden: bitvector for a certain row/column/block and a certain number(candidate) decribes the positions of this number within the row/column/block) and if in the resulting bitvector exactly three bits are set we have a triplet.
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Mon Sep 18, 2017 7:00 am

hkociemba wrote:I really do not understand why this should be a valid naked triplet but not part of a valid hidden triplet. As a naked triplet there is one number (3) which appears in only one cell and two numbers (1,2) which appear in two cells. As part of a hidden triplet there is one number (1) which appears at one position and two numbers (2,3) which appear in two positions. So this is totally equivalent.

So I am unsure what to do exactly to make our programs comparable. Of course I would prefer to keep the more general definition for pairs, triplets etc. because in this case there is no discussion what is valid and what not. And the program logic to dectect pairs, triplets,... is very simple: You just OR for example three bitvectors (naked: bitvector for a certain row and column position describes the numbers(candidates) in the corresponding cell, hidden: bitvector for a certain row/column/block and a certain number(candidate) decribes the positions of this number within the row/column/block) and if in the resulting bitvector exactly three bits are set we have a triplet.

Well, in a formal sense, that's all true. However, a human solver would certainly solve those cells using singles and so too does Sudoku Explainer, with which my program has to be compatible. If I were to submit such a 'hidden triplet' (rating 4.0) in the Patterns Game, I would get a 50 points fine because it's also a lower-rated hidden single (rating 1.2). There is a convention to take the easier path when several are available.

Here's a quotation from http://www.sudokuwiki.org/Naked_Candidates:

"The combinations of candidates for a Naked Triple will be one of the following:

(123) (123) (123) - {3/3/3} (in terms of candidates per cell)
(123) (123) (12) - {3/3/2} (or some combination thereof)
(123) (12) (23) - {3/2/2/}
(12) (23) (13) - {2/2/2}"


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 hkociemba » Mon Sep 18, 2017 8:51 am

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

Ok, I now put a conditional compiler directive "STRICT_TUPLES" into my program. If true, no tuple may contain a subtuple of shorter length. Interestingly the values still differ. Using your order I get
95 givens, 711 candidates when using pointing/claiming and naked+hidden pairs. Except for one steps it is all pointing/claiming.
Hidden Text: Show
r5 c16 n9
r5 c16 n16
r6 c15 n8
r6 c15 n9
hidden tuple of size 2 with numbers 11, 12 in block 8: r5c16 <> 9,16 r6c15 <> 8,9
r1 c13 n3
r1 c14 n3
block 2 candidates for number 3 all in row 1 (pointing): r1 c13c14 <> 3
r3 c4 n5
block 3 candidates for number 5 all in row 3 (pointing): r3 c4 <> 5
r2 c14 n9
r2 c15 n9
r2 c16 n9
block 3 candidates for number 9 all in row 2 (pointing): r2 c14c15c16 <> 9
r5 c13 n9
r5 c14 n9
block 5 candidates for number 9 all in row 5 (pointing): r5 c13c14 <> 9
r6 c1 n2
r6 c3 n2
r6 c4 n2
r6 c6 n2
r6 c8 n2
block 7 candidates for number 2 all in row 6 (pointing): r6 c1c3c4c6c8 <> 2
r6 c6 n15
r6 c7 n15
block 7 candidates for number 15 all in row 6 (pointing): r6 c6c7 <> 15
r8 c1 n13
r8 c3 n13
r8 c9 n13
r8 c10 n13
r8 c11 n13
block 8 candidates for number 13 all in row 8 (pointing): r8 c1c3c9c10c11 <> 13
r14 c1 n6
r14 c2 n6
r14 c3 n6
r14 c11 n6
block 16 candidates for number 6 all in row 14 (pointing): r14 c1c2c3c11 <> 6
r5 c4 n5
r8 c4 n5
block 1 candidates for number 5 all in column 4 (pointing): r5r8 c4 <> 5
r5 c8 n6
r7 c8 n6
block 2 candidates for number 6 all in column 8 (pointing): r5r7 c8 <> 6
r11 c5 n11
block 2 candidates for number 11 all in column 5 (pointing): r11 c5 <> 11
r14 c8 n13
block 2 candidates for number 13 all in column 8 (pointing): r14 c8 <> 13
r9 c13 n9
r12 c13 n9
r13 c13 n9
r14 c13 n9
block 8 candidates for number 9 all in column 13 (pointing): r9r12r13r14 c13 <> 9
r13 c14 n13
r15 c14 n13
block 8 candidates for number 13 all in column 14 (pointing): r13r15 c14 <> 13
r9 c2 n15
r11 c2 n15
block 13 candidates for number 15 all in column 2 (pointing): r9r11 c2 <> 15
r9 c11 n14
r10 c11 n14
r11 c11 n14
block 15 candidates for number 14 all in column 11 (pointing): r9r10r11 c11 <> 14
r7 c1 n6
r7 c2 n6
r8 c1 n6
r8 c2 n6
r8 c3 n6
r8 c4 n6
row 5 candidates for number 6 all in block 5 (claiming): r7c1 r7c2 r8c1 r8c2 r8c3 r8c4 <> 6
r13 c13 n16
r13 c14 n16
r13 c15 n16
r13 c16 n16
r14 c13 n16
r14 c15 n16
r14 c16 n16
row 16 candidates for number 16 all in block 16 (claiming): r13c13 r13c14 r13c15 r13c16 r14c13 r14c15 r14c16 <> 16
r9 c6 n15
r10 c6 n15
r11 c5 n15
column 7 candidates for number 15 all in block 10 (claiming): r9c6 r10c6 r11c5 <> 15
r15 c11 n13
r15 c12 n13
block 14 candidates for number 13 all in row 15 (pointing): r15 c11c12 <> 13

I am really interested why there still is a difference.

Edit: I get the same result with my order.
Including naked singles with my order I get the same result.

Edit2: I changed some values because the STRICT_TUPLES stuff was not correct and is more complicated than I thought. It should be correct for pairs but for triplets it is still not working.
Last edited by hkociemba on Mon Sep 18, 2017 1:48 pm, edited 1 time in total.
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Mon Sep 18, 2017 9:45 am

hkociemba wrote:I am really interested why there still is a difference.

Edit: I get the same result with my order.
Including naked singles with my order I get 97 givens, 685 candidates.

I'll try to look into this later in the week, which is rather busy. In the meantime, have you tried the famous 'step 7.' using "STRICT_TUPLES"?

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 » Mon Sep 18, 2017 10:23 am

m_b_metcalf wrote:I'll try to look into this later in the week, which is rather busy. In the meantime, have you tried the famous 'step 7.' using "STRICT_TUPLES"?


Yes, and now I get 14657 givens, 52680 candidates within one second with your order and also with mine. This is also less than your 52965...
I think it is not useful to put the output here unless our numbers match for the smaller examples.

Edit: I found an error in the STRICT_TUPLES code. So this value is probably too small. Try to fix it as soon as possible.
Edit2: I think I have fixed the problem. It was necessary to tackle the problem with a recursive procedure which sometimes is hard to debug. Now I get in your and in my order 52936 candidates.
Last edited by hkociemba on Mon Sep 18, 2017 10:41 pm, edited 2 times in total.
hkociemba
 
Posts: 66
Joined: 09 July 2017

Postby Pat » Mon Sep 18, 2017 10:46 am

m_b_metcalf wrote:
hkociemba wrote:

    Since you disallow pairs
    with the structure {1,2}, {2} --

    do you also disallow triplets
    with the structure {1,2},{2,3},{3} ?

It looks as though this is allowed as a naked triplet

would you be able to verify this
via some example?

    gsf's software does accept these situations
    (for pair, for triplet; "naked" or "hidden")
    as he allows the user full control of the order of methods

    SuDoku Explainer too !
    (if you work via GUI)
User avatar
Pat
 
Posts: 3424
Joined: 18 July 2005

Postby Pat » Mon Sep 18, 2017 11:01 am

hkociemba wrote:
m_b_metcalf wrote:have you tried the famous 'step 7'
using "STRICT_TUPLES"?

Yes, and now I get

    14657 givens {correct to: known cells},
    52680 candidates
within one second
with your order and also with mine.

This is also less than your 52965...

          { in my English,
          given cells + solved cells = known cells }

case 7 (NO "singles" recognized)
is normally a very heavy run

    progress gradually adds many (un-recognized) "naked singles"

    when 2-or-more of them share a house,
    they are recognized as a "naked" duo

    when 3-or-more of them share a house,
    they are recognized as a "naked" trio

    say we've reached an advanced stage
    and the typical house contains 100 (un-recognized) "naked singles"

    finding a million "naked" duos
    is not very expensive

    but exhausting "naked" duos,
    we now find 50 million "naked" trios---

with STRICT_TUPLES
this work
(productive but very time-consuming)
vanishes
User avatar
Pat
 
Posts: 3424
Joined: 18 July 2005

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

Postby hkociemba » Tue Sep 19, 2017 2:32 pm

I think I will make my solver available once the results with Mike's solver converge to the same value. The only thing I still would like to integrate is a puzzle generator. In the moment I just take a solved puzzle and remove redundant entries, eventually respecting one of the symmetries. So what is a good way to generate a solved puzzle? Of course there are trivial ways for filling the cells and the rows, columns, bands and stacks can be permuted in various ways, but this gives only a small fraction of all posibilites. Any good idea or reference?
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Wed Sep 20, 2017 7:04 am

hkociemba wrote:I think I will make my solver available once the results with Mike's solver converge to the same value. The only thing I still would like to integrate is a puzzle generator. In the moment I just take a solved puzzle and remove redundant entries, eventually respecting one of the symmetries. So what is a good way to generate a solved puzzle? Of course there are trivial ways for filling the cells and the rows, columns, bands and stacks can be permuted in various ways, but this gives only a small fraction of all posibilites. Any good idea or reference?

Herbert, I simply don't have the time at the moment to answer this in any detail. You might get a better response if you pose the question in the General section of this forum. The generation of solution grids was a subject of great debate on the now-defunct Programmer's Forum, where you will find useful contributions, such as here. gsf produced a set of CDs with all the billions of non-isomorphic grids years ago. Finding them would require some research.

HTH

Mike Metcalf

P.S. Something I wrote aeons ago:

"I decided instead to generate a grid by filling its first row with the nine digits in a random order, obtained using random_number, and then adding subsequent rows of randomly arranged digits, sorting their order as necessary to avoid clashes with digits already in place on previous rows or already in the current box. If this cannot be done, a fresh set of random numbers is used. For the third and sixth rows, an additional check is required that the box constraint is also fulfilled. Also, a deadlock condition can arise when the three digits missing from an almost completed box have already been assigned to a single column above the box. If this occurs, the program restarts.
...
"Since it had been written in a parameterized way, it worked too for any square grid from 4 x 4 upwards. (Larger grids not only require more computation, but contain ever more complicated potential deadlock conditions.)"
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 » Wed Sep 20, 2017 11:10 am

Thanks for the hints and the link. I'm quite uncertain if this works for large grids like 100x100. I think I try a simulated annealing approach first and look if that works. While I retired a year ago and have really much more time than before I am conscious that this is not the case for most other people. Hope that you have time to look for the 16x16 sometimes and why you have more than then 711 candidates left than the result I got here. http://forum.enjoysudoku.com/giant-sudoku-s-16x16-25x25-36x36-100x100-t6578-105.html#p259428
hkociemba
 
Posts: 66
Joined: 09 July 2017

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

Postby m_b_metcalf » Wed Sep 20, 2017 11:53 am

hkociemba wrote: I'm quite uncertain if this works for large grids like 100x100.

It works well, with some refinements, up to 49x49. A variation can be used for higher, even, sizes. I couldn't resist testing what I've said: a 49x49 solution grid was produced in 7s and then reduced to this symmetric puzzle using basics in another 2mins.

Regards,

Mike Metcalf
Code: Select all
  5 44 19 16  .  . 10 27 36 32 45 18  . 41  . 14 23  . 40  4 26 21 42  . 46  . 49  3  8 35 17  .  9 38  . 12  . 31 33 39 47  6 30  .  . 25 29 37 24
 42  . 34  .  4 17 25 16 43 10  . 31  . 14 45 30  . 32 47  .  . 40 22  8  .  7 20 27  .  . 36  3  . 29 13  9  . 28  . 23 21 37 44 39 12  . 18  . 11
 27 35  .  7  .  .  .  .  .  . 44  . 29  3  .  .  . 38 16 12  . 23  .  .  2  .  . 47  . 25 19  1  .  .  . 40 13  . 48  .  .  .  .  .  . 31  . 26  8
  . 29 23  .  .  .  .  .  .  .  .  . 35  . 36  .  . 33  . 15  . 12 26 16 39 13  5 17  .  4  . 47  .  . 11  .  2  .  .  .  .  .  .  .  .  .  1 49  .
  . 36 31 14  .  2  .  . 23  .  . 40  . 12 25 29 48  .  .  8 39  .  .  4 45 19  .  . 18  6  .  . 37 20 24 27  . 49  .  .  1  .  . 21  . 32  5 47  .
  . 13  . 22  .  .  9  .  .  .  . 30 24 47 34 44 35  .  5  .  .  .  6 33  . 18 28  .  .  . 21  . 27 41 43 42 25 14  .  .  .  . 23  .  .  4  . 19  .
 46 32 47 18  .  .  . 39  1 22 34  5 11 49 17 20  . 31 24  . 42  .  . 35  . 15  .  . 33  . 12 44  . 30 14  4 19 36 10  3 16 26  .  .  .  6 38 28 48
 20  . 38 32 42 33  . 44 21 31 12 15  . 17  1 25 13  9  7 43 23 28  2  .  .  . 37 16 27  5 18 34  8 49 29  3  . 22 14 48  6 40  .  4 19 46 26  . 41
  .  .  .  .  .  .  .  .  6 36  .  .  .  . 12  .  .  .  .  .  .  .  . 46  . 35  .  .  .  .  .  .  .  . 25  .  .  .  .  1 28  .  .  .  .  .  .  .  .
 19  .  . 12  . 46 17 13 11  9 49 28  . 45  .  .  . 42 35  .  4 41 39 32  6 25 38 10 30  . 48 43  .  .  . 33  . 23 31 20 26 29  8  5  . 34  .  . 14
  8  . 16  .  .  . 30 24  .  .  . 39  . 33  . 11 32  . 49 40  .  . 13  . 14  . 34  .  . 15 31  . 28  1  . 41  .  7  .  .  .  2 12  .  .  . 23  . 27
  . 37  . 47 23 29  .  .  .  . 22  1  5 48  3  . 17  .  . 16 46 27 18 15  . 43 31 40 24  7  .  . 20  . 41 13 36 35 25  .  .  .  . 32 38 39  . 42  .
  .  .  .  .  .  . 14  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 33  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 11  .  .  .  .  .  .
 49 18  1  .  . 35  . 23  .  .  7 41 14 32 39  . 29  . 21 10  . 19 12  .  .  .  3 44  . 38 45  . 22  . 37 16 24 15  4  .  . 42  . 30  .  . 31 17 20
 29  .  .  . 33 34 44  2  .  4 40  6  .  5 41  7  .  . 11  . 47  .  . 19 30 46  .  . 37  . 25  .  . 16 21 10  .  9 39 27  . 12 48 38 26  .  .  . 42
 32  . 35 19  . 31  . 33 34  . 17 36  .  . 16  . 24 39 48 26 14  .  .  6 40 20  .  .  3 46 43 30 13  . 38  .  . 25  1  . 42  7  . 22  . 10  2  .  9
 21  .  9 40  . 38 46  . 18  3  . 22 28  .  .  .  6  . 29  . 37 14  1  .  .  . 39  7 11  .  5  . 19  .  .  . 15 16  . 43 48  . 33 35  . 23 27  .  4
  6  .  . 24 12  . 27 46 19 29  .  . 43  9 13 33  .  . 15  .  . 16 44 17  .  2 48 42  .  .  7  .  . 45 10 49 31  .  . 36 35 14 28  . 11 37  .  . 32
  .  7 22 48 11  . 37 32 45  . 47  . 30 26 23  . 43  1  . 42 20  .  .  . 15  .  .  . 35 18  . 49 14  .  9 28 41  .  6  .  2 34 19  . 44 40 16 31  .
 14 16 43  .  1 15  . 11 12 37 39  . 48  . 27  . 49  .  . 36 21 34  .  .  .  .  . 22  4  8  .  . 29  .  2  . 23  .  3 40 38 30  . 47 46  . 13  6 25
  . 10  .  .  2  5  . 38 20  1  .  . 25 42  . 12  . 35 45 31  . 32 28 27 37 41  4  8  . 44 40 24  . 47  . 19 11  .  . 26 46 13  . 43 49  .  . 18  .
  3  . 29 37 24 48 18 36  . 25  2  .  8  . 20  .  5 40  .  . 43  .  9 11  . 33 47  .  7  .  . 21 26  . 49  . 39  . 46 14  . 22 16  6 27 35 30  . 10
  . 40  .  .  .  .  .  .  .  .  1  .  . 29 22  .  .  .  .  .  . 26  .  .  .  .  . 35  .  .  .  .  .  . 12 21  .  . 20  .  .  .  .  .  .  .  . 36  .
  9 30 10 39 46 12 15 18  . 38  . 17  .  . 37 47  8  .  . 23  . 20 40 43 27  6  1 28  . 19  .  .  5 33 45  .  . 13  . 16  . 48 14 49  4  2 21 34  7
  7  2  . 35 20  . 16 40  . 11 19  . 21  . 24  9  . 10 44  6 38  .  . 41  .  8  .  . 23 39 27 17  . 37 31  . 30  . 28 18  . 43 26  . 13 47  . 48 45
 28 26 42 36 25 23 45 49  . 15  .  3  .  . 14 39 18  .  . 48  . 17 37 31 29 44 21  4  . 24  .  .  2  8 16  .  . 32  . 12  . 27 22 11 20  5  9 40  1
  .  5  .  .  .  .  .  .  .  . 48  .  . 39 49  .  .  .  .  .  . 46  .  .  .  .  . 14  .  .  .  .  .  . 22  7  .  . 36  .  .  .  .  .  .  .  .  8  .
 17  . 27 13 22  1 47  5  . 12 14  . 33  .  4  . 31 46  .  . 16  . 10 34  . 24  2  . 28  .  . 29 40  . 36  . 35  .  9 37  . 25 38 19 18 41 39  . 15
  . 46  .  .  9 47  . 31 41 18  .  .  1 27  .  3  . 30 36 29  . 24 14 48 16 32 19 43  . 22 49  7  . 21  . 23  8  .  . 13 40 33  . 28 25  .  . 45  .
 23 14 15  .  3  7  . 26  8 46 10  . 20  . 42  . 19  .  . 37 40 29  .  .  .  .  .  2 43 47  .  . 16  . 33  . 44  . 17 49 25 41  .  9 21  . 12  1 22
  .  1 45  5 19  .  6 15 17  .  3  .  9 23  8  . 20 41  . 35 25  .  .  . 42  .  .  .  2 30  . 28 12  . 27 18 48  . 37  . 34 38 32  . 36 16 33 29  .
 37  .  . 42 32  . 29 45 33 43  .  . 39 34  7  1  .  . 26  .  .  5 47 12  . 22 35 21  .  .  4  .  . 40 18 11 14  .  . 28 30 16 10  . 41 17  .  .  2
  4  . 28 30  . 10 48  . 49 19  . 42 44  .  .  . 47  . 46  .  2 36 33  .  .  . 27 15 31  . 34  . 41  .  .  . 32 20  . 35 22  . 39 24  . 18 43  . 40
 44  . 41 21  . 13  .  4 16  . 36  2  .  . 32  . 10 15 28 33 34  .  .  9 18 37  .  . 25 14  1 20 17  . 23  .  .  6 45  .  7  5  . 27  . 19 48  .  3
 33  .  .  . 18  8 12 48  . 28 21 32  . 40 38 13  .  . 31  . 17  .  . 10  3  1  .  . 36  .  9  .  . 39  6 47  . 43 27 42  .  4 49 37 15  .  .  . 26
 41 17 48  .  . 42  .  8  .  . 24 49 40 21 26  . 12  . 37 27  . 38 11  .  .  . 29  1  . 34 20  . 31  . 19 44 18 46 30  .  .  3  .  7  .  . 22  9 13
  .  .  .  .  .  . 34  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 43  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  5  .  .  .  .  .  .
  . 20  . 29 44 16  .  .  .  .  4  9 36 19 48  . 15  .  . 34  6 49  8 39  .  3 32 31 22 12  .  . 45  .  5  2  7 27 11  .  .  .  . 17 23  1  . 33  .
  1  . 37  .  .  .  5 12  .  .  . 44  . 18  . 45 38  . 39 41  .  . 15  . 23  . 40  .  .  2 16  . 10  9  . 17  .  4  .  .  . 36 24  .  .  .  3  . 19
 22  .  . 31  . 26 23  1 14 20 43 10  . 30  .  .  . 28 18  .  7 35  5 37 19 27 24  9 48  .  8 40  .  .  . 29  . 45 41 38 49 39  6 36  . 12  .  . 16
  .  .  .  .  .  .  .  .  3 27  .  .  .  . 40  .  .  .  .  .  .  .  . 18  . 42  .  .  .  .  .  .  .  . 44  .  .  .  . 34  9  .  .  .  .  .  .  .  .
 24  . 18  3 10 40  . 34 32 17  5 23  .  7 33 31  4 22 20  9 19 45 36  .  .  . 41 30 29 49 28 37 11 42 35 15  . 26 12  6 14  1  . 46 39  8 25  . 21
 18  4 33 10  .  .  . 22 25 48 11 43 49 15 46 40  . 21 34  .  8  .  . 45  .  5  .  . 12  . 23  9  . 17 30 14 28 39  7 29 27 35  .  .  .  3 24 13 47
  . 47  . 46  .  . 21  .  .  .  .  4 42 36 35 26  7  . 17  .  .  . 19 20  . 11 12  .  .  . 37  . 49 24 15 48 45 38  .  .  .  . 18  .  . 27  . 22  .
  . 41 30 45  . 44  .  . 31  .  . 12  . 46 10 37 25  .  . 39 11  .  . 24 35 40  .  .  6 28  .  . 42 22  8 32  . 34  .  .  4  .  . 20  . 48 19 43  .
  . 38  7  .  .  .  .  .  .  .  .  .  6  . 30  .  . 24  . 28  . 42 25 29 13 47 17 39  . 45  . 46  .  .  4  .  1  .  .  .  .  .  .  .  .  . 15 32  .
 34 42  . 28  .  .  .  .  .  . 41  . 17 35  .  .  .  6 32 18  . 30  .  . 36  .  . 23  . 26 47 10  .  .  . 20 12  .  8  .  .  .  .  .  .  7  . 25 37
  2  .  3  .  6 14 26 29 47 23  . 24  . 37 31 16  . 49  9  .  .  4 48 44  . 21  8 32  .  . 13 18  . 43  7 25  . 10  .  5 41 19 46 33 45  . 17  . 38
 36 23  8 15  .  . 22  9 13  2 32 19  .  1  . 48 14  . 33 38 29 18 34  . 10  .  7 26 41 11 39  . 21  5  . 43  . 37 40 46 17 24  4  .  . 42 35 16 49
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 » Wed Sep 20, 2017 6:02 pm

Thanks, something like this is exactly what I need! I could not resist trying to solve this puzzle with my program. Your puzzle can be solved with basic methods including hidden tuples of size <=3, naked tuples of size <=4 and basic fishes of size <=3 with my solver in 0.3 s. The general SAT-solver needed 0.8 s to solve it. I fed the solution to my reduce routine using as I believe the same symmetry and created in 40 s a harder minimal puzzle which needs hidden+naked tuples + basic fishes of size <=4.
Hidden Text: Show
Code: Select all
  . 44  . 16  . 43 10  . 36 32  . 18  2  . 11  . 23  . 40  4 26 21  .  1  . 34  .  3  8 35 17  .  9  . 28  . 20 31  . 39 47  . 30 13  . 25  . 37  .
 42  6  .  1  4 17 25  . 43 10 26 31 19  . 45  . 41  . 47  2  . 40 22  .  .  . 20 27  . 48 36  . 46  . 13  . 38 28 35 23 21  . 44 39 12 33  . 15 11
 27  . 20  .  .  . 49  .  4 33 44 46  .  3  . 28  .  . 16  .  . 23  . 14  . 36  . 47  .  . 19  .  . 10  . 40  .  5 48 15 24  . 43  .  .  . 41  .  8
  .  .  . 38  .  .  .  7 37  .  .  . 35 25 36  . 27 33 19  .  . 12 26 16  . 13  5 17  .  . 22 47 32  . 11 30  2  .  .  .  8 44  .  .  .  9  .  .  .
 15 36 31 14  .  . 33 28  .  .  9  . 38 12 25 29  .  .  3  8  . 44  .  4 45 19  . 11  .  6 26  .  . 20 24 27 17  . 34  .  . 46  7  .  . 32  5 47 35
 26 13 12  . 39 11  . 17 15  . 20  . 24  .  .  .  . 37  5 46  1 31  . 33 48 18  . 38 49 40 21  2  .  .  .  . 25  . 29  . 32 45  . 16  3  . 10 19 36
 46  .  . 18 45 41  8 39  1  . 34  . 11 49  .  .  .  . 24 13 42 37 43  .  9  . 25 29 33 23 12  .  .  .  .  4 19  . 10  . 16 26 27  2 40  6  .  . 48
  .  .  . 32  .  . 36 44 21 31  .  . 47  .  1 25  .  9  7  . 23 28  .  . 11  .  . 16 27  . 18 34  . 49 29  . 10  .  . 48  6 40 35  .  . 46  .  .  .
  . 15 26  9  . 27 31 19  .  .  . 37  . 16  .  . 30  .  .  . 24  7 20 46  . 35 22 48 39  .  .  . 23  .  . 34  . 17  .  .  . 49  2 40  . 44 45 21  .
  . 24 21  .  . 46  .  . 11  .  .  . 18  . 15  . 44 42 35 22  . 41  . 32  . 25  . 10  . 16 48 43 47  . 40  . 27  .  .  . 26  .  .  5  .  . 37  3  .
  .  3 16  4  .  6 30 24 38  . 46 39  . 33  . 11  .  . 49 40 18  . 13  . 14  . 34  . 21 15 31  .  .  1  . 41  .  7 47  . 45  2 12 25  . 22 23 10  .
 45  . 44  . 23  .  . 30 10 34 22  .  . 48  3  .  .  .  2  . 46  . 18  . 49  . 31  . 24  . 11  .  .  . 41 13  .  . 25 19 12 21  .  . 38  .  6  . 33
 10 48  . 41  .  . 14  . 29  . 25 20  4  2  .  . 37 45  .  . 31  . 23 21 33 17 42  . 19  .  . 12 36  .  . 46  9 30 38  . 39  . 11  .  . 49  .  7 18
 49 18  1  .  5 35  . 23  . 40  7  . 14  . 39 34 29 48 21  . 33  . 12  .  8  .  3  .  9  . 45  6 22 46 37  . 24  .  4 11  . 42  . 30 28  . 31 17 20
  .  . 13  .  . 34  .  2  .  . 40  6  .  . 41  .  .  8  . 32 47  3 24 19  . 46 43 45 37 31  . 23  .  . 21  .  .  9 39  .  . 12  . 38  .  . 36  .  .
 32  .  .  .  . 31  .  .  .  .  . 36 27  . 16  .  .  . 48 26  .  .  .  .  .  .  .  .  . 46 43  .  .  . 38  .  4 25  .  .  .  .  . 22  .  .  .  .  9
 21 45  9 40 26  . 46 41 18  . 13 22  .  .  2  .  6  .  . 25  . 14  1  .  .  . 39  7  . 42  .  . 19  . 34  .  . 16 32  . 48 20 33  . 24 23 27 30  4
  .  8 25  .  . 18  .  . 19  . 23  . 43  9  . 33  .  . 15  .  . 16 44 17 38  2 48 42  .  .  7  .  . 45  . 49 31  .  5  . 35  .  .  1  .  . 34 41  .
  .  7 22 48  .  . 37  .  .  . 47  . 30 26  .  . 43  1  . 42 20 10 21 13  . 12 36 25 35 18  . 49 14  .  . 28 41  .  6  .  .  . 19  .  . 40 16 31  .
  .  . 43 20  1 15 42  .  .  . 39  7 48  . 27 19 49 18  . 36 21 34  .  5 26  9  . 22  4  8  . 32 29 28  2  . 23 44  3  .  .  . 17 47 46 45 13  .  .
 30  . 36 23  2  5  3 38 20  . 16 14 25 42  . 12 34 35  .  . 22  . 28 27  . 41  4  . 17  .  . 24  6 47  . 19 11 33 21  . 46 13 15 43 49 29  7  . 39
  . 34 29 37 24  . 18  .  .  .  2  .  . 28 20 15  5  .  . 17 43  .  .  . 32  .  .  .  7  1  .  . 26  4 49 38  .  . 46  .  .  . 16  . 27 35 30 23  .
 38 40  6  .  . 19  . 37  . 16  .  . 32 29 22  .  2  3  .  . 28  .  .  .  .  .  .  . 47  .  . 48 18  . 12 21 49  .  .  4  . 10  . 31  .  . 46 36 17
  .  .  .  .  . 12  . 18 42 38 31  .  .  . 37 47  8 29 25  .  . 20  .  . 27  .  . 28  .  . 35 11  5 33 45  .  .  . 24 16 44 48  . 49  .  .  .  .  .
  .  2 14  .  . 49  .  . 46 11  . 34 21  4 24  9  . 10 44  6  . 22  3 41 12  8 15 36  . 39 27 17  . 37 31  5 30  1  . 18 29  .  . 42  .  . 32 48  .
  .  .  .  .  . 23  . 49  7 15 35  .  .  . 14 39 18 34 30  .  . 17  .  . 29  .  .  4  .  . 38 41  2  8 16  .  .  . 19 12 33 27  . 11  .  .  .  .  .
 31  5  4  .  . 32  . 47  .  6  .  . 23 39 49  . 26 19  .  . 45  .  .  .  .  .  .  . 20  .  . 13 30  . 22  7 34  .  .  2  . 17  . 29  .  . 28  8 12
  . 21 27 13 22  . 47  .  .  . 14  .  . 20  4 32 31  .  . 11 16  .  .  .  7  .  .  . 28 43  .  . 40  6 36 45  .  .  9  .  .  . 38  . 18 41 39 44  .
 35  . 17 26  9 47 20 31 41  . 37 11  1 27  .  3 39 30  .  . 44  . 14 48  . 32 19  . 10  .  .  7 15 21  . 23  8 12  2  . 40 33 34 28 25 38  4  .  6
  .  . 15 27  3  7 39  .  .  . 10 35 20  . 42 18 19 11  . 37 40 29  . 28 34 30  .  2 43 47  .  5 16 48 33  . 44 24 17  .  .  . 31  9 21 13 12  .  .
  .  1 45  5  .  .  6  .  .  .  3  .  9 23  .  . 20 41  . 35 25 39 31 40  .  4 11 13  2 30  . 28 12  .  . 18 48  . 37  .  .  . 32  .  . 16 33 29  .
  . 31 49  .  . 36  .  . 33  .  6  . 39 34  .  1  .  . 26  .  .  5 47 12 20 22 35 21  .  .  4  .  . 40  . 11 14  . 15  . 30  .  . 23  .  .  8 46  .
  4 25 28 30 16  . 48 14 49  . 29 42  .  .  6  . 47  .  . 45  . 36 33  .  .  . 27 15  . 37  .  . 41  .  3  .  . 20 26  . 22  9 39  .  7 18 43  5 40
 44  .  .  .  . 13  .  .  .  .  .  2 12  . 32  .  .  . 28 33  .  .  .  .  .  .  .  .  . 14  1  .  .  . 23  . 29  6  .  .  .  .  . 27  .  .  .  .  3
  .  .  2  .  .  8  . 48  .  . 21 32  .  . 38  .  . 23  . 14 17 25  7 10  .  1 44 41 36 29  . 45  .  .  6  .  . 43 27  .  .  4  . 37  .  . 20  .  .
 41 17 48  . 35 42  .  8  . 39 24  . 40  . 26 23 12 16 37  . 32  . 11  . 28  . 29  . 15  . 20 33 31 36 19  . 18  . 30 47  .  3  .  7 43  . 22  9 13
 25  9  .  2  .  . 34  . 48  . 38 29 46  6  .  . 11 36  .  .  3  . 17 26 43 16 13  .  1  .  . 27  4  .  . 22 40 19 23  . 37  .  5  .  . 15  . 20 31
 47  . 46  . 44  .  . 35 26 41  4  .  . 19 48  .  .  . 43  .  6  .  8  . 21  . 32  . 22  . 24  .  .  .  5  2  .  . 11 25 10 28  .  . 23  . 40  . 30
  . 43 37 49  . 30  5 12 22  . 28 44  . 18  . 45  .  . 39 41 35  . 15  . 23  . 40  . 13  2 16  .  .  9  . 17  .  4 42  . 20 36 24 48  . 11  3 27  .
  . 33 11  .  . 26  .  . 14  .  .  . 13  . 47  . 46 28 18 44  . 35  . 37  . 27  .  9  . 17  8 40  3  . 32  . 21  .  .  . 49  .  . 36  .  . 42  4  .
  . 19 32  8  . 45  7 25  .  .  . 33  . 11  .  .  1  .  .  .  5 47  4 18  . 42 46 20 38  .  .  . 43  .  . 35  . 48  .  .  . 31 29 41  . 26 49  2  .
  .  .  .  3  .  . 13 34 32 17  .  . 16  . 33 31  . 22 20  . 19 45  .  . 44  .  . 30 29  . 28 37  . 42 35  . 43  .  .  6 14  1 47  .  .  8  .  .  .
 18  .  . 10 31 20 32 22 25  . 11  . 49 15  .  .  .  . 34 19  8  2 38  . 41  . 16 37 12 36 23  .  .  .  . 14 28  .  7  . 27 35  1 26  6  3  .  . 47
 13 47  5  . 40 39  . 10 28  . 33  . 42  .  .  .  .  2 17  1 41 43  . 20 31 11  .  6 34 32 37 25  .  .  .  . 45  . 16  .  3 23  .  8  9  . 14 22 29
 16 41 30 45  .  .  1  3  .  . 18  .  7 46 10 37  .  . 13 39  . 15  . 24 35 40  . 33  . 28 29  .  . 22  8 32 26  . 49  .  . 47 36  .  . 48 19 43 23
  .  .  . 43  .  .  . 20 40  .  .  .  6  8 30  .  3 24 23  .  . 42 25 29  . 47 17 39  .  .  2 46 33  .  4 31  1  .  .  . 36 18  .  .  . 21  .  .  .
 34  . 24  .  .  . 19  . 39  5 41 38  . 35  .  4  .  . 32  .  . 30  . 22  . 49  . 23  .  . 47  .  .  3  . 20  .  2  8 33 13  . 40  .  .  . 11  . 37
  2 12  . 11  6 14 26  . 47 23 30 24 34  . 31  . 36  .  9 20  .  4 48  .  .  .  8 32  . 27 13  . 35  .  7  . 42 10 22  5 41  . 46 33 45 28  . 39 38
  . 23  . 15  . 25 22  . 13  2  . 19 45  . 44  . 14  . 33 38 29 18  .  3  . 28  . 26 41 11 39  . 21  . 20  .  6 37  . 46 17  .  4 12  . 42  . 16  .

1353 givens, 6518 candidates
hkociemba
 
Posts: 66
Joined: 09 July 2017

PreviousNext

Return to Sudoku variants