Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Is there a name for this "twice false" technique?

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Wed Nov 23, 2005 1:00 am    Post subject: Is there a name for this "twice false" technique? Reply with quote

I occasionally use a true-false chaining technique on the candidates of a single digit to obtain a few eliminations. I'm curious if my approach exists as a formalized technique.

I'm not great at word descriptions, so I'll just illustrate with a very simple example.
Code:
 .  .  .  | 5  .  .  | .  5  . 
 .  .  .  | .  5  .  | .  5  5 
 .  .  .  | .  .  .  | .  .  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  5  5 
 .  .  .  | .  .  .  | .  .  . 
----------+----------+----------
 .  .  .  | 5  5  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

The above is a jellyfish pattern which I used to think was irreducible. But a '5' can indeed be eliminated from box 3. Starting at a conjugate pair, arbitrarily assign true (T) and (F) values to the pair. Then follow the implications of those assignments, further assigning true and false to as many locations as possible to obtain ...
Code:
 .  .  .  | F  .  .  | .  T  . 
 .  .  .  | .  T  .  | .  F  F 
 .  .  .  | .  .  .  | .  .  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  F  T 
 .  .  .  | .  .  .  | .  .  . 
----------+----------+----------
 .  .  .  | T  F  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

There can be but one 'T' in any group (row, column, or 3x3 box), but there can be any number of 'F's.

Now do it again, this time assigning true (t) where false (F) was first assigned, and false (f) where true (T) was first assigned. But there are exceptions, so it's not quite that simple.

There are no exeptions for conjugate pairs, so make the exchanges there first. And again follow the implications to obtain ...
Code:
 .  .  .  | t  .  .  | .  f  . 
 .  .  .  | .  f  .  | .  f* t 
 .  .  .  | .  .  .  | .  .  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  t  f 
 .  .  .  | .  .  .  | .  .  . 
----------+----------+----------
 .  .  .  | f  t  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

Since r2c8 is false in either case, candidate 5 may be eliminated from that location.
********************
Now a more complicated example.
Code:
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | 3  3  . 
----------+----------+----------
 3  .  3  | .  3  .  | 3  3  . 
 3  .  .  | .  .  .  | .  3  . 
 3  .  .  | .  3  .  | 3  3  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 3  .  3  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

The first set of T/F assignments looks like ...
Code:

 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | T  F  . 
----------+----------+----------
 F  .  T  | .  F  .  | F  F  . 
 F  .  .  | .  .  .  | .  T  . 
 F  .  .  | .  T  .  | F  F  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 T  .  F  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

The second set of t/f assignments to just the conjugates looks like ...
Code:

 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | f  t  . 
----------+----------+----------
 3  .  f  | .  t  .  | 3  3  . 
 3  .  .  | .  .  .  | .  3  . 
 3  .  .  | .  f  .  | 3  3  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 f  .  t  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

Next assign false (f) to remaining candidates in groups with a true (t) to obtain ...
Code:

 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | f  t  . 
----------+----------+----------
 f  .  f  | .  t  .  | f  f  . 
 3  .  .  | .  .  .  | .  f  . 
 3  .  .  | .  f  .  | 3  f  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 f  .  t  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

Note that column 7 (and box 6) are without a true, so 't' may be assigned to r6c7. As a result, r6c1 is 'f', and then column 1 (and box 4) are without a true, so r5c1 is 't'. The final result is ...
Code:

 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | f  t  . 
----------+----------+----------
 f  .  f  | .  t  .  | f  f  . 
 t  .  .  | .  .  .  | .  f  . 
 f  .  .  | .  f  .  | t  f  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 f  .  t  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

Duplicating the first T/F assignments (so we can have them side-by-side) ...
Code:

 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | T  F  . 
----------+----------+----------
 F* .  T  | .  F  .  | F* F* . 
 F  .  .  | .  .  .  | .  T  . 
 F* .  .  | .  T  .  | F  F* . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 T  .  F  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 

The candidate 3 may be eliminated (*) from the five locations bearing false in both maps, leaving us with ...
Code:

 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | 3  3  . 
----------+----------+----------
 .  .  3  | .  3  .  | .  .  . 
 3  .  .  | .  .  .  | .  3  . 
 .  .  .  | .  3  .  | 3  .  . 
----------+----------+----------
 .  .  .  | .  .  .  | .  .  . 
 3  .  3  | .  .  .  | .  .  . 
 .  .  .  | .  .  .  | .  .  . 
Back to top
View user's profile Send private message
arsoncupid

Joined: 22 Nov 2005
Posts: 10
:

Items
PostPosted: Wed Nov 23, 2005 3:00 am    Post subject: Reply with quote

I just used this technique yesterday!

Code:
23478 9   6  | 234 2345 357 | 48  1  234
2348  5   32 | 6   1    39  | 7   28 2349
2347  234 1  | 8   234  379 | 46  5  23469

5     23  23 | 7   9    4   | 1   6  8
1     6   8  | 23  235  35  | 9   4  7
9     7   4  | 1   6    8   | 2   3  5

246   248 9  | 5   7    1   | 3   28 246
346   348 5  | 9   34   2   | 468 7  1
234   1   7  | 34  8    6   | 5   9  24


r1c1, r2c1 are an 8 pair.
r1c7, r2c8 are another.
r7c8, r8c7 are a third.
r7c2, r8c2 are a fourth.

r7c1, r8c1 are a 6 pair.
r7c9, r8c7 are another.
r3c7, r3c9 are a third.

These two systems, of 6's and 8's, intersect at r8c7.

By guessing r7c1=6, and following the results of that through these two systems, then r8c7=6.
Alternatively, if r8c1=6, then r8c7=8.

In both cases, r8c7 cannot be 4. So that 4 can be dropped.

I think of this as a form of Nishio. Instead of seeking a contradiction, you seek an exclusion.
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Nov 23, 2005 6:55 am    Post subject: Reply with quote

rkral, your second step is no good. If you flip the first conjugate chain from TF to FT, flipping the second is optional. There are three arrangements of true/false values, not two; you can only eliminate a cell that's false for all three. Let's take a look from a coloring perspective:
Code:
 .  .  .  | a  .  .  | .  A  .
 .  .  .  | .  A  .  | .  *  b
 .  .  .  | .  .  .  | .  .  .
----------+----------+----------
 .  .  .  | .  .  .  | .  .  .
 .  .  .  | .  .  .  | .  b  B
 .  .  .  | .  .  .  | .  .  .
----------+----------+----------
 .  .  .  | A  a  .  | .  .  .
 .  .  .  | .  .  .  | .  .  .
 .  .  .  | .  .  .  | .  .  .

Originally you assigned A as the true value, which implies B is also true since b can't be true as well.

In the second step you switch this so a is true. That tells you nothing about b or B. Therefore you can't tell if the cell you ended up eliminating is true or false. If a is true and B is true, which you can't rule out, that cell must also be true!

Had you approached this the other way you'd run into the same snag. If you say b is true, a is also true. But if B is true, that tells you nothing about a or A.

In coloring terminology, A excludes b; if one is true the other is false. They are not conjugates because if one is false, it does not prove the other true. Your three possibilities are ab, aB, and AB.

This pattern is indeed irreducible from the information you have. The reduction probably worked for you only because it often turns out to be the case, just as you may often see a triple of 12 23 123 that you can reduce to 12 23 13. This sort of symmetry seems to be common, but not mandatory, so you got lucky on this one.
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Wed Nov 23, 2005 10:55 am    Post subject: Reply with quote

Lummox JR wrote:
rkral, your second step is no good.
...
In the second step you switch this so a is true. That tells you nothing about b or B. Therefore you can't tell if the cell you ended up eliminating is true or false. If a is true and B is true, which you can't rule out, that cell must also be true.


Embarassed Thanks for the correction. Ironically, that's now the "second" time I've had to learn that.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron