Multi-Value Chain Operands

Advanced methods and approaches for solving Sudoku puzzles

Multi-Value Chain Operands

Postby daj95376 » Wed Aug 31, 2011 6:18 am

I'm tired and probably should wait until morning to create this post. Ignoring my better judgement, here goes.

After several failed attempts to incorporate multi-value logic into my chain/loop routine, I'm in the middle of another try to make sense out of chaos. Consider the following scenario:

Code: Select all
 (23=1)r2c2 - ... = (9)r8c9 - (9=234)r2c789 - loop
 +-----------------------------------------------+
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .  123  .   |   .   .   .   |  234 234 2349 |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   X9  |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 +-----------------------------------------------+

Convincing myself that a valid loop existed was the first hurdle that I overcame.

The term (234)r2c789 involves three values in three cells. Thus, each value can be considered as being assigned to one of the cells. The term (23)r2c2 involves two values in one cell. Thus, an OR relationship exists and neither value can be considered as being assigned to the cell. I'm unable to derive any eliminations in the weak link between (234)r2c789 and (23)r2c2. Is this correct?

Any insight on handling multi-value logic would be appreciated!!!

Regards, Danny A. Jones
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Multi-Value Chain Operands

Postby champagne » Wed Aug 31, 2011 6:45 am

daj95376 wrote:Any insight on handling multi-value logic would be appreciated!!!

Regards, Danny A. Jones


When my solver detects such a situation, it just creates an equivalence

1r2c2 == 9r8c9

so both share the same tag in next steps.

regards

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

Re: Multi-Value Chain Operands

Postby ronk » Wed Aug 31, 2011 11:18 am

daj95376 wrote:The term (234)r2c789 involves three values in three cells. Thus, each value can be considered as being assigned to one of the cells. The term (23)r2c2 involves two values in one cell. Thus, an OR relationship exists and neither value can be considered as being assigned to the cell. I'm unable to derive any eliminations in the weak link between (234)r2c789 and (23)r2c2. Is this correct?

Try thinking about it as a larger ALS. Were the ALS (12349)r2789 part of a continuous loop, eliminations of digits (234) elsewhere in r2 would be valid.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Multi-Value Chain Operands

Postby daj95376 » Wed Aug 31, 2011 2:42 pm

Okay, I don't allow (23=1)r2c2 as an entry in my SI table. Thanks!!!

Code: Select all
 (2349=1)r2c2789 - ... = (9)r8c9 - (9=1234)r2c2789 - loop
 +-----------------------------------------------+
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .  123  .   |   .   .   .   |  234 234 2349 |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   X9  |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 +-----------------------------------------------+

All I need to do is allow Naked Subsets where a candidate can occur only once. Hmmm!

Regards, Danny
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Multi-Value Chain Operands

Postby daj95376 » Fri Sep 02, 2011 8:59 am

New scenario ... same old headache.

Code: Select all
 ANS(123=4)r13c3,r2c1 - ... - ANS(3=156)r8c2,r79c3 - loop
 +-----------------------------------------------+
 |   .   .  12   |   .   .   .   |   .   .   .   |
 |  234  .   .   |   .   .   .   |   .   .   .   |
 |   .   .  13   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .  15   |   .   .   .   |   .   .   .   |
 |   .  356  .   |   .   .   .   |   .   .   .   |
 |   .   .  16   |   .   .   .   |   .   .   .   |
 +-----------------------------------------------+

In order to determine that a loop exists, I must verify that the 1s in ALS(1234) are peers of the 1s in ALS(1356). Right?

I must also perform equivalent testing at all weak links. Right?
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Multi-Value Chain Operands

Postby champagne » Fri Sep 02, 2011 9:51 am

daj95376 wrote:New scenario ... same old headache.

Code: Select all
 ANS(123=4)r13c3,r2c1 - ... - ANS(3=156)r8c2,r79c3 - loop
 +-----------------------------------------------+
 |   .   .  12   |   .   .   .   |   .   .   .   |
 |  234  .   .   |   .   .   .   |   .   .   .   |
 |   .   .  13   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |   .   .   .   |   .   .   .   |   .   .   .   |
 |---------------+---------------+---------------|
 |   .   .  15   |   .   .   .   |   .   .   .   |
 |   .  356  .   |   .   .   .   |   .   .   .   |
 |   .   .  16   |   .   .   .   |   .   .   .   |
 +-----------------------------------------------+

In order to determine that a loop exists, I must verify that the 1s in ALS(1234) are peers of the 1s in ALS(1356). Right?

I must also perform equivalent testing at all weak links. Right?


I hope I don't misunderstand your PM.

Here if I am right you show easily

4r2c1 true => 3r8c2 false
4r2c1 false => 3r8c2 true

3r8c2 true => 4r2c1 false
3r8c2 false => 4r2c1 true

so 3r8c2 = 4r2c1 is a strong link
not directly an answer to your point but no need to establish first that the 2 groups of "1" are a bi value.

my solver would not detect that, but in case, it would keep in memory the strong link.

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

Re: Multi-Value Chain Operands

Postby daj95376 » Fri Sep 02, 2011 5:10 pm

champagne wrote:I hope I don't misunderstand your PM.

Here if I am right you show easily

4r2c1 true => 3r8c2 false
4r2c1 false => 3r8c2 true

3r8c2 true => 4r2c1 false
3r8c2 false => 4r2c1 true

so 3r8c2 = 4r2c1 is a strong link
not directly an answer to your point but no need to establish first that the 2 groups of "1" are a bi value.

Your statements in blue can be derived without the loop information. I'm pretty sure that your statements in green don't exist without the loop information.

In any event, I'm still stuck looking for an easier way to deal with the loop scenario than digging into the candidate locations for every value common to the ANS() expressions.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Multi-Value Chain Operands

Postby champagne » Fri Sep 02, 2011 5:39 pm

daj95376 wrote:
champagne wrote:I hope I don't misunderstand your PM.

Here if I am right you show easily

4r2c1 true => 3r8c2 false
4r2c1 false => 3r8c2 true

3r8c2 true => 4r2c1 false
3r8c2 false => 4r2c1 true

so 3r8c2 = 4r2c1 is a strong link
not directly an answer to your point but no need to establish first that the 2 groups of "1" are a bi value.

Your statements in blue can be derived without the loop information. I'm pretty sure that your statements in green don't exist without the loop information.

In any event, I'm still stuck looking for an easier way to deal with the loop scenario than digging into the candidate locations for every value common to the ANS() expressions.


As I said, I not sure I understood properly your PM, but

4 r2c1 false => 23r2c1 true => 23r13c3 false => 1 r13c1 true => 1r79c3 false => 56r79c1 true => 3r8c2 true

Again, this is not the kind of thing my solver sees

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

Re: Multi-Value Chain Operands

Postby daj95376 » Wed Sep 21, 2011 1:17 am

I don't have the full logic implemented from my previous scenario, but I do have a partial ANS() implementation that located the following eliminations:

Code: Select all
 +------------------------------------------------------------------------+
 |  1      259    259    |  589    358     7      |  6      359    4      |
 |  4      8      6      |  259    1235    125    |  7      1359   59     |
 |  59     7      3      |  569    156     4      |  2      159    8      |
 |-----------------------+------------------------+-----------------------|
 |  2589   2459   7      |  3      2458   b259    |  1      59     6      |
 | a259+8  24569 a259+8  | b26+8   1468-2  1-259  |  3      7     a59     |
 |  3      569    1      |  7     b56     b59     |  4      8      2      |
 |-----------------------+------------------------+-----------------------|
 |  7      29     4      |  1      29      8      |  5      6      3      |
 |  258    3      258    |  25     7       6      |  9      4      1      |
 |  6      1      59     |  4      59      3      |  8      2      7      |
 +------------------------------------------------------------------------+
 # 73 eliminations remain

 (259=8)r5c9+13 - (8=2569)r5c4+r4c6,r6c56  =>  r5c5<>2; r5c6<>259

Given the effort and number of attempts to upgrade my solver, I consider this a victory even though the execution time takes way longer.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: Multi-Value Chain Operands

Postby ronk » Wed Sep 21, 2011 3:15 pm

daj95376 wrote:I don't have the full logic implemented from my previous scenario, but I do have a partial ANS() implementation that located the following eliminations:
...
(259=8)r5c9+13 - (8=2569)r5c4+r4c6,r6c56 => r5c5<>2; r5c6<>259
...
Given the effort and number of attempts to upgrade my solver, I consider this a victory even though the execution time takes way longer.

Congratulations. This particular pattern may be viewed as an ALS-xz with multiple values possible for the 'z'. Maybe its an ALS-xzzz. :)

And r5c4 can be part of either the left or right set with 'x' being either <6> or <8>, respectively.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: Multi-Value Chain Operands

Postby daj95376 » Wed Sep 21, 2011 10:11 pm

ronk wrote:Congratulations. This particular pattern may be viewed as an ALS-xz with multiple values possible for the 'z'. Maybe its an ALS-xzzz. :)

And r5c4 can be part of either the left or right set with 'x' being either <6> or <8>, respectively.

Thanks! It was really difficult upgrading my solver from handling single-digit logic to multi-digit logic. As I mentioned, I was only partially successful. The version that handled full multi-digit logic was so slow that I couldn't accept the execution time. As it is, I wince whenever my solver tackles a puzzle with lots of SIs present from the ANS() submodule.

I don't know why I can't remember the definition of an ALS-xz without looking it up every time. However, I was still fairly sure that my solver had found an ALS-xz because each elimination candidate would have forced the multi-digit component of each SI to be false. This then caused a conflict for the single digit component in the ANS() expressions.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006


Return to Advanced solving techniques