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

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: re: 144-squared triples

Postby hkociemba » Sun Sep 03, 2017 9:37 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---

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

re: 144-squared triples

Postby Pat » Sun Sep 03, 2017 1:44 pm

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

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

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

  • r39c76 had the 3 possibilities of the trio
    PLUS just these 2 -- 117,136
  • r39c78 had the 3 possibilities of the trio
    PLUS just this 1 -- 136
  • and the 3rd cell of the trio is not even mentioned
    -- it had the 3 possibilities of the trio
    PLUS NONE !!
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

Re: re: 144-squared triples

Postby hkociemba » Sun Sep 03, 2017 11:00 pm

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

Re: re: 144-squared triples

Postby m_b_metcalf » Mon Sep 04, 2017 4:47 pm

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

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

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

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

Thanks,

Mike Metcalf


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

is now rated as 7.2/7.2/3.2 (but has two hidden triplets as found by Sudoku Explainer in its third and fifth steps, as well as by my own program).
Attachments
ht.txt
(36.66 KiB) Downloaded 9 times
problem144.txt
(81.28 KiB) Downloaded 9 times
Last edited by m_b_metcalf on Tue Sep 05, 2017 6:07 am, edited 1 time in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8373
Joined: 15 May 2006
Location: Berlin

Re: re: 144-squared triples

Postby hkociemba » Mon Sep 04, 2017 9:49 pm

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

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

P.S: I entered 009000600000301000800050002050708030008000700070503040200030009000407000006000100 # 138

In my opinion it has no hidden triplets. It cannot be solved with basic methods, even worse my solver cannot apply any basic method at all here.
Attachments
continuation144.txt
(33.87 KiB) Downloaded 10 times
hkociemba
 
Posts: 66
Joined: 09 July 2017

Re: re: 144-squared triples

Postby m_b_metcalf » Tue Sep 05, 2017 6:11 am

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

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


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

Regards,

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

re: 144-squared triples

Postby Pat » Tue Sep 05, 2017 10:20 am

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

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

    Hope you reach this hidden single in column 15 somehow!

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

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

    hidden tuple of size 3 with numbers 37, 63, 71 in block 17:
    r13c57 <> 97,121, r16c49 <> 53, r___c___ <> NONE,
is again of that un-usual type mentioned in my previous post --
one of the 3 cells of the trio
has NO exclusions (already had only values from the trio).
un-usual -- presents an opportunity for software to fail.
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

re: 144-squared triples

Postby Pat » Tue Sep 05, 2017 10:25 am

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

Re: re: 144-squared triples

Postby m_b_metcalf » Tue Sep 05, 2017 10:57 am

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

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

Regards,

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

re: a 7.2 was previously rated 4.0 ??

Postby Pat » Tue Sep 05, 2017 11:04 am

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

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

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

    It cannot be solved with basic methods

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

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

User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

re: "hidden" triples

Postby Pat » Tue Sep 05, 2017 11:22 am

m_b_metcalf wrote:

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

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

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

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

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

    and i can probably find a test-case rated 3.2
    which you CAN solve with triplets
    (the X-wing being replaced by subsets).
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

re: 144-squared triples

Postby Pat » Tue Sep 05, 2017 11:27 am

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

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

    including steps 1-369
    (singles,intersections,duos)
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

re: triples

Postby Pat » Tue Sep 05, 2017 11:59 am

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

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

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

    champagne # 205 # (36210) # (discussion)

    (Layout 205 of the Patterns Game)
User avatar
Pat
 
Posts: 3441
Joined: 18 July 2005

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

Postby hkociemba » Wed Sep 06, 2017 8:17 am

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

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

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


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

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

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

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

Postby m_b_metcalf » Wed Sep 06, 2017 8:49 am

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

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

Thanks anyway,

Mike

P.S. Seems that you're slowly becoming equipped to play in the Patterns Game!
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8373
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to Sudoku variants