remote triples

Advanced methods and approaches for solving Sudoku puzzles

remote triples

Postby StrmCkr » Fri Oct 24, 2008 2:50 pm

Remote Triples: {unsure if this is new or not..}

Code: Select all
 *-----------------------------*
 | . . . | . .  . | .   .    . |
 | . . . | . X  . | .   29   . |
 | . . . | . .  . | .   .    . |
 |-------+--------+------------|
 | . . . | . .  . | .   289  . |
 | . . . | . 29 . | 289 .    . |
 | . . . | . .  . | .   89   . |
 |-------+--------+------------|
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 *------------------------------*

X < > 2,9

Side note: from standard locked set operand.
R5C7 < > 8,

Which shows this self-degenerated variation of this same type:

Code: Select all
 *----------------------------*
 | . . . | . .  . | .   .    . |
 | . . . | . X  . | .   29   . |
 | . . . | . .  . | .   .    . |
 |-------+--------+------------|
 | . . . | . .  . | .   289  . |
 | . . . | . 29 . | 29  .    . |
 | . . . | . .  . | .   89   . |
 |-------+--------+------------|
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 *------------------------------*


X<>2,9

A real world example:

Code: Select all
 *-----------*
 |...|.5.|.6.|
 |17.|6..|5..|
 |9.6|3..|.18|
 |---+---+---|
 |...|..1|..5|
 |.41|..6|.73|
 |2..|...|...|
 |---+---+---|
 |7..|...|.3.|
 |.2.|.8.|.4.|
 |.39|...|.5.|
 *-----------*

Code: Select all
 *-----------------------------------------------------------------------------*
 | 348     8       2348    | 124789  5       24789   | 23479   6       2479    |
 | 1       7       2348    | 6       4-29    2489    | 5       29@     249     |
 | 9       5       6       | 3       247     247     | 247     1       8       |
 |-------------------------+-------------------------+-------------------------|
 | 368     689     378     | 24789   23479   1       | 24689   289@    5       |
 | 58      4       1       | 2589    29@     6       | 29-8@    7       3       |
 | 2       5689    3578    | 45789   3479    345789  | 14689   89@     1469    |
 |-------------------------+-------------------------+-------------------------|
 | 7       1568    458     | 12459   12469   2459    | 12689   3       1269    |
 | 56      2       5       | 1579    8       3579    | 1679    4       1679    |
 | 468     3       9       | 1247    12467   247     | 12678   5       1267    |
 *-----------------------------------------------------------------------------*


R2C5 <>2,9, R5C7 <>8

edit
i noticed there is some additional restrictiosn from this chain as well..
Code: Select all
 *-----------------------------*
 | . . . | . .  . | .   .    . |
 | . . . | . X  . | .   29   . |
 | . . . | . .  . | .   .    . |
 |-------+--------+------------|
 | . . . | . .  . | /  289     / |
 | x x x | x 29 x | 289   /  /
 | . . . | . .  . | /  89     / |
 |-------+--------+------------|
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 *------------------------------*


mostly from the pair that is derived in the process.
Last edited by StrmCkr on Sat Oct 25, 2008 1:29 pm, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 661
Joined: 05 September 2006

Re: remote triples

Postby denis_berthier » Fri Oct 24, 2008 10:04 pm

StrmCkr wrote:Remote Triples: {unsure if this is new or not..}

Code: Select all
 *-----------------------------*
 | . . . | . .  . | .   .    . |
 | . . . | . X  . | .   29   . |
 | . . . | . .  . | .   .    . |
 |-------+--------+------------|
 | . . . | . .  . | .   289  . |
 | . . . | . 29 . | 289 .    . |
 | . . . | . .  . | .   89   . |
 |-------+--------+------------|
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 *------------------------------*

X < > 2,9

xyt-chain {2 9}r2c8 - {9 8}r6c8 - {8 2 9#1}r5c7 - {2 9 8#2}r4c8 - {9 2}r5c5 ==> r2c5 <> 2

and a similar chain for r2c5 <> 9, once one has eliminated r5c7 <> 8

[Corrected an error noticed by ronk in the first version of this chain]
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby PIsaacson » Sat Oct 25, 2008 10:05 am

StrmCkr,

Thanks for the updates!

Allan's link-sets and Champagne's full-tagging are on my "must-read, must-try-to-understand" list. I've read their posts, gone to their web sites and I have a notebook full of questions and high level designs to duplicate some of their work. I even wrote a small program to find all possible sets/link-sets to determine approximate computation time. The "average" puzzle takes over 48 hours, and that's without any logic to combine them into base/cover link-sets with associated reductions. I'm looking forward to your constraint approach. Send me the url/topic.

My solver determined that your remote triples was best solved by POM.
Code: Select all
Puzzle: ....5..6.17.6..5..9.63...18.....1..5.41..6.732........7......3..2..8..4..39....5. puzzle 1 ../test/remote_triples.ss

 348       8         2348     |124789    5+        24789    |23479     6+        2479     
 1+        7+        2348     |6+        249       2489     |5+        29        249     
 9+        5         6+       |3+        247       247      |247       1+        8+       
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 368       689       378      |24789     23479     1+       |24689     289       5+       
 58        4+        1+       |2589      29        6+       |289       7+        3+       
 2+        5689      3578     |45789     3479      345789   |14689     89        1469     
 --------- --------- ---------+--------- --------- ---------+--------- --------- ---------
 7+        1568      458      |12459     12469     2459     |12689     3+        1269     
 56        2+        5        |1579      8+        3579     |1679      4+        1679     
 468       3+        9+       |1247      12467     247      |12678     5+        1267     

do_pinnings - starting with 27 total solved

update_cell - setting r1c2 = d8
update_cell - setting r1c4 = d1
update_cell - setting r1c7 = d3
update_cell - setting r2c3 = d3
update_cell - setting r2c6 = d8
update_cell - setting r3c2 = d5
update_cell - setting r4c1 = d3
update_cell - setting r6c5 = d3
update_cell - setting r7c2 = d1
update_cell - setting r8c3 = d5
update_cell - setting r8c6 = d3
update_cell - setting r9c5 = d1

do_pinnings - ending with 12 updates 39 total solved
do_pinnings - starting with 39 total solved

update_cell - setting r1c1 = d4
update_cell - setting r1c3 = d2
update_cell - setting r5c1 = d5
update_cell - setting r7c3 = d4
update_cell - setting r7c5 = d6
update_cell - setting r7c7 = d8
update_cell - setting r8c1 = d6
update_cell - setting r9c1 = d8

do_pinnings - ending with 8 updates 47 total solved
do_pinnings - starting with 47 total solved

update_cell - setting r5c4 = d8

do_pinnings - ending with 1 updates 48 total solved
do_pinnings - starting with 48 total solved

do_pinnings - ending with 0 updates 48 total solved
do_restrictions - starting with 48 total solved

do_restrictions - ending with 0 updates 48 total solved
do_fishing - starting with 48 total solved

do_fishing - reducing r2c5.<249> by <2> - covered by no sets
do_fishing - reducing r3c7.<247> by <2> - covered by no sets
update_cell - setting r1c6 = d9
do_fishing - forcing r1c6 to d9 - covered by all sets
do_fishing - reducing r4c4.<2479> by <9> - covered by no sets
do_fishing - reducing r6c4.<4579> by <9> - covered by no sets

do_fishing - ending with 5 updates 49 total solved
do_pinnings - starting with 49 total solved

update_cell - setting r1c9 = d7
update_cell - setting r2c5 = d4
update_cell - setting r3c7 = d4
update_cell - setting r4c4 = d4
update_cell - setting r6c9 = d4
update_cell - setting r8c9 = d1
update_cell - setting r9c6 = d4
update_cell - setting r9c9 = d6

do_pinnings - ending with 8 updates 57 total solved
do_pinnings - starting with 57 total solved

update_cell - setting r6c7 = d1

do_pinnings - ending with 1 updates 58 total solved
do_pinnings - starting with 58 total solved

update_cell - setting r4c7 = d6
update_cell - setting r6c2 = d6
update_cell - setting r6c8 = d9
update_cell - setting r8c7 = d9
update_cell - setting r9c7 = d7

do_pinnings - ending with 5 updates 63 total solved
do_pinnings - starting with 63 total solved

update_cell - setting r2c8 = d2
update_cell - setting r2c9 = d9
update_cell - setting r4c2 = d9
update_cell - setting r4c5 = d2
update_cell - setting r4c8 = d8
update_cell - setting r5c5 = d9
update_cell - setting r5c7 = d2
update_cell - setting r6c3 = d8
update_cell - setting r7c4 = d9
update_cell - setting r7c6 = d5
update_cell - setting r7c9 = d2
update_cell - setting r8c4 = d7
update_cell - setting r9c4 = d2

do_pinnings - ending with 13 updates 76 total solved
do_pinnings - starting with 76 total solved

update_cell - setting r3c5 = d7
update_cell - setting r3c6 = d2
update_cell - setting r4c3 = d7
update_cell - setting r6c4 = d5
update_cell - setting r6c6 = d7

do_pinnings - ending with 5 updates 81 total solved
RCB solution        1 for puzzle 1 ../test/remote_triples.ss

 4 8 2| 1 5 9| 3 6 7
 1 7 3| 6 4 8| 5 2 9
 9 5 6| 3 7 2| 4 1 8
------+------+------
 3 9 7| 4 2 1| 6 8 5
 5 4 1| 8 9 6| 2 7 3
 2 6 8| 5 3 7| 1 9 4
------+------+------
 7 1 4| 9 6 5| 8 3 2
 6 2 5| 7 8 3| 9 4 1
 8 3 9| 2 1 4| 7 5 6

Puzzle call statistics:
  do_pinnings      updates/calls 53/9               5.8889       0.2883 msec       0.0320 msec/call       0.0054 msec/update
  do_restrictions  updates/calls 0/1                0.0000       0.0151 msec       0.0151 msec/call          inf msec/update
  do_fishing       updates/calls 5/1                5.0000       1.9804 msec       1.9804 msec/call       0.3961 msec/update
Puzzle 1 took 2.4584 msec for 1 solution(s)

Puzzle final statistics:
  tot_pinnings     updates/calls 53/9               5.8889       0.2883 msec       0.0320 msec/call       0.0054 msec/update
  tot_restrictions updates/calls 0/1                0.0000       0.0151 msec       0.0151 msec/call          inf msec/update
  tot_fishing      updates/calls 5/1                5.0000       1.9804 msec       1.9804 msec/call       0.3961 msec/update

sudoku -bvg ../test/remote_triples.ss
nrczt promote 0) 0  1) 0  2) 0  3) 0  4) 0  5) 0  6) 0    z_links) 0  t_links) 0  g_links) 0
nrczt search
vt chains) 0  vs chains) 0  ve chains) 0  nl[0] exits) 0  nrczt 0) 0  nrczt 1) 0  nrczt 2) 0  nrczt 3) 0  nrczt 4) 0 
nl exits 1) 0/0  2) 0/0  3) 0/0  4) 0/0  5) 0/0  6) 0/0  7) 0/0  8) 0/0  9) 0/0 
sudoku used solving order prfdantsc -N18 -A5 -D5


3d-medusa coloring cracked it with 5 reductions.
nrczt cracked it with 2 chains and 2 bi-value cell reductions.
distributed-disjoint-subsets cracked it with 2 ADDS and 5 reductions.

Nothing exactly matched your solution of R2C5 <> 2,9 R5C7 <> 8. POM fishing was the fastest (about 2 msec) with a R2C5 <> 2. nrczt resolved R2C5 == 4 on the 2nd chain.

Removed from the nrczt group extentions topic to here
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby StrmCkr » Sat Oct 25, 2008 6:38 pm

added a mod to the first post added in markings of x's where a pair from sub patten excludes additional 2'9s along the row...


denis -
its a combined coverset of layers 289...

. thats how i approached the pattern.

one single move.

not two.

and your way also is the same thing worded diffrent.:)
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 661
Joined: 05 September 2006

Postby ronk » Sat Oct 25, 2008 7:20 pm

StrmCkr wrote:its a combined coverset of layers 289...

. thats how i approached the pattern.

one single move.

not two

But there are two different "coversets."

Coverset 2r2, 9c8, 2b6, 8b6, 9r5 and 2c5 imply r2c5<>2. In chain form using NL notation ...
r2c5 -2- r2c8 -9- r46c8 -28- r5c7 -9- r5c5 -2- r2c5 ==> r2c5<>2

Coverset 9r2, 2c8, 8b6, 9b6, 2r5 and 9c5 imply r2c5<>9. In chain form ...
r2c5 -9- r2c8 -2- r46c8 -89- r5c7 -2- r5c5 -9- r2c5 ==> r2c5<>9

To consider them as one move makes no sense to me.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby StrmCkr » Sat Oct 25, 2008 8:32 pm

i think of it this way.

linked layers operate as a single unit.

for example
a remote pair.

if its a singular unit with coverset logic: the covering set being 2 digits.

then both end points of the code are identical the operation is a two fold restiction equal to the end point cells (2 digits). restriction in this case is line of sight to the end points. marked with x.

in the example its a
3 layer coverset with a freedom of 2 with in the layer.
where both endpoints are the same as the above. => 2 restrictions via line of sight equal to both end points.

to explain this better id have to show you how my solver works... which would not be too fun.. perhaps i should build a thread on it..

i built it using x-cell.:)
i broke up the standard sudoku into a
9 "planer" {layer} approach... issolating each digit to there own plane. and linking them into subplanes as pairs etc...

where subplanes fuction as 1 layer affectign both linked layers equally.

"
only thing i hate is manually entering in grids..."

any one know how to translate a 81 charter sting into 81 cells? using excel?
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 661
Joined: 05 September 2006

Postby David P Bird » Sun Oct 26, 2008 12:16 am

StrmCkr
Use the MID worksheet function to extract each character into its corresponding cell and multiply by 1 to force it to numeric.
eg
Enter 1 to 9 in A2:A10 and B1:J1 as row and column numbers
Copy the character string as text to M1
Enter "=1*MID($M$1,B$1+9*$A1,1)" in B2 and copy this to fill B2:J10
David P Bird
2010 Supporter
 
Posts: 960
Joined: 16 September 2008
Location: Middle England

Postby aran » Mon Oct 27, 2008 4:11 am

From a hidden pair perspective :
hp89r46c8
-8r5c7 =>r5c7 <8>
-9=2r2c8 =>r2c5 <2>
-89=2r5c7-2=9r5c5 =>r2c5 <9>.

hp89r46c8=2r4c8-2=9r2c8 (=>r2c5 <9>)-9=8r6c8-8r5c7 (=>r5c7 <8>) =*9r5c7-9=2r5c5 (=>r2c5 <2>)
* combined with 2r4c8

=>r2c5 <2> <9>, r5c7 <8>
aran
 
Posts: 334
Joined: 02 March 2007

Postby ronk » Mon Oct 27, 2008 4:58 am

If this pattern deserves a name, it should at least be described (and the eliminations proven) with a generalized non-degenerate naked triple, as in the exemplar below. By that I specifically mean that all three digits can be in all three cells of the naked triple.
Code: Select all
 *--------------------------------*
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  X  . |  .  29 . |
 |  .  .  . |  .  .  . |  .  .  . |
 |----------+----------+----------|
 |  .  .  . |  .  .  . |  . 289 . |
 |  .  .  . |  .  29 . | 289 .  . |
 |  .  .  . |  .  .  . |  . 289 . |
 |----------+----------+----------|
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 *--------------------------------*
 X <> 2,9


Moreover, the term "naked triples" is not appropriate. Firstly, there is only one triple in the pattern. Secondly, the pattern behaves like a "remote naked pair", where the links between the remote pair are obviously different.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Mon Oct 27, 2008 6:42 am

ronk wrote:
Code: Select all
 *--------------------------------*
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  X  . |  .  29 . |
 |  .  .  . |  .  .  . |  .  .  . |
 |----------+----------+----------|
 |  .  .  . |  .  .  . |  . 289 . |
 |  .  .  . |  .  29 . | 289 .  . |
 |  .  .  . |  .  .  . |  . 289 . |
 |----------+----------+----------|
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 *--------------------------------*
 X <> 2,9

With the 289 Naked Triple, I can relate this pattern to a General Remote Pair through

Code: Select all
(2|9) -[r2c8]- (9|2) -[r46c8]= (9|2) =[r5c7]- (9|2) -[r5c5]- (2|9)

This is all that's needed.

http://www.dailysudoku.com/sudoku/forums/viewtopic.php?p=9089&sid=9b4066ff0df80597a3b4db638fd2b66a#9089

keith wrote:Chapter 2: A More General Remote Pair

It is not necessary that the remote pair be connected by a chain of cells each having the same two candidates. Only one candidate is required.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Luke » Mon Oct 27, 2008 7:42 am

StrmCkr's pattern:
Code: Select all
 *-----------------------------*
 | . . . | . .  . | .   .    . |
 | . . . | . X    | .   ab   . |
 | . . . | . .  . | .   .    . |
 |-------+--------+------------|
 | . . . | . .  . | .   abc  . |
 | . . . | . ab . | ab .     . |
 | . . . | . .  . | .   bc   . |
 |-------+--------+------------|
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 *------------------------------*
X <> a because the a values form a singles chain.
X <> b because the b values form an AIC.

The puzzle reduced:
Code: Select all
 *-----------------------------------------------------------*
 | 4     8     2     | 1     5     79    | 3     6     79    |
 | 1     7     3     | 6     249   8     | 5     29    249   |
 | 9     5     6     | 3     247   247   | 247   1     8     |
 |-------------------+-------------------+-------------------|
 | 3     69    78    | 2479  2479  1     | 46    289   5     |
 | 5     4     1     | 8     29    6     | 29    7     3     |
 | 2     69    78    | 4579  3     4579  | 146   89    146   |
 |-------------------+-------------------+-------------------|
 | 7     1     4     | 259   6     259   | 8     3     29    |
 | 6     2     5     | 79    8     3     | 179   4     179   |
 | 8     3     9     | 247   1     247   | 267   5     267   |
 *-----------------------------------------------------------*
a = 2, singles chain: [r2c8]=[r4c8]=[r5c7]=[r5c5], [r2c5]<>2
b = 9, AIC: 9[r2c5]-9[r2c8]=2[r2c8]-2[r4c8]=2[r5c7]-2[r5c5]=9[r5c5]-9[r2c5], [r2c5]<>9.
User avatar
Luke
2015 Supporter
 
Posts: 435
Joined: 06 August 2006
Location: Southern Northern California

Postby udosuk » Mon Oct 27, 2008 7:49 am

daj95376 wrote:
ronk wrote:
Code: Select all
 *--------------------------------*
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  X  . |  .  29 . |
 |  .  .  . |  .  .  . |  .  .  . |
 |----------+----------+----------|
 |  .  .  . |  .  .  . |  . 289 . |
 |  .  .  . |  .  29 . | 289 .  . |
 |  .  .  . |  .  .  . |  . 289 . |
 |----------+----------+----------|
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 |  .  .  . |  .  .  . |  .  .  . |
 *--------------------------------*
 X <> 2,9

With the 289 Naked Triple, I can relate this pattern to a General Remote Pair

Perhaps Remote Pair with Grouped Strong Link is more descriptive.

The main point here is not the triple. It's the grouped strong link of 2 (& 9) in r46c8+r5c7 that allows the remote pair to work. For example you can even make it a quad or a quint:
Code: Select all
+----------+----------+-------------------+
|  .  .  . |  .  .  . |  .    .     .     |
|  .  .  . |  .  X  . |  .    29    .     |
|  .  .  . |  .  .  . |  .    .     .     |
+----------+----------+-------------------+
|  .  .  . |  .  .  . | .     12589 .     |
|  .  .  . |  .  29 . | 12589 12589 12589 |
|  .  .  . |  .  .  . | .     12589 .     |
+----------+----------+-------------------+
|  .  .  . |  .  .  . |  .    .     .     |
|  .  .  . |  .  .  . |  .    .     .     |
|  .  .  . |  .  .  . |  .    .     .     |
+----------+----------+-------------------+
X <> 2,9

(The mechanism is similar to Empty Rectangle but not quite the same.)

In JSudoku this move will be detected as 2 separated "Grouped Y-wings" (i.e. W-wings) of 2 & 9 respectively.:idea:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Mon Oct 27, 2008 8:23 am

udosuk wrote:
Code: Select all
+----------+----------+-------------------+
|  .  .  . |  .  .  . |  .    .     .     |
|  .  .  . |  .  X  . |  .    29    .     |
|  .  .  . |  .  .  . |  .    .     .     |
+----------+----------+-------------------+
|  .  .  . |  .  .  . | .     12589 .     |
|  .  .  . |  .  29 . | 12589 12589 12589 |
|  .  .  . |  .  .  . | .     12589 .     |
+----------+----------+-------------------+
|  .  .  . |  .  .  . |  .    .     .     |
|  .  .  . |  .  .  . |  .    .     .     |
|  .  .  . |  .  .  . |  .    .     .     |
+----------+----------+-------------------+
X <> 2,9

(The mechanism is similar to Empty Rectangle but not quite the same.)

If there is no ER, where is your strong link:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby PIsaacson » Mon Oct 27, 2008 9:25 am

Code: Select all
 *-----------------------------*
 | . . . | . .  . | .   .    . |
 | . . . | . X  . | .   29   . |
 | . . . | . .  . | .   .    . |
 |-------+--------+------------|
 | . . . | . .  . | .   289  . |
 | . . . | . 29 . | 289 .    . |
 | . . . | . .  . | .   89   . |
 |-------+--------+------------|
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 | . . . | . .  . | .   .    . |
 *------------------------------*


Can this be analyzed as an example of subset counting?

Multiplicities for candidates 2/8/9 = 2/1/2 total 5 for 5 cells.
r2c5 = 2 reduces total multiplicity to 4 - illegal?
r2c5 = 9 reduces total multiplicity to 4 - illegal?
PIsaacson
 
Posts: 249
Joined: 02 July 2008

Postby StrmCkr » Mon Oct 27, 2008 11:06 am

wow.. lots of attention.

thanks guys i was trying to extend the pattern into quads and quintouples today with not much luck..

other thoughts are back into UR forms?


and yes paul it can..
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 661
Joined: 05 September 2006

Next

Return to Advanced solving techniques