The New Sudoku Players' Forum

[hkociemba]

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).

[Pat]

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 !!

[hkociemba]

• 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.

[m_b_metcalf]

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).


Edit: File attachments deleted.

[hkociemba]

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.

[m_b_metcalf]

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

[Pat]

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.

[Pat]

and a little later
(step 375)

hidden tuple of size 3 with numbers 35, 55, 118 in block 74:
r76c22 <> 114, r___c___ <> NONE, r___c___ <> NONE,

is even more un-usual,
two of the 3 cells of the trio
have NO exclusions

[m_b_metcalf]

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

[Pat]

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

obtained from
(a modified version of) SuDoku Explainer

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)

the anomaly is that during game 17
this puzzle was rated 4.0 -- impossible

[Pat]

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).

[Pat]

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)

[Pat]

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)

[hkociemba]

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.

[m_b_metcalf]

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!