Subset Counting

Advanced methods and approaches for solving Sudoku puzzles

Postby flip » Sun Mar 12, 2006 5:20 pm

I think I understand now that aeb did not say that nice loops are a special case of subset counting, but that they are a type of counting arguments.
As requested in my first post, it would be nice if he'll explain this with reference to the nice loop given (edited: in a new thread?).
flip
 
Posts: 17
Joined: 08 January 2006

Postby aeb » Sun Mar 12, 2006 5:56 pm

flip wrote:
Code: Select all
[r9c5]=2=[r9c1]=5=[r1c1]=7=[r1c9]=4=[r9c9]-4-[r9c5] => [r9c5]<>4

 ^57  9   45    2   6   3     8   1   ^47
  6   12  14    7   5   8     9   24   3
  27  8   3     9   1   4     27  6    5
  3   4   2     6   9   5     1   78   78
  18  5   7     3   28  12    4   9    6
  18  6   9     4   78  17    5   3    2
  4   12  15    8   3   27    6   57   9
  9   3   8     5   47  6     27  247  1
 ^25  7   6     1   24  9     3   458 ^48

Can you also please elaborate, using this bivalue loop as example...

This thread was mainly meant to show that ALS work can be simplified. The type of chain you have here is of a rather different category, just like ravel already remarked: since you start with [r9c5]=2=[r9c1] one has to use all of the row, not just the corners.
Since you ask, let me suggest a possible approach (that really belongs in a different thread). The reasoning will use lower bounds instead of upper bounds. The counting version says that 24578 at the four corners each have minimum multiplicity 1, and four corners is not enough to place five digits. Why at least 1? For digit 2 the bottom row - assuming (9,5)4 - shows that there is a 2 in our set. For digit 4 the last column shows that there is a 4 in the set. For digit 5 the first column shows that there is a 5 in the set. For digit 7 the first row shows that there is a 7 in the set. And finally, for digit 8 - assuming (9,5)4 - cell (9,9) shows that there is an 8 in the set.
This achieves the goal: make the elimination by counting instead of by following a chain.
aeb
 
Posts: 83
Joined: 29 January 2006

Postby flip » Sun Mar 12, 2006 6:10 pm

aeb wrote:The type of chain you have here is of a rather different category ... Since you ask, let me suggest a possible approach (that really belongs in a different thread) ...

Thanks, as you can see from my edited post just above this, I came to this conclusion belatedly (you must have missed my post while you were composing yours)
flip
 
Posts: 17
Joined: 08 January 2006

Postby aeb » Sun Mar 12, 2006 7:29 pm

ravel wrote:I understand your way of looking at ALS, where you only need one set to make the conclusion. Once the set is found, it is an elegant way for showing, why an elimination can be made safely. Do you have an example, where you can make an elimination, which cannot be done with an (xz- or xy-) ALS also ?

I am afraid I don't know yet what xz- and xy-ALS are. I just noticed that each time people here invoke ALS, I would have used a simpler subset counting.
ravel wrote:And are you finding the set "as a whole" or are you putting it together from (2 or more) almost locked sets?
As a whole.
ravel wrote:So please can you show an x-wing elimination with subset counting and tell me, if a comprehensive forcing chain can be expressed with subset counting. For the latter i took an arbitrary sample:
Code: Select all
 3 5678  57 | 4  19*  26  | 27*  289  157#
17  567   4 | 8  19*  26  |  3    29* 157
 2   18   9 | 3   5    7  |  6    18    4 

r1c9=7 => r1c7=2 => r2c8=9 => r2c5=1 => r1c5=9 => r1c9=1

Earlier today I answered flip on a similar question. This really belongs in a different thread - such things can be done by counting arguments, but not by the type of subset counting shown in the example. The chain is beautifully short, the counting reasoning is longer since both lower and upper bounds are involved. Roughly: assuming (1,9)7 one finds for the entire subset 129 with max multiplicities 112, and for row 1 min multiplicities 110, leaving max multiplicities 002 for row 2, impossible.
aeb
 
Posts: 83
Joined: 29 January 2006

Previous

Return to Advanced solving techniques

cron