A complete transformation of the grid...

Everything about Sudoku that doesn't fit in one of the other sections

A complete transformation of the grid...

Postby 999_Springs » Wed Aug 06, 2008 5:33 pm

Suppose we ignore the 3x3 block constraint for this post.

Every candidate in any puzzle is fixed by 3 things that can take values 1-9: row number, column number and candidate value. Two of these things determine where the candidate goes and the other one determines what it is.

My suggestion: take a blank grid and rewrite everything of the form rAcB#C in the form rCcA#B. If a technique is found in this new grid (ignoring the box constraint, which doesn't work here) then (I think) it will lead to a valid elimination in the original grid.

Here are some sample techniques in the new grid and their equivalents in the original, to see how this works.

Single:
Code: Select all
new grid              original grid
. . . . . . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .
. . . . . . . . . ==> . . . . . 7 . . .
. . . . . . . . .     . . . . . . . . .
. . . . 6 . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .
. . . . . . . . .     . . . . . . . . .
r7c5=6                r5c6=7


Horizontal naked pair:
Code: Select all
new grid                original grid
. . .  . . .  . . .     . . . . . . . . .
. . .  . . .  . . .     . . . . . . . . .
. . 36 . . 36 . . .     . . 3-----3 . . .
. . .  . . .  . . .     . . | . . | . . .
. . .  . . .  . . . ==> . . | . . | . . .
. . .  . . .  . . .     . . 3-----3 . . .
. . .  . . .  . . .     . . . . . . . . .
. . .  . . .  . . .     . . . . . . . . .
. . .  . . .  . . .     . . . . . . . . .
r3c1245789<>36          r1245789c36<>3 (X-Wing)


Vertical naked pair:
Code: Select all
new grid               original grid
. . .  . . . . . .     .   . . . . . .   . .
. . .  . . . . . .     .   . . . . . .   . .
. . 17 . . . . . .     3,8-----------3,8 . .
. . .  . . . . . .     .   . . . . . .   . .
. . .  . . . . . . ==> .   . . . . . .   . .
. . .  . . . . . .     .   . . . . . .   . .
. . .  . . . . . .     .   . . . . . .   . .
. . 17 . . . . . .     .   . . . . . .   . .
. . .  . . . . . .     .   . . . . . .   . .
r1245679c3<>17         r3c17<>1245679 (Hidden pair)


XY-Wing:
Code: Select all
new grid                original grid
. . 17 . . . .  . .     . . . . . . . . .
. . .  . . . .  . .     . . . . . . . . .
. . .  . . . .  . .     1-----------1 . .
                        8-----8
. . .  . . . .  . .     . . . . . . . . .
. . .  . . . .  . . ==> . . . . . . . . .
. . .  . . . .  . .     . . . . . . . . .
. . .  . . . .  . .     . . . 8-----8 . .
. . 14 . . . 47 . .     . . . . . . . . .
. . .  . . . .  . .     . . . . . . . . .
r1c7<>7                 r7c7<>1 (Some strange technique)


Y-Wing:
Code: Select all
new grid                original grid
. . 3 . . 39 .  . .     . . .  . . . . . .
. . | . . .  .  . .     . . .  . . . . . .
. . | . . .  .  . .     . . 19 . . . . . .
. . | . . .  .  . .     . . .  . . . . . .
. . | . . .  .  . . ==> . . .  . . . . . .
. . | . . .  .  . .     . . 1------------1
. . | . . .  .  . .     . . 9------------9
. . | . . .  .  . .     . . .  . . . . . .
. . 3 . . .  39 . .     . . .  . . . . . .
r1c7<>9, r9c6<>9        r7c9<>1, r6c9<>9 (Some other strange technique)


The point of this is that it would be easier to spot certain techniques (e.g. the strange-technique equivalent of XY-wing is less easily recognisable).
However, it would be a lot better if the effect of block constraints were known, so other techniques may be more easily found by this system.

Does this system have any value?
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby RW » Wed Aug 06, 2008 6:26 pm

I think I have seen some similar ideas here earlier, at least the naked subset -> fish elimination has been described here.

It is an interesting concept, that could have some value if developed a bit. Thinking practically, I don't know how many people would be doing this whole transformation manually... But it could be a nice tool to have in a solver program!:)

To tired to think about the box constraint now... gotta sleep and look at it again tomorrow.

Btw. It also brings to mind the grid transformation technique used to solve DG-sudokus.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby susume » Wed Aug 06, 2008 7:48 pm

Very cool. To see box constraints in the transformed puzzle, you could append a letter (a-h+j) to the digit in the new grid, e.g. 6e if the original clue was in the middle box. This is a bit clumsy, but may work until someone thinks of something more elegant.

Since box is a dependent variable of row & column, and these are transforming to column & digit, the box constraints will now operate on column & digit - values 456 in column 456 represent original box 5, and there will be constraints on whether they can share a row, etc.

In order to make the two grids easier to compare visually, you could leave row constant and just swap the column and digit values (or vice versa). Looking forward to more details....

susume
susume
 
Posts: 19
Joined: 03 August 2008

Postby Glyn » Wed Aug 06, 2008 8:06 pm

999_Springs
Ruud had implemented a change of coordinate views in Sudocue Version 3.1, prior to the introduction of some of Denis Berthier's nrc(t) chains in the Sudoku Beta version 3.2. You could download a copy to experiment with if you have a Windows installation.

It is also worth checking out Bob Hanson's Sudoku Assistant an early view of the grid in that way, and Allan Barker's posts on this site and at SudokuOne
Glyn
 
Posts: 357
Joined: 26 April 2007

Postby 999_Springs » Wed Aug 20, 2008 3:30 pm

How can it be proved that every elimination in the transformed grid is valid in the original grid?
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.


Return to General