The New Sudoku Players' Forum

by **Pat** » Wed Sep 06, 2017 11:03 am

Pat wrote:
step 371
hidden tuple of size 3 with numbers 37, 63, 71 in block 17:
r13c57 <> 97,121, r16c49 <> 53, r___c___ <> NONE,
is of that un-usual type --
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.

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

we all agree that this situation is a legitimate "hidden" trio,
and as you said this "has to be foreseen in the hidden triple algorithm"

but in the world of 9-squared,
this un-usual situation is rather rare --
so you tested hundreds of puzzles
but did you find even one of these "NONE"?

re-reading your post,
i see no explicit statement on this point

{/nag}

by **m_b_metcalf** » Wed Sep 06, 2017 12:27 pm

Pat wrote:so you tested hundreds of puzzles
but did you find even one of these "NONE"? {/nag}

Is this what you mean?

Hidden Text: Show

by **Pat** » Wed Sep 06, 2017 12:36 pm

m_b_metcalf wrote:Is this what you mean?

Code: Select all
. 1 . 2 3 4 . . . . . 3 5 6 7 . 1 . 6 . . 8 9 1 7 . . . 8 . . 7 . . . . . . 9 4 5 3 2 . . . 3 . . 8 . . 7 . . . 8 . 2 5 . . 9 3 5 . 6 1 9 4 . . . . . . 4 8 . 5 .

ED=4.0/4.0/2.8
8 values + 1 alien, 2 'nones'

yes !!
thanks.

duos

by **Pat** » Wed Sep 06, 2017 1:24 pm

Pat wrote:
now i'm left to wonder
if such strange cases happen with "hidden" duos too---

NONE

by **hkociemba** » Sun Sep 10, 2017 8:24 pm

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

I did some other test which was quite interesting. I took your second attachment problem144.txt with its 14657 givens and fed it again into my solver, disallowed singles and used only pointing, claiming, hidden/naked pairs and triplets.
Of course the puzzle cannot be solved without using singles but after 14314 steps there where only 6079 from the 144^3 candidates left - this is exactly one candidate for the 144^2 - 14657 = 6079 unsolved cells. So in principle the puzzle was solved. I append the verbose output (really weird) and @Pat: Again there are lots of hidden triplets which eliminate just one candidate...

P.S: It is not obvious that omitting singles always leads to exactly one left candidate for the unfilled cells. This does not seem to work for every puzzle.

by **hkociemba** » Wed Sep 13, 2017 1:39 pm

@Mike: Maybe it is possible to track down the problem if we compare the number candidates left when applying some basic methods to problem144.txt.

problem144.txt: 14657 givens, 54442 candidates
applying only:
1. pointing/claiming: 14657 givens, 53265 candidates
2. hidden pairs: 14657 givens, 54400 candidates
3. hidden pairs/triplets: 14657 givens, 54348 candidates
4. naked pairs: 14657 givens, 54298 candidates
5. naked pairs/triplets: 14657 givens, 54201 candidates
6. naked+hidden pairs + pointing/claiming: 14657 givens, 53055 candidates
7. naked+hidden pairs/triples + pointing/claiming (after a 30 min computation!): 14657 givens, 6079 (!) candidates
8. naked+hidden pairs/triplets + pointing/claiming+ hidden singles: 15070 givens, 47079 candidates
9. naked+hidden pairs/triplets + pointing/claiming+ naked singles: 14708 givens, 52335 candidates
10. naked+hidden pairs/triplets + pointing/claiming+ naked/hidden singles: solved

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 singles. The candidates left in case 7 are exactly one for each unfilled cell with exactly the right value, so this seems ok. Nevertheless it would be great if we could get the same numbers with two totally independent written programs which would considerably increase the confidence in the code. Computation time except for case 7 is at most a few seconds/case.

by **Pat** » Wed Sep 13, 2017 3:09 pm

hkociemba wrote:problem144.txt: 14657 givens, 54442 candidates
applying only:

7.
naked+hidden pairs/triples
+ pointing/claiming
(after a 30 min computation!):

14657 givens, 6079 (!) candidates

8.
naked+hidden pairs/triplets
+ pointing/claiming
+ hidden singles:

15070 givens, 47079 candidates
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.

{edit:} amazing but right. took me a while to see how this happens

by **m_b_metcalf** » Wed Sep 13, 2017 4:15 pm

hkociemba wrote:@Mike: Maybe it is possible to track down the problem if we compare the number candidates left when applying some basic methods to problem144.txt.

Herbert, a brilliant idea and so easy and fast to perform. Here is your list with my results added in red:

problem144.txt: 14657 givens, 54442 candidates

applying only:

same

54354

same

52965 in 11s.

52965

So, there are some interesting differences. Your result no. 7 really does appear odd! We still have a bit more work to do.

HTH

Mike Metcalf

[Edit]P.S. In 8 and 9 the number of givens is no longer 14657(?).

by **hkociemba** » Wed Sep 13, 2017 6:36 pm

Nr. 3 seems to be a good candidate to see the what is the difference since there are not many steps involved. I add the verbose output together with the 94 candidates. There should be 6 candidates which were not deleted by your program...

Hidden Text: Show

P.S. Yes in 8. and 9. there are some hidden and naked singles, so the number of givens changes.

by **m_b_metcalf** » Thu Sep 14, 2017 1:33 pm

hkociemba wrote:Nr. 3 seems to be a good candidate to see the what is the difference since there are not many steps involved. I add the verbose output together with the 94 candidates. There should be 6 candidates which were not deleted by your program...
[snip]

P.S. Yes in 8. and 9. there are some hidden and naked singles, so the number of givens changes.

Yes, thanks, that was very useful. I discovered that a premature exit from the code can be taken on rare occasions in a misguided effort to improve efficiency. When this is corrected, the table becomes (changes only)

So, the problem seems to be solved, but there are discrepancies in cases 7, 8 and 9 which I cannot explain. Especially 7!

Regards,

Mike Metcalf

P.S. I haven't understood your point about singles. Are you saying that some cells in problem144 can be solved only with singles?

by **hkociemba** » Thu Sep 14, 2017 7:57 pm

m_b_metcalf wrote:P.S. I haven't understood your point about singles. Are you saying that some cells in problem144 can be solved only with singles?

I mean that for example in Nr. 9 we use naked+hidden pairs/triplets + pointing/claiming + naked singles . At some point(s) we can apply this method and hence increase the number of givens. That's why I get 14708 instead of 14657 givens here. The first time a naked single appears is in step 385 with my solver. If for your solver naked singles never appear here I suppose something is wrong.

I realized another problem. It is not very intuitive but the order of the computation indeed has an influence on the result. If we for example take the result of Nr.7 everything what is left are naked singles - there is only one candidate left for each cell. So if we apply naked singles in the end the puzzle is solved. This differs from the result of Nr. 9 where the same methods are used but where naked singles is the method of first choice. I also observed that with Nr. 8 I got 15070 or 15069 givens depending on the order I use for the basic methods. So it will be difficult to compare the results unless we use exactly the same logic in which order the basic methods are applied.

by **m_b_metcalf** » Fri Sep 15, 2017 8:32 am

hkociemba wrote:I realized another problem. It is not very intuitive but the order of the computation indeed has an influence on the result. If we for example take the result of Nr.7 everything what is left are naked singles - there is only one candidate left for each cell. So if we apply naked singles in the end the puzzle is solved.

I agree that it is plausible that the order of processing can make a difference, but 7. is dramatic.

My order of processing for this test was:

Code: Select all: do until no more progress find naked pairs in rows/columns/boxes find hidden pairs in rows/columns/boxes if any found cycle find naked triplets in rows if any found cycle find naked triplets in columns if any found cycle find naked triplets in boxes if any found cycle find hidden triplets in rows if any found cycle find hidden triplets in columns if any found cycle find hidden triplets in boxes if any found cycle pointing/claiming end do

and that gives the figure of 52980 after no further progress. I have then altered the sequence to what I think you do, namely

Code: Select all: do until no more progress find naked pairs in boxes/rows/columns find hidden pairs in boxes/rows/columns find naked triplets in boxes/rows/columns find hidden triplets in boxes/rows/columns pointing/claiming end do

and find 52878 candidates left, a small change but not as dramatic as what you report. Maybe you could look into what your program spends 30 minutes doing?

Regards,

Mike Metcalf

by **hkociemba** » Fri Sep 15, 2017 6:09 pm

The output in the attachment was produced by this code which is I hope exactly what your program does. I dod not know if the order of the 4 kinds of pointing/claiming is important.:

Hidden Text: Show

The complete process takes more than 14000 lines and in this order even takes an hour to complete. I only add the output until there are less than 52000 candidates left. Hope that helps

by **m_b_metcalf** » Sat Sep 16, 2017 8:28 am

hkociemba wrote:The output in the attachment was produced by this code which is I hope exactly what your program does. I dod not know if the order of the 4 kinds of pointing/claiming is important.:
Hidden Text: Show
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;
naked_tuple_row(3);
if n_cand_set > progress then
goto restart;
naked_tuple_col(3);
if n_cand_set > progress then
goto restart;
naked_tuple_block(3);
if n_cand_set > progress then
goto restart;

hidden_tuple_row(3);
if n_cand_set > progress then
goto restart;
hidden_tuple_col(3);
if n_cand_set > progress then
goto restart;
hidden_tuple_block(3);
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;

The complete process takes more than 14000 lines and in this order even takes an hour to complete. I only add the output until there are less than 52000 candidates left. Hope that helps

Thanks for that. I'll have a look at it later. In the meantime, however, I have two questions:

1) If case 7 ends with 6079 naked singles, why doesn't the puzzle get fully solved in case 9? (pat seems to understand why this can happen, but I don't.)

2) Your program appears to be otherwise very fast, solving massive puzzles that yield to basic techniques in just a few seconds. So how is it possible that it spends 30 minutes running in case 6? Can you instrument the code somehow to see where the bulk of the time is spent?

Thanks,

Mike Metcalf

by **hkociemba** » Sat Sep 16, 2017 9:00 am

m_b_metcalf wrote:1) If case 7 ends with 6079 naked singles, why doesn't the puzzle get fully solved in case 9? (pat seems to understand why this can happen, but I don't.)

2) Your program appears to be otherwise very fast, solving massive puzzles that yield to basic techniques in just a few seconds. So how is it possible that it spends 30 minutes running in case 6? Can you instrument the code somehow to see where the bulk of the time is spent?

Q2: I suppose you mean case 7. I don't know the reason yet (but I also did not try to track this down yet). I just observe that while solving at the beginning as usual the verbose output scrolls down the screen very fast but after some time occasionally for seconds or even longer hangs. It seems that the program has tot test lots of cases without getting a positive result back. I will try to find out why this happens in case 7, where naked singles are not "cleared".

Q1: I am also puzzled by this fact and if Pat can explain it, it would be great. I tried to reproduce this with some 9x9 puzzles but in this case the puzzles in case 9 always got solved.

So I cannot answer any of your questions satisfactorily in the moment...

Edit: Concerning Q2 I see a bit clearer. 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. A similar argumentations works for the triplets.

The New Sudoku Players' Forum

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

re: 144-squared "hidden" triples

Re: re: 144-squared "hidden" triples

re: 144-squared "hidden" triples

re: 144-squared

Re: re: 144-squared triples

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

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

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

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

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

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

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

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

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