The New Sudoku Players' Forum

[denis_berthier]

.
Eleven's variable replacement method and its complexity

AFAIK, the method to be discussed here was first introduced by eleven in this thread: http://forum.enjoysudoku.com/an-alternative-way-to-solve-the-hard-17-clue-t30022.html#p200126, at a time when I wasn't very present on the forum.
I became aware of it only here: http://forum.enjoysudoku.com/endor-fins-1-2-ser-8-3-8-9-t38805.html#p301646
Since then, I've been busy with extending CSP-Rules with new features (mainly related to allowing some control over the number of steps and with the Pandiag variant of Latin Squares) and I haven't had too much time to think about it. But this question of complexity remained in the background of my thoughts and it was revived by a new application of it here: http://forum.enjoysudoku.com/post308008.html#p308008

Generally speaking the method consists of replacing sets of undecided values in some house by supposedly decided variables x, y, ..., the real value of which is unknown.
The method is smart and mathematically valid; validity is not the point of discussion here. My interest is about its logical complexity.


Let me introduce my questioning by recalling Mith's example (in the second mentioned thread):

Code: Select all

Resolution state after Singles:
+--------------+----------------+-----------------+
! 9    8     6 ! 5    3     124 ! 1247  124  1247 !
! 7    24    3 ! 124  9     6   ! 5     124  8    !
! 24   5     1 ! 24   7     8   ! 9     6    3    !
+--------------+----------------+-----------------+
! 12   126   4 ! 9    8     5   ! 1267  3    127  !
! 123  1236  9 ! 124  1246  7   ! 8     5    124  !
! 8    7     5 ! 3    1246  124 ! 1246  124  9    !
+--------------+----------------+-----------------+
! 134  134   8 ! 7    5     124 ! 124   9    6    !
! 5    14    7 ! 6    124   9   ! 3     8    124  !
! 6    9     2 ! 8    14    3   ! 14    7    5    !
+--------------+----------------+-----------------+

The key is to note that, after singles, the digits 124 only appear once each, while almost all of the other digits are placed. Whatever the solution, the digits 124 will appear in some order in other houses. Let's pick column 4, for example, and we'll relabel r235c4 as ABC. We don't know how the digits 124 map to ABC, but let's look at a grid with ABC in place of all the 124s:

Code: Select all

+-----------------+-------------+------------------+
! 9     8     6   ! 5  3    C   ! ABC7   ABC  ABC7 !
! 7     BC    3   ! A  9    6   ! 5      BC   8    !
! AC    5     AC  ! B  7    8   ! 9      6    3    !
+-----------------+-------------+------------------+
! ABC   ABC6  ABC ! 9  8    5   ! ABC67  3    ABC7 !
! AB3   AB36  9   ! C  AB6  7   ! 8      5    AB   !
! 8     7     5   ! 3  AB6  AB  ! ABC6   ABC  9    !
+-----------------+-------------+------------------+
! AB3C  AB3C  8   ! 7  5    ABC ! ABC    9    6    !
! 5     ABC   7   ! 6  ABC  9   ! 3      8    ABC  !
! 6     9     ABC ! 8  ABC  3   ! ABC    7    5    !
+-----------------+-------------+------------------+

But this grid just solves with singles. [...]And now we can match this to the original puzzle to find C=1, A=4, B=2

From a theoretical point of view, there is some interesting (pseudo-)mystery here:
- you start by deleting some information (stating that B=1or2or4 instead of B=2or4 in r3c4), which should make the puzzle harder;
- but then you find a solution with Singles only, whereas the original puzzle required whips[4].

I think this example is enough motivation for the complexity pseudo-mystery.

[denis_berthier]

.
Using eleven's method, all the (Naked, Hidden and Super-Hidden) Subsets become Singles.

A good way to tackle a problem is to start with its most obvious cases.

Take a Naked Pair in a row and rename x and y the respective contents of the two rc-cells. The eliminations that would have been done by the Naked Pair can now be done by Singles.
Obviously, this also works for Naked Triplets and Naked Quads, with resp. 3 and 4 variables.

By super-symmetry, this also works for Hidden Subsets and Super-Hidden ones (Fish). Another way to say this is, the same method can be applied to cells in the rn, cn or bn spaces.

Now, what does this mean in terms of the complexity of eleven's method?
First, the method is not a resolution rule (in the strict sense I've given to this expression); it is a general method that can be applied in very different situations. If a complexity has to be ascribed to something, it cannot be to the method itself, but to each of its specific applications.

So, what is the complexity in the Subsets cases? Remember that the complexity of a resolution rule is the complexity of the condition pattern of the rule; the application part (assert a value or delete a candidate) is generally obvious.
In order to apply the method, the Subset pattern has to be found; that's the only part where complexity appears in the method. Miracle: in all the Subset cases, the complexity of the method is the same as that of the Subset.

[denis_berthier]

.
Complexity in the Mith example
We have to explain why a puzzle in W4 becomes solvable by Singles.

The key is to note that, after singles, the digits 124 only appear once each, while almost all of the other digits are placed.

If that was really the key, it would mean that one has to check all the occurrences of 3 digits as decided values, i.e. all the 81 rc-cells.

The real application of the method is described in the next sentence:

Let's pick column 4, for example, and we'll relabel r235c4 as ABC

Column 4 has 5 cells containing (at least) one of 1 2 4. This means a complexity of 5 - which may be unnecessary but anyway explains the reduction from W4 to W0. I haven't tried all the other possibilities (all the other rows, columns, blocks and all those in the rn, cn and bn spaces), but there may be a simpler choice than column 4.
On the other hand, as applying the method results in a solution with Singles, it may be the case that complexity 5 is really required.
Anyway, the apparent mystery of complexity reduction is explained.

[denis_berthier]

.

It is not clear to me if you're making some general hypothesis or claim.

You can consider I'm making a very general observation, not limited to the technique of variables replacement. As it's totally obvious, it doesn't deserve to be called a claim.

Let R be any of the ratings I've introduced, i.e. BC, Z, tW, W, gW, B, gB... plus the corresponding ratings with Subsets added, plus those with Finned-Fish added. (Starting from W, most of the time, all are equal). Remember that we are talking of ratings of the hardest step in the resolution path - and the number of steps is not taken into account.

Each of these ratings defines an intrinsic property of a puzzle. This is true not only for Sudoku but for any binary Constraint Satisfaction Problem or any CSP that can be re-expressed in such a form, including of course all those that I have coded in CSP-Rules.

Take R to be any of these ratings. For any puzzle P, R(P) is well defined (possibly infinite). Here is the obvious observation I mentioned above:
Measured in terms of R, the complexity of any transformation applied to P that would result in a puzzle P' with an R rating R(P') strictly smaller than R(P) cannot be smaller than R(P).

The Subsets example in my second post is very clear.

Remarks:
In some cases, expressing the complexity of the transformation in terms of R may not be obvious.
In some cases, using the transformation can lead to a shorter resolution path, but that is off topic, because the number of steps of a resolution path is not an intrinsic property of a puzzle.

[mith]

Column 4 has 5 cells containing (at least) one of 1 2 4.

I must be misunderstanding something here. Where are you getting 5 cells from?

[denis_berthier]

Column 4 has 5 cells containing (at least) one of 1 2 4.

I must be misunderstanding something here. Where are you getting 5 cells from?

No, you're right. I must have confused two puzzles when I wrote this. For a correct explanation of this case, see the discussion page 2 of this thread: http://forum.enjoysudoku.com/endor-fins-1-2-ser-8-3-8-9-t38805.html#p301646

[denis_berthier]

.
7 months since the last post in this thread. I've been busy with other things and it had dropped off my mind, but some post in the Tridagon thread reminded me of this.
I now have a somewhat better view of the whole replacement process.

Let P be a puzzle and T a resolution theory. Suppose that, at some resolution state RS in the resolution path of P within T, the conditions for applying eleven's variable replacement method apply to 3 cells (it could be 4 or more, say n, we'll get similar results).

What the method does is indeed apply a clever form of T&E(BRT, 2) - more generally T&E(BRT, n-1) - to RS.
I say clever, because it factors branches of T&E, precisely those branches that don't depend on the specific values of x, y, z.... But it is fundamentally T&E(BRT, n-1).

This view explains both:
- why it can't be expressed as a resolution rule;
- why it can (apparently) reduce the T rating of a puzzle; what's measured after applying the method is no longer the T-rating, but a rating based on T and T&R(BRT, n-1).
And it corresponds to what's done in the proof of the method.

[eleven]

Maybe this is a good place to give another example for applying the method.

This is one of the new 11.8's by hendrik_monard:

Code: Select all

98.76.5..7.54.98...46......69.8.7....57946.8.8.45..7..4.8...93......46.........2.

After placing 9r5c4 (TH) we get this grid (ER 9.8):

Code: Select all

 *----------------------------------------------------------------------*
 |  9      8      123    |  7     6      123    |  5      14    1234    |
 |  7      123    5      |  4     123    9      |  8      16    1236    |
 |  123    4      6      |  123   58     58     |  123    79    79      |
 |-----------------------+----------------------+-----------------------|
 |  6      9      123    |  8     123    7      |  1234   145   12345   |
 |  123    5      7      |  9     4      6      |  123    8     123     |
 |  8      123    4      |  5     123    123    |  7      69    69      |
 |-----------------------+----------------------+-----------------------|
 |  4      1267   8      |  126   57     125    |  9      3     157     |
 |  1235   1237   1239   |  123   5789   4      |  6      157   1578    |
 |  135    1367   139    |  136   5789   1358   |  14     2     14578   |
 *----------------------------------------------------------------------*

We replace 123 by xyz and (wlog) set r2,4,6 in c5 to x,y,z.

Code: Select all

 *----------------------------------------------------------------------*
 |  9      8      xyz    |  7     6      xyz    |  5      14    1234    |
 |  7      xyz    5      |  4     x      9      |  8      16    1236    |
 |  xyz    4      6      |  xyz   58     58     |  xyz    79    79      |
 |-----------------------+----------------------+-----------------------|
 |  6      9      xyz    |  8     y      7      |  xyz4   145   12345   |
 |  xyz    5      7      |  9     4      6      |  xyz    8     xyz     |
 |  8      xyz    4      |  5     z      xyz    |  7      69    69      |
 |-----------------------+----------------------+-----------------------|

With singles we get

Code: Select all

 *----------------------------------------------------------------------*
 |  9      8      xy     |  7     6      yz     |  5      14    1234    |
 |  7      z      5      |  4     x      9      |  8      16    1236    |
 |  xy     4      6      |  yz    58     58     | *xz-y   79    79      |
 |-----------------------+----------------------+-----------------------|
 |  6      9      xz     |  8     y      7      |  4-xyz  145   12345   |
 |  xz     5      7      |  9     4      6      | *xyz    8    *xyz     |
 |  8      y      4      |  5     z      x      |  7      69    69      |
 |-----------------------+----------------------+-----------------------|

Now y cannot be in r3c7 (would be forced to both r1c36).
x in r3c7 forces x in r5c1 (through r3c1,r14c3) and yz in r3c79.
z in r3c7 forces z in r5c1 (through r3c41) and xy in r3c79.
=> -xyzr4c7
[Edit: i made a mistake here, so i need another step:]
This gives singles 1r9c7, 4r4c7,r9c9,r1c8 and we get

Code: Select all

 *-----------------------------------------------------------------*
 |  9      8      xy     |  7     6      yz    |  5    4    xyz    |
 |  7      z      5      |  4     x      9     |  8    16   6-y    |
 |  xy     4      6      |  12    58     58    |  23   79   79     |
 |-----------------------+---------------------+-------------------|
 |  6      9      xz     |  8     y      7     |  4    15   xz5    |
 |  xz     5      7      |  9     4      6     |  23   8    xyz    |
 |  8      y      4      |  5     z      x     |  7    69   69     |
 |-----------------------+---------------------+-------------------|


Here it can be easily seen, that x in r1c9 forces z in r5c1 and vice versa, i.e. y in r5c9, so y must be in r15c9 => 6r2c9
Solves with skyscraper.

[denis_berthier]

.
A better example in relation with this thread is how I applied the method here:
http://forum.enjoysudoku.com/post316286.html?hilit=replacement#p316286

As you can see, when interpreted in terms of T&E, the 3rd and 4th steps are a version of T&E(2): you try to plug in 2 numbers (the 3rd is a consequence of them) and the combinations that are contradictory with the givens are eliminated.
Granted, my initial presentation with isomorphisms is smarter, as is your presentation with x,y,z variables, but remember, I'm talking of an interpretation in a different framework.
For my general philosophy on this point of interpretation, see here http://forum.enjoysudoku.com/the-t-e-depth-of-a-resolution-rule-t39888-5.html.

[eleven]

Yes, that's how you would program the method:
In the candidates grid replace all occurances of 1,2,3 (including the givens) by 123, then choose a unit with 123's only, place single digits 1,2,3 there and feed the solver with this sukaku.
Try it for all 123 only units and choose the one with the simplest solution (if you can find one).
In the solution then replace all 123's according to the givens to get a solution to the original puzzle.
However no one would do that manually.

[denis_berthier]

Yes, that's how you would program the method:
[..]
However no one would do that manually.

OK. But the interpretation as T&E is not about manual solving. It's about explaining (apparent) reduction of complexity.

[totuan]

Maybe this is a good place to give another example for applying the method.
This is one of the new 11.8's by hendrik_monard:

Code: Select all

98.76.5..7.54.98...46......69.8.7....57946.8.8.45..7..4.8...93......46.........2.

After placing 9r5c4 (TH) we get this grid (ER 9.8):

Hidden Text: Show

Code: Select all

 *----------------------------------------------------------------------*
 |  9      8      123    |  7     6      123    |  5      14    1234    |
 |  7      123    5      |  4     123    9      |  8      16    1236    |
 |  123    4      6      |  123   58     58     |  123    79    79      |
 |-----------------------+----------------------+-----------------------|
 |  6      9      123    |  8     123    7      |  1234   145   12345   |
 |  123    5      7      |  9     4      6      |  123    8     123     |
 |  8      123    4      |  5     123    123    |  7      69    69      |
 |-----------------------+----------------------+-----------------------|
 |  4      1267   8      |  126   57     125    |  9      3     157     |
 |  1235   1237   1239   |  123   5789   4      |  6      157   1578    |
 |  135    1367   139    |  136   5789   1358   |  14     2     14578   |
 *----------------------------------------------------------------------*

We replace 123 by xyz and (wlog) set r2,4,6 in c5 to x,y,z.

Code: Select all

 *----------------------------------------------------------------------*
 |  9      8      xyz    |  7     6      xyz    |  5      14    1234    |
 |  7      xyz    5      |  4     x      9      |  8      16    1236    |
 |  xyz    4      6      |  xyz   58     58     |  xyz    79    79      |
 |-----------------------+----------------------+-----------------------|
 |  6      9      xyz    |  8     y      7      |  xyz4   145   12345   |
 |  xyz    5      7      |  9     4      6      |  xyz    8     xyz     |
 |  8      xyz    4      |  5     z      xyz    |  7      69    69      |
 |-----------------------+----------------------+-----------------------|

With singles we get

Code: Select all

 *----------------------------------------------------------------------*
 |  9      8      xy     |  7     6      yz     |  5      14    1234    |
 |  7      z      5      |  4     x      9      |  8      16    1236    |
 |  xy     4      6      |  yz    58     58     | *xz-y   79    79      |
 |-----------------------+----------------------+-----------------------|
 |  6      9      xz     |  8     y      7      |  4-xyz  145   12345   |
 |  xz     5      7      |  9     4      6      | *xyz    8    *xyz     |
 |  8      y      4      |  5     z      x      |  7      69    69      |
 |-----------------------+----------------------+-----------------------|

Now y cannot be in r3c7 (would be forced to both r1c36).
x in r3c7 forces x in r5c1 (through r3c1,r14c3) and yz in r3c79.
z in r3c7 forces z in r5c1 (through r3c41) and xy in r3c79.
=> -xyzr4c7
[Edit: i made a mistake here, so i need another step:]
This gives singles 1r9c7, 4r4c7,r9c9,r1c8 and we get

Code: Select all

 *-----------------------------------------------------------------*
 |  9      8      xy     |  7     6      yz    |  5    4    xyz    |
 |  7      z      5      |  4     x      9     |  8    16   6-y    |
 |  xy     4      6      |  12    58     58    |  23   79   79     |
 |-----------------------+---------------------+-------------------|
 |  6      9      xz     |  8     y      7     |  4    15   xz5    |
 |  xz     5      7      |  9     4      6     |  23   8    xyz    |
 |  8      y      4      |  5     z      x     |  7    69   69     |
 |-----------------------+---------------------+-------------------|


Here it can be easily seen, that x in r1c9 forces z in r5c1 and vice versa, i.e. y in r5c9, so y must be in r15c9 => 6r2c9
Solves with skyscraper.

Code: Select all

 *--------------------------------------------------------------------*
 | 9      8     *123    | 7      6     *123    | 5      14     1234   |
 | 7     *123    5      | 4     *123    9      | 8      16     1236   |
 |*123    4      6      |*123    58     58     | 123    79     79     |
 |----------------------+----------------------+----------------------|
 | 6      9     *123    | 8     #123    7      |A1234   145    12345  |  A => impossible pattern
 |*123    5      7      | 9      4      6      |#123    8      123    |    => r4c7=4
 | 8     *123    4      | 5     #123   #123    | 7      69     69     |
 |----------------------+----------------------+----------------------|
 | 4      1267   8      | 126    57     125    | 9      3      157    |
 | 1235   1237   1239   | 123    5789   4      | 6      157    1578   |
 | 135    1367   139    | 136    5789   1358   | 14     2      14578  |
 *--------------------------------------------------------------------*
 *-----------------------------------------------------------*
 | 9     8    *123   | 7     6    *123   | 5     4    #123   |
 | 7    *123   5     | 4    *123   9     | 8     16   #1236  |
 |*123   4     6     |*123   58    58    | 23    79    79    |
 |-------------------+-------------------+-------------------|
 | 6     9    *123   | 8    #123   7     | 4     15    1235  |
 |*123   5     7     | 9     4     6     | 23    8    A123   |  A => impossible pattern
 | 8    *123   4     | 5    #123  #123   | 7     69    69    |    => r2c9=6
 |-------------------+-------------------+-------------------|
 | 4     126   8     | 126   57    12    | 9     3     57    |
 | 1235  1237  1239  | 123   579   4     | 6     57    8     |
 | 35    367   39    | 36    5789  58    | 1     2     4     |
 *-----------------------------------------------------------*

It seems that, when you can use “replacement method” then have "impossible pattern" side by side. I'm not sure...

totuan

[denis_berthier]

It seems that, when you can use “replacement method” then have "impossible pattern" side by side. I'm not sure...

You have an example where this is true.
But the method is extremely general. You can apply it to a Naked Triplet.

But the converse is true: when you have an impossible k-digit pattern (with appropriate conditions on the places of cells), you can apply k-replacement.
In any case, applying replacement is just that: applying it. It doesn't guarantee to lead to a solution.