The New Sudoku Players' Forum

by **hkociemba** » Sat Sep 16, 2017 2:05 pm

I found a smaller and easy to solve fully symmetric 25x25 example which shows similar behaviour:

Code: Select all: . . . 24 9 . 19 11 . 12 18 . 7 . 3 13 . 14 10 . 20 22 . . . . . 14 13 10 . 2 . . 24 . 11 . 25 . 15 17 . 20 . 3 18 8 . . . 18 8 . . 20 . . 17 . . 14 . 4 . . 25 . . 19 . . 21 24 . 25 19 . . . 3 18 . . 7 22 . . . 20 24 . . 9 2 . . . 13 4 17 22 . . . . . . 4 . . 21 24 23 . . 16 . . . . . . 12 25 . . 5 16 7 15 6 3 18 . . 20 4 22 . . 2 9 12 11 . 21 10 . . 18 6 . 17 . 13 . . 22 4 21 10 23 1 24 16 19 . . 8 . 11 . 25 2 2 . . 25 . 7 . . . 16 . 3 . 18 . 23 . . . 21 . . . . 22 . . 20 . 13 24 21 . 1 . . 9 25 2 . . 18 . 15 6 7 . 5 . . 1 21 . 23 . . 11 9 . . . . 16 . . . . 20 13 . . 6 . 17 18 10 . . 21 . . 12 . . . . 16 8 5 . . . 4 1 . 22 15 . . 3 . 7 16 . 18 22 15 17 3 . 13 . . . 1 . 9 25 19 12 2 . 23 21 . 3 . . . 22 . 13 . 20 14 24 . . . 2 8 5 . . . 19 . . . 9 . 13 4 . 1 2 24 23 10 . 12 . . . 19 . 3 17 22 15 18 . 16 8 . 9 . . 11 . . 7 . . . . 17 6 3 . . . . 2 . . 13 . . 20 14 10 . 1 . . 9 24 . . . . 19 . . . . 15 4 . . 3 . 18 8 . 3 7 . 17 4 20 . 6 . . 13 1 14 . . 11 . 16 5 25 . 24 . . 6 . . . . 23 . . . 1 . 24 . 21 . 18 . . . 3 . . . . 11 21 9 . 2 . 16 . . 11 19 3 7 18 8 17 1 14 . . 10 . 20 . 22 6 . . 12 19 . 17 3 7 8 . . 15 22 6 . . 21 24 25 9 . 10 13 . . 7 17 . . . . . . 15 . . 1 10 13 . . 12 . . 16 . 25 . 9 24 13 23 . . . 11 25 . . 9 16 . . . 8 20 . . 14 4 . 17 . 3 7 . 25 2 . . 8 . . 12 . . 18 . 7 . . 13 . . 23 . . 22 20 . . . 22 20 14 . 23 . . 10 . 2 . 24 . 3 . . 6 . 8 16 19 . . . . . 5 8 . 17 18 . 3 4 . 20 . 14 9 . 2 11 . 21 23 . . . 310 givens, 1588 candidates(pencilmarks).

With using only pointing/claiming + hidden+naked pairs I get 310 givens, 315 candidates. All 315 empty cells have one candidate left.
When applying pointing/claiming + hidden+naked pairs + naked singles I get 360 givens, 1155 candidates!
If you cannot reproduce this result we should switch to this example for further investigations of the differences of our programs.
I try to find a 16x16 example now...

by **m_b_metcalf** » Sat Sep 16, 2017 2:32 pm

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

I will look at the 25x25 later. In the meantime, I had made the following test with my program:

In both case a ) and b) the program took less than a second before stopping.

HTH

Mike Metcalf

by **m_b_metcalf** » Sat Sep 16, 2017 2:59 pm

I've made a quick test on the 25x25:

Regards,

Mike Metcalf

by **hkociemba** » Sat Sep 16, 2017 4:02 pm

So we should try to get the same results with this example first. It does not need triplets at all to get solved. It can be completely solved using only hidden singles, pointing/claiming and naked+hidden pairs. I append the output for using only pointing/claiming and naked+hidden pairs which leaves the 315 candidates left (I think in the order you use, I deleted the triplets part):

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;

block_candidates_in_row;
block_candidates_in_col;
row_candidates_in_block;
col_candidates_in_block;
if n_cand_set > progress then
goto restart;

Exactly 1276 candidates are deleted here.

Edit: This takes just a fraction of a second. So though Mike made plausible that my explanation for the >30 min running time with the 144x144 was wrong I will not try to find the reason in the moment. Its more interesting why Mike gets a different result with the 25x25 and without singles.

by **hkociemba** » Sat Sep 16, 2017 9:33 pm

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.

Code: Select all: 9 13 . . . . 2 . . 6 . 8 . . . 5 . . 15 3 . 5 16 . 10 . . . 6 . . . 8 . 7 . . 4 9 . . 14 . . . 2 . . . . 11 . . 12 8 . 15 . 3 2 13 . 10 . . . . . . . 13 . . 8 7 14 . . 3 . . 16 . . 5 . . . 4 . . . . 6 . 10 . . 4 15 3 11 . . 12 9 . . . 14 . 7 . . . . . . . 9 . . . 1 2 . 4 15 7 . . 8 6 . . . . 5 . . . . 13 . . 4 . 9 13 . . 3 . . . . . 11 1 . . . . . . 16 . . 6 4 . 10 12 . . 8 11 5 . . . . . . . . 2 15 . . 6 . 5 . . . . 6 . 10 2 . . . . . . . . . . 1 . 14 . . . 15 . 4 . 12 . . . . 8 . . . . 15 16 7 . . 11 . . 1 4 . 9 13 2 . 3 11 . . . 12 7 . . 14 95 givens, 774 candidates(pencilmarks).

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.

by **m_b_metcalf** » Sun Sep 17, 2017 7:45 am

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

Mike Metcalf

by **Pat** » Sun Sep 17, 2017 7:55 am

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

amazing but right. took me a while to see how this happens

imagine a "naked" duo ={1,2}
AND one of these cells
is a "hidden single" 1 (in another house)

in case 8,
the "hidden single" is recognized,
taking it out of play

==> the "naked" duo VANISHES.

other

by **hkociemba** » Sun Sep 17, 2017 9:18 am

m_b_metcalf wrote:
hkociemba wrote:They are different: 733 candidates in both cases. Also, for a complete solution I find a naked triplet.

I am sure we are close to find the cause of the differences because this example is small enough. 25x25nosingles.txt is the debug output in the order you compute and here is the output of my solver for the complete solution without any triplets.

Hidden Text: Show

Or did you mean complete solving without using naked singles?
I hope (a part of) the differences do not result from a misunderstanding. A naked tuple of size n for example consists of n cells which contain n numbers but of course not each cell has to contain all n numbers. So in the case n=2 my program deals something like cell1_candidates= 4, 6 and cell2_candidates= 6 as a naked pair. Since usually naked singles are eliminated, in the case of a naked pair it is imaginable that you define a naked pair only as two cells which exactly have two candidates. This would of course exclude many cases I still deal when naked singles are not allowed.

by **m_b_metcalf** » Sun Sep 17, 2017 9:35 am

hkociemba wrote:Since usually naked singles are eliminated, in the case of a naked pair it is imaginable that you define a naked pair only as two cells which exactly have two candidates. This would of course exclude many cases I still deal when naked singles are not allowed.

Quite. In the normal order of processing in my program, I look for singles before pairs, so the case you cite I don't look for in the naked pair code as it cannot occur.

by **hkociemba** » Sun Sep 17, 2017 9:39 am

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

amazing but right. took me a while to see how this happens

imagine a "naked" duo ={1,2}
AND one of these cells
is a "hidden single" 1 (in another house)

in case 8,
the "hidden single" is recognized,
taking it out of play

==> the "naked" duo VANISHES.

the other cell is a "naked single" =2
-- which is un-recognized,
leaving us no way to exclude the 2

Thanks -but sorry, my fault - I meant not case 8 but case 9 and indeed wonder why we can delete much more candidates without applying *naked singles* than with applying naked singles. Hiddens singles are excluded in both cases...

by **hkociemba** » Sun Sep 17, 2017 10:05 am

m_b_metcalf wrote:
hkociemba wrote:Since usually naked singles are eliminated, in the case of a naked pair it is imaginable that you define a naked pair only as two cells which exactly have two candidates. This would of course exclude many cases I still deal when naked singles are not allowed.

Quite. In the normal order of processing in my program, I look for singles before pairs, so the case you cite I don't look for in the naked pair code as it cannot occur.

So you think all differences can be explained with that? Then it really was a big misunderstanding...

by **Pat** » Sun Sep 17, 2017 10:19 am

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.

other

in that cell

by **m_b_metcalf** » Sun Sep 17, 2017 10:26 am

hkociemba wrote:
m_b_metcalf wrote:Quite. In the normal order of processing in my program, I look for singles before pairs, so the case you cite I don't look for in the naked pair code as it cannot occur.

So you think all differences can be explained with that? Then it really was a big misunderstanding...

I don't think that explains everything as even with naked singles switched on I have many more candidates left than you. And there's still the timing problem to clear up. Note that subsuming some naked singles into naked pairs would not allow use of that code as a filter in the Patterns Game.

I'll try to find time to look at your solution sequence later.

Regards,

Mike Metcalf

by **hkociemba** » Sun Sep 17, 2017 11:09 am

m_b_metcalf wrote:
hkociemba wrote:So you think all differences can be explained with that? Then it really was a big misunderstanding...

I don't think that explains everything as even with naked singles switched on I have many more candidates left than you.

This may be caused by the same argumentation concerning hidden pairs. If number 4 has two possibilites in a house and number 5 has only one, my code considers this as a hidden pair...
Only if you need some triplet to solve this puzzle (while using all other lower rated methods) there is definitely something different. Try to find some time later to patch my code to exclude these potentially hidden or naked singles in the n-tuples.

by **m_b_metcalf** » Sun Sep 17, 2017 1:03 pm

hkociemba wrote:Only if you need some triplet to solve this puzzle (while using all other lower rated methods) there is definitely something different. Try to find some time later to patch my code to exclude these potentially hidden or naked singles in the n-tuples.

If I alter the order of processing I don't need triples (my usual order reflects the SE ratings' order).

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

The New Sudoku Players' Forum

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)

Re:

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)