Sharks - a Truth Balancing Method

Advanced methods and approaches for solving Sudoku puzzles

Sharks - a Truth Balancing Method

Postby David P Bird » Sun Apr 01, 2012 11:37 am

New readers: the first two pages of this thread amount to "thinking out loud" while the idea was developed. Unless this is of interest, jump to <this restart > where everything has been re-presented more consistently.

To avoid confusion with champagne's possible multi-fish variants, I'm going to temporarily call my simplified truth balancing routine a Shark (being a fish eater). It may be possible to reconcile the two terms later, but at this stage I just don't know. In the simplest cases Multi-Fish and Sharks will arrive at the same exclusions but using different approaches. However the Shark pattern location system also allows more complex scenarios to be identified, when it remains to be seen if they are equivalent or not. Anyway, opening a new thread give me the chance to present a re-working of the truth balancing method I described in champagne's bi-bi patterns thread (where I felt it was already off-topic).

It appears that both our approaches will handle some SK loop situations when they may provide some extra exclusions. In many cases these would be found using locked set eliminations after the SK loop eliminations have been made, but I dont this will always be true. So it also remains to be seen if how extensive the overlaps are.

This is how the re-worked system goes:

The Shark method operates on a promising subset of digits.
Different flags are used to identify cells (including those with givens)
a) that must contain a member digit (#)
b) that can't contain a member (x).
A total of 9 rows and columns are selected with the objective of maximising the number of (#) cells that are covered.
A secondary objective to aid row and column selection is to maximise the number of (x) cells in the uncovered cells.

It is easy to show that the numbers of truths contained in the sets of doubly covered cells (red) and uncovered cells (blue) will be equal.
Consequently if the number of available cells in the in the blue set matches the number of (#) cells in the red set, the blue cells must all contain member digits and any other cells in the red set can't contain members.

There may be more than one way rows and columns can be selected to achieve this balance and each one will provide slightly different eliminations.

At this stage of the procedure Sharks and Multi-Fish will provide identical exclusions. However the Shark approach can be extended to consider cases when an immediate truth balance has not been reached:

On inspection it will be found that not all the seemingly available options in these sets can be realised.
In the blue set the cells available to hold a truth in a house be limited because there are known truths in external cells.
In the red set a house be forced to contain an extra truth because there are insufficient openings available in the external cells.

The adjustments to be made need to be considered by house type (rows, columns or boxes) and the most limiting result used for each set.
If these adjustments achieve a truth balance, eliminations can only be made in those houses where no adjustment has been made. This is because in the adjusted houses the location of the target cells is uncertain.

.......89.5.1.....6....31...7...16......9..2...8.....4..4.2....7..5..3...6...7... 3329 eleven 991 11.20 1.20 1.20 713 B4B
Code: Select all
                   v               v                      v       v     
 *-----------------------*-----------------------*----------------------*
>| 1234    1234   1237   | 2467   4567    2456   | 2457   8    # 9    # |<
>| 2489  # 5x     279    | 1x     478     2489 # | 247    36x    36x    |<
 | 6x      2489 # 279    | 24789  4578    3x     | 1x     457    257    |
 *-----------------------*-----------------------*----------------------*
 | 23459   7x     2359   | 2348   3458    1x     | 6x     359    358    |
>| 1345    134    6x     | 3478   9    #  458    | 578    2    # 13578  |<
>| 12359   1239   8    # | 2367   3567x   256    | 579    13579  4    # |<
 *-----------------------*-----------------------*----------------------*
>| 13589   1389   4    # | 3689   2    #  689    | 5789   15679  15678  |<
 | 7x      1289   129    | 5      1468    4689   | 3x     1469   1268   |
 | 123589  6x     12359  | 3489   1348    7x     | 24589  1459   1258   |
 *-----------------------*-----------------------*----------------------*
                   ^               ^                       ^      ^

In this puzzle from champagne's "nothing special found" set the digit set is [2489]
The red set (covered twice) contains 8 givens and the blue set (uncovered) has 9 available cells, so there is no immediate truth balance.
However, in row 2 there are only three cells that can hold a truth that aren’t covered twice which requires r2c35 to hold at least one truth.
This produces a truth balance so that in the doubly covered set all non-member digits are false and the uncovered cells in rows14567 all the member digits are false giving 18 eliminations in all.
Because the adjustment has been made in row 2, which of r2c35 can't hold a member digit is uncertain and no elimination is possible in these cells. However it's apparent that as 7 is the only non-member they hold it must be true in one of them.

It's also possible that a member digit must be true in a cell external to the doubly covered set because it is part of a locked set containing non-member digits. I believe champagne's method allows that to be investigated which separates the systems as they stand now.

Champagne, it would be interesting to see how your revised solver handles this problem now, and how much difference there is between us. From my limited trials your 2x2 multi-fish all coincide with SK loops as far as I can see. Is that true? Shark handles the ones I've tired so far and I expect to post more on them later.

ronk, is it possible to produce a truth and link sets diagram to represent the eliminations in my example?

[Edit] Selection rules for rows and columns corrected in blue, and row selections inverted in the figure – fragments of two rival marking systems I had been testing got mixed together. Other minor improvements made.
[Edit 2 Ajustment system extended form rows & columns to rows, columns & boxes - shown in green.
Last edited by David P Bird on Fri Apr 27, 2012 2:56 pm, edited 3 times in total.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Sharks - a Truth Balancing Method

Postby champagne » Sun Apr 01, 2012 1:54 pm

David P Bird wrote:
Champagne, it would be interesting to see how your revised solver handles this problem now, and how much difference there is between us. From my limited trials your 2x2 multi-fish all coincide with SK loops as far as I can see. Is that true? Shark handles the ones I've tired so far and I expect to post more on them later.



going deeper in that post will take time.

I can give a quick answer to one of your question. You can check it using the file "03 TT" in the data base

From the stats in that file

1418 puzzles have both a SK loop and a 2x2 rank 0 logic

553 have no SK loop but the 2x2 rank 0 (or nearly rank 0) logic

If you have difficulties to use the "03 tt" file, I can post some examples



Regarding the first point, I did not change the solver after ronk cracked that puzzle and the new solver is currently in development in another area.

champagne
champagne
2017 Supporter
 
Posts: 5625
Joined: 02 August 2007
Location: France Brittany

Re: Sharks - a Truth Balancing Method

Postby ronk » Sun Apr 01, 2012 1:58 pm

David P Bird wrote:ronk, is it possible to produce a truth and link sets diagram to represent the eliminations in my example?

I'm still trying to follow your post. In the mean time, here's a 4-digit-fish with 20 exclusions that I see.

____Image

Code: Select all
     20 Truths = {2R23489 4R23489 8R23489 9R23489}
     20 Links = {2c39 4c58 8c59 9c38 249n1 38n2 349n4 28n6 29n7}
     20 Eliminations --> r249c1<>3, r9c17<>5, r49c4<>3, r28c6<>6, r67c8<>9, r57c9<>8, r1c3<>2,
     r1c5<>4, r2c7<>7, r3c4<>7, r4c1<>5, r8c2<>1, r9c1<>1

The 20 base sets in rows are covered by 8 column sets and 12 cells.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sharks - a Truth Balancing Method

Postby ronk » Sun Apr 01, 2012 4:21 pm

champagne wrote:From the stats in that file
1418 puzzles have both a SK loop and a 2x2 rank 0 logic
553 have no SK loop but the 2x2 rank 0 (or nearly rank 0) logic

My definition for a "2x2" is a piece of lumber with a 2" by 2" cross-section. What's yours?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sharks - a Truth Balancing Method

Postby David P Bird » Sun Apr 01, 2012 5:04 pm

ronk, many thanks for your diagram. It alerted me to the fact I had mis-described the Shark row & column selection rules. I have now edited the OP and I apologise the confusion I created.

Hats off to you. Your row & column selections get the different sets to balance without making any adjustments and I'm kicking myself that I missed them. (I was just happy to have found an example to illustrate that aspect of the procedure.)


champagne, thanks for the feedback. I'll do some exploring.

DPB
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Sharks - a Truth Balancing Method

Postby champagne » Sun Apr 01, 2012 5:05 pm

ronk wrote:
champagne wrote:From the stats in that file
1418 puzzles have both a SK loop and a 2x2 rank 0 logic
553 have no SK loop but the 2x2 rank 0 (or nearly rank 0) logic

My definition for a "2x2" is a piece of lumber with a 2" by 2" cross-section. What's yours?



David uses it as a short for a rectangle rank 0 or nearly rank 0 SLG made as a base of 2 rows and 2 columns

here is an example coming from my recent post in the "bi bi" thread

Code: Select all
    X     7+    7+    |67+   67+   7+    |6+    6+    X     
    2+    7+    X     |X     1267+ 127+  |6+    X     1+   
    2+    X     2+    |12+   12+   12+   |X     1+    1+   

    26+   17+   1267+ |X     X     127+  |26+   X     17+   
    2+    17+   127+  |X     127+  X     |2+    127+  17+   
    26+   17+   X     |127+  X     127+  |26+   1267+ 17+   

    6+    X     6+    |67+   67+   7+    |X     7+    7+   
    X     1+    1+    |12+   12+   12+   |2+    2+    X     
    6+    1+    X     |1267+ X     127+  |2+    X     7+   


Code: Select all
    sets
    1267R2 1267R9 1267C3 1267C8
    linksets
    27B1 16B3 16B7 27B9 r2c5 r2c6 r4c3 r5c3 r5c8 r6c8 r9c4 r9c6



champagne
champagne
2017 Supporter
 
Posts: 5625
Joined: 02 August 2007
Location: France Brittany

2-row + 2-column base sets that aren't an sk-loop

Postby ronk » Sun Apr 01, 2012 6:47 pm

champagne wrote:
ronk wrote:
champagne wrote:From the stats in that file
1418 puzzles have both a SK loop and a 2x2 rank 0 logic
553 have no SK loop but the 2x2 rank 0 (or nearly rank 0) logic
My definition for a "2x2" is a piece of lumber with a 2" by 2" cross-section. What's yours?
David uses it as a short for a rectangle rank 0 or nearly rank 0 SLG made as a base of 2 rows and 2 columns

It can't be David P Bird doing that. He complains when others use 3-letter acronyms without an explanation.

champagne wrote:here is an example coming from my recent post in the "bi bi" thread

This example is the well-known "sk-loop" or "hidden-pair-loop". I'd like to look at a 2-row & 2-column base set that is not an sk-loop. In your "03 TT something special" file, would this be any puzzle with a "G3", "G13", "G23" or "G123" tag, but without the "K" tag?

BTW I find 738 of those, not the 553 you stated above. Does this mean 185 have more than 2 rows and/or more than 2 columns?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: 2-row + 2-column base sets that aren't an sk-loop

Postby ronk » Sun Apr 01, 2012 7:41 pm

ronk wrote:I'd like to look at a 2-row & 2-column base set that is not an sk-loop. In your "03 TT something special" file, would this be any puzzle with a "G3", "G13", "G23" or "G123" tag, but without the "K" tag?

Examining one of these, I see one variant of an "almost sk-loop.". In this particular case, if r9c5 held a clue other than one of sk-digits <1367>, it would be an sk-loop. Without a clue at r9c5, extra truths (a.k.a. base sets, strong inference sets) provided by r456c2 balance the truth/link count, again resulting in 0-rank logic.

Code: Select all
.....67...5.1...3...9.2...42..........8.4...29.46..........7.6....3..1..8.......5 ;1426;elev;318;;;;;G3

____Image

Code: Select all
     18 Truths = {1367R3 1367R9 137C5 1367C9 456N2}
     18 Links = {1367c2 3n1 9n3 469n5 46n9 1b38 3b29 6b3 7b29}
     20 Eliminations --> r4c5<>589, r1c28<>1, r6c59<>8, r7c27<>3, r8c28<>7, r4c9<>89, r1c2<>3,
     r2c7<>6, r6c5<>5, r7c2<>1, r8c2<>6, r9c3<>2, r9c5<>9
Last edited by ronk on Sun Apr 01, 2012 10:44 pm, edited 2 times in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sharks - a Truth Balancing Method

Postby David P Bird » Sun Apr 01, 2012 10:30 pm

ronk (regarding 2x2 term) wrote:It can't be David P Bird doing that. He complains when others use 3-letter acronyms without an explanation.

LOL! Yes that's true. It took me some time at first to realise what champagne's term meant, but he's not an English speaker like what we is.

Here's an example to compare the eliminations from an SK loop with those from two alternative Sharks

2.......6.5..8..1...4...9...7.3.1......82.......7.5.3...9...4...8..1..5.6.......2;10;tax;tarek-ultra-0203
Code: Select all
           A               A             A               A       
 *----------------------*----------------------*----------------------*
 | 2    # 139    1378x  | 1459   34579  3479   | 3578x  478    6    # |
A| 379    5x     367    | 2469 # 8x     234679 | 237    1x     347    |B
 | 1378x  136    4   #  | 1256   3567   2367   | 9    # 278    3578x  |
 *----------------------*----------------------*----------------------*
A| 4589   7x     2568   | 3x     469  # 1x     | 2568   24689  4589   |B
A| 13459  13469  1356   | 8x     2    # 469  # | 1567   4679   14579  |
A| 1489   12469  1268   | 7x     469  # 5x     | 1268   3x     1489   |B
 *----------------------*----------------------*----------------------*
 | 1357x  123    9   #  | 256    3567   23678  | 4    # 678    1378x  |
A| 347    8x     237    | 2469 # 1x     234679 | 367    5x     379    |B
 | 6    # 134    1357x  | 459    34579  34789  | 1378x  789    2    # |
 *----------------------*----------------------*----------------------*
           B               B       B     B               B

A: (2469)Shark:r24568,c2468
Simple balance: Cells Covered twice Max(Available Cells)=9, Cells Not Covered Min(Truths) = 8
Adjusted count in c5 Cells Covered twice Max(Available Cells)=9, Cells Not Covered Min(Truths) = 9

Cells covered twice r2c6 <> 37, r5c2 <> 13, r6c2 <> 1, r4c8 <> 8, r5c8 <> 7, r8c6 <> 37 (9 Exclusions)
Cells not covered (2469)r1379c5 is a Weak Inference Set

B: (2469)Shark:r2468,c24568
Simple balance: Cells Covered twice Max(Available Cells)=8, Cells Not Covered Min(Truths) = 8
Cells covered twice r2c6 <> 37, r6c2 <> 1, r4c8 <> 8, r8c6 <> 37 (6 Exclusions)
Cells not covered r5c19 <> 49, r5c37 <> 6 (6 Exclusions)

C: SK Loop: (13)c2,(24)b7,(37)r8,(69)b9,(78)c8,(24)b3,(37)r2,(69)b1
r5c2 <> 13, r6c2 <> 1, r8c6 <> 37, r4c8 <> 8, r5c8 <> 7, r2c6 <> 37 (9 Exclusions)
(469)LockedSet:r5c258 r5c19 <> 49, r5c37 <> 6 (6 Exclusions)

As can be appreciated, these sharks are somewhat different from a multi-fish using two rows and two columns plus the boxes containing the intersects.

[Added] To expand on the adjustment made in Shark A: A simple count shows a misbalance, but in column 5 it's clear that the uncovered set must contain at least one truth as the are no more openings in the other cells. Consequently no eliminations can be made in this column, only a derived inference that the member digits form a Weak Inference Set in r1379c5.

It takes both sharks to produce the same eliminations as the SK loop. However in B: the eliminations in the uncovered cell sets aren't produced by the SK loop, but follow on from a locked set being formed.

ronk, your 'almost SK loop' looks interesting but I haven't had time to digest it yet.

[Edit Major edits in blue made to correct error found by ronk, wording elsewhere changed accordingly.]
Last edited by David P Bird on Tue Apr 03, 2012 8:41 am, edited 1 time in total.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Sharks - a Truth Balancing Method

Postby ronk » Mon Apr 02, 2012 2:28 am

David P Bird wrote:A: (2469)Shark:r24568,c2468
Cells covered twice r2c6 <> 37, r5c2 <> 13, r6c2 <> 1, r4c8 <> 8, r5c8 <> 7, r8c6 <> 37 (9 Exclusions)
Cells not covered r19c5 <> 479, r37c5 <> 6, (8 Exclusions)
...
the eliminations in the uncovered cell sets aren't produced by the SK loop.

Hmm, I see no valid basis for "eliminations in the uncovered cell sets."

David P Bird wrote:
ronk (regarding 2x2 term) wrote:It can't be David P Bird doing that. He complains when others use 3-letter acronyms without an explanation.
LOL! Yes that's true. It took me some time at first to realise what champagne's term meant, but he's not an English speaker like what we is.

To what champagne term do you refer? His "TT"?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: 2-row + 2-column base sets that aren't an sk-loop

Postby champagne » Mon Apr 02, 2012 2:52 am

ronk wrote:It can't be David P Bird doing that. He complains when others use 3-letter acronyms without an explanation.


could be me

ronk wrote:
champagne wrote:here is an example coming from my recent post in the "bi bi" thread

This example is the well-known "sk-loop" or "hidden-pair-loop". I'd like to look at a 2-row & 2-column base set that is not an sk-loop. In your "03 TT something special" file, would this be any puzzle with a "G3", "G13", "G23" or "G123" tag, but without the "K" tag?

BTW I find 738 of those, not the 553 you stated above. Does this mean 185 have more than 2 rows and/or more than 2 columns?


I see through your example that you got the answer. No surprise if such puzzles have "close to SK loop" patterns.

Regarding the 738 / 533 deviation, I guess I did not make the appropriate request in Access.

Just a warning regarding these flags showing "exotic patterns". This comes from several runs using parameters and from additional tasks to fill in the results in the data base.
There is room here for human errors and the entire file should be rerun in once, what I intend to do later with a revised code performing better.

champagne

EDIT : I compared ronk's soltuion for puzzle 1426 to the proposal of the solver. We have exactly the same SLG.
champagne
2017 Supporter
 
Posts: 5625
Joined: 02 August 2007
Location: France Brittany

Re: Sharks - a Truth Balancing Method

Postby David P Bird » Mon Apr 02, 2012 7:06 pm

ronk wrote: Hmm, I see no valid basis for "eliminations in the uncovered cell sets".

I've clearly done a bad writing job. My previous posts were made midway through changing my spreadsheet from one colouring scheme for Sharks to another and I know I blundered at the points where I made the later edits. I'll re-check that no other slip-ups have survived.

In Sharks the set of cells that are covered twice must contain the same number of true member digits as the set of cells that are completely uncovered. The upper limit on how many truths there will be in each of these sets will be set by the one with the fewest available cells, and the lower limit will be set by the one that holds the highest minimum number of truths. When these are equal we know the number of true members in both sets. One can have no more true members, and the other can have no more cells containing non-members.

For that puzzle there were two ways the rows and columns could be selected 'A' and 'B'. I showed the 'A' rows and columns above and to the left of the grid, and the 'B' rows and columns below and to the right of it.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Sharks - a Truth Balancing Method

Postby ronk » Mon Apr 02, 2012 10:34 pm

David P Bird wrote:
ronk wrote: Hmm, I see no valid basis for "eliminations in the uncovered cell sets".
I've clearly done a bad writing job ...

Since ...
you wrote:A: (2469)Shark:r24568,c2468
Cells covered twice r2c6 <> 37, r5c2 <> 13, r6c2 <> 1, r4c8 <> 8, r5c8 <> 7, r8c6 <> 37 (9 Exclusions)
Cells not covered r19c5 <> 479, r37c5 <> 6, (8 Exclusions)

... and r1c5=9 is part of the solution, it's difficult to become a believer. ;)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Sharks - a Truth Balancing Method

Postby David P Bird » Tue Apr 03, 2012 7:10 am

ronk wrote:Since ...
[dpb] wrote:A: (2469)Shark:r24568,c2468
Cells covered twice r2c6 <> 37, r5c2 <> 13, r6c2 <> 1, r4c8 <> 8, r5c8 <> 7, r8c6 <> 37 (9 Exclusions)
Cells not covered r19c5 <> 479, r37c5 <> 6, (8 Exclusions)

... and r1c5=9 is part of the solution, it's difficult to become a believer. ;)

Right ronk, I've found the problem (I suspect my spreadsheet colouring engine had a bit of dirt in the carburettor at the time.)

Shark B: is fine as no adjustments are needed to the minimum(true cells) and maximum(available cells) between the two sets to reach a balance as a simple count gives 8 for each.

In Shark A: the simple count gives minimum(true cells)=8 for the uncovered set and maximum(available cells)=9 in the doubly covered set and there is no immediate balance. In column 5 however there is an adjustment that can be made as one more truth is needed which must be in one of the uncovered cells. This raises the minimum(true cells) to 9 and so achieves a balance.

As described in the OP, in houses where the counts have been adjusted no eliminations can be made because the locations of the target cells aren't known for sure. In this case we know that only one of the four available cells can hold a member digit, but which don't know which one it is. So the eliminations in the other houses are good, but in column 5 we can only infer that the member digits form a weak inference set in r1379c5.
(Thanks for keeping me on my toes; I'll edit that post.)

I also looked at your Almost SK Loop but as you used so many box constraints, my simple row and column methods can't penetrate it.
David P Bird
2010 Supporter
 
Posts: 957
Joined: 16 September 2008
Location: Middle England

Re: Sharks - a Truth Balancing Method

Postby ronk » Tue Apr 03, 2012 11:00 am

David P Bird wrote:... in houses where the counts have been adjusted no eliminations can be made because the locations of the target cells aren't known for sure. ... in column 5 we can only infer that the member digits form a weak inference set in r1379c5.
(Thanks for keeping me on my toes; I'll edit that post.)

In summary then, presumably for puzzle ...

Code: Select all
2.......6.5..8..1...4...9...7.3.1......82.......7.5.3...9...4...8..1..5.6.......2 ;10;tax;tarek-ultra-0203

... the two sharks A and B (together 38 strong inference sets) provide the same exclusions as an sk-loop (16 strong + 16 weak inference sets) followed by a naked triple (3 strong inference sets), i.e., equal on the exclusion count and almost equal on the total inference count.

Do you have an example where a basic follow-on move to the sk-loop doesn't cause a match of the exclusions :?:

David P Bird wrote:I also looked at your Almost SK Loop but as you used so many box constraints, my simple row and column methods can't penetrate it.

Not sure to which box constraints you refer, but maybe this logic set will help:

Code: Select all
000006700050100030009020004200000000008040002904600000000007060000300100800000005

19 Truths = {1367C1359 456N2}
19 Links = {1r17 3r17 6r28 7r28 3n1 9n3 469n5 46n9 1367b4}
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques