Equivalence of puzzles

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

Equivalence of puzzles

Postby Smythe Dakota » Thu Nov 23, 2006 1:43 am

It is well known that two Sudokus (either completed grids or partially filled-in puzzles) can be considered equivalent if one grid can be obtained from the other by a series of zero or more of the following maneuvers:
__________________________

A. Interchange any two complete rows within the same band.

B. Interchange any two complete columns within the same stack.

C. Interchange any two complete bands.

D. Interchange any two complete stacks.

E. Rotate the puzzle 90 degrees.

F. Replace each digit with its image under some one-to-one correspondence of the set {1,2,3,4,5,6,7,8,9} onto itself.
__________________________

Any other type of equivalence (such as horizontal, vertical, or diagonal reflection) can be achieved with a combination of the above.

Now let's step down a bit and look at Latin squares. (A 9x9 Latin square is just a Sudoku without the boxes.) Two 9x9 Latin squares (either completed grids or partially filled-in puzzles) can be considered equivalent if one grid can be obtained from the other by a series of zero or more of the following maneuvers:
__________________________

N. Interchange any two complete rows.

O. Interchange any two complete columns.

P. Rotate the puzzle 90 degrees.

Q. Replace each digit with its image under some one-to-one correspondence of the set {1,2,3,4,5,6,7,8,9} onto itself.
__________________________

But now I propose two more (for Latin squares):
__________________________

R. Interchange rows with digits.

S. Interchange columns with digits.
__________________________

By interchanging columns with digits, for example, I mean that if rXcY contains the digit Z in the first puzzle, then rXcZ would contain the digit Y in the second puzzle.

To see that such interchanges indeed result in equivalent Latin squares, consider the set BIGTHING of all triples (X,Y,Z) where each X,Y,Z is a digit 1 through 9. There are 729 (9x9x9) elements in this set. A valid Latin square is a subset LITTLETHING of BIGTHING such that:

1. No two distinct elements of LITTLETHING have the same first and second coordinates, and

2. No two distinct elements of LITTLETHING have the same first and third coordinates, and

3. No two distinct elements of LITTLETHING have the same second and third coordinates.

If LITTLETHING has 81 elements, it represents a completed Latin square grid. If it has fewer than 81 elements, it represents a partially filled-in puzzle.

If you consider the first coordinate to represent the row, the second to represent the column, and the third to represent the digit, then the above conditions are equivalent, respectively, to:

1. There can be at most one digit in each cell.

2. No two cells in the same row can have the same digit.

3. No two cells in the same column can have the same digit.

Since the set-of-ordered-triples definition of Latin square is symmetric in its handling of the three coordinates, it follows that any two of them (e.g. columns and digits) can be interchanged, and the result will still be a valid Latin square.
__________________________

Now that I've convinced everybody, let me ask the big question:

Can something like this be done with full Sudokus (recognizing the boxes also)? i.e. is there some way of defining row-digit and column-digit interchanges that can create a new type of equivalence for Sudokus, or does it work only for Latin squares?

Bill Smythe
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006

Re: Equivalence of puzzles

Postby Smythe Dakota » Tue Nov 28, 2006 9:55 am

No responses, even after 5 days?

I've sort of answered my own question, though.

In my first post I equated 9x9 Latin squares with triples (X,Y,Z), where each of X,Y,Z is a digit from 1 to 9. X represents the row, Y the column, and Z the digit. For example, if r3c5 contains the digit 8, then (3,5,8) would be a member of the subset of (up to 81) triples which represents the puzzle.

I then pointed out that by interchanging, for example, the Y and Z coordinates, you could effectively interchange columns with digits, thus generating a new (equivalent) Latin square.

To do this with full Sudokus, you would instead need to use sextuples (U,V,W,X,Y,Z), where each of U,V,W,X,Y,Z is a digit from 1 to 3. U represents the band, V is the row number within the band, W is the stack, X is the column number within the stack, and Y and Z represent the digit. Specifically, Y is the "digit chute" (chute 1 = digit 1,2,3, etc) and Z is the "digit cell" (cell 1 = digit 1,4,7, etc).

With this definition, a valid Sudoku is a set LITTLETHING of (up to 81) such sextuples, subject to the following rules:
______________________________

1. No two distinct elements of LITTLETHING have the same first through fourth coordinates (U,V,W,X), and

2. No two distinct elements of LITTLETHING have the same first, second, fifth, and sixth coordinates (U,V,Y,Z), and

3. No two distinct elements of LITTLETHING have the same third, fourth, fifth, and sixth coordinates (W,X,Y,Z), and

4. No two distinct elements of LITTLETHING have the same first, third, fifth, and sixth coordinates (U,W,Y,Z).
______________________________

These correspond, respectively, to the standard Sudoku rules:

1. There can be at most one digit in each cell.

2. No two cells in the same row can have the same digit.

3. No two cells in the same column can have the same digit.

4. No two cells in the same box can have the same digit.
______________________________

Right away we see that interchanging rows with digits (or columns with digits), which was so easy with 9x9 Latin squares, doesn't work with full Sudokus. There isn't the same symmetry among the rules for rows, columns, and digits as is the case with Latin squares.

But suppose we replace rule 4 with the following:
______________________________

4a. No two distinct elements of LITTLETHING have the same first, third, fourth, and fifth coordinates (U,W,X,Y).
______________________________

This is equivalent to replacing the 4th Sudoku rule (box rule) with the following:

4a. No two cells in the same mini-column (3-cell column within a box) can have digits in the same "digit chute".
______________________________

For example, a box containing

1 4 6
2 3 8
5 7 9

would be illegal, because 1 and 2 are in the same "digit chute" (and so are 8 and 9), but a box containing

1 4 7
4 7 1
7 1 4

would be OK, despite all the repetitions, because 1,4,7 are each in different "digit chutes".

If we call this variation Smythedoku, then there is a one-to-one correspondence between valid Sudoku grids (either complete grids or partial grids) and valid Smythedoku grids (either complete grids or partial grids). Just interchange coordinates W,X with coordinates Y,Z (respectively) in the above-mentioned (U,V,W,X,Y,Z) setup, to achieve this correspondence.

Does this give anybody any ideas (of ANY kind:) )?

Bill Smythe
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006

Re: Equivalence of puzzles

Postby tarek » Tue Nov 28, 2006 11:17 am

This needs a bit of thoughtwith some strong coffee

Smythe Dakota wrote:For example, a box containing

1 4 6
2 3 8
5 7 9

would be illegal, because 1 and 2 are in the same "digit chute" (and so are 8 and 9), but a box containing

1 4 7
4 7 1
7 1 4

would be OK, despite all the repetitions, because 1,4,7 are each in different "digit chutes".


I'm just thinking about this in reverse........ A valid vanilla sudoku is actually a valid Latin square.....

How could you take one box which looks perfectly fine to me & say that it is illegal ?

If I take one box on its own, I could permute the digits (or symbols) to any other digits keeping the vanilla sudoku rules & therefore also keeping the Latin square rules, that includes your illegal box

tarek
User avatar
tarek
 
Posts: 3762
Joined: 05 January 2006

Postby Smythe Dakota » Sun Dec 03, 2006 2:18 am

Here's another way to look at it.

Think of a valid 9x9 Latin square (a Sudoku without the boxes) to be a 9x9x9 cube. Instead of digits, there are marbles in a few (up to 81) of the 729 cells. The rest of the cells are empty. Each row, column, and shaft (in a completed puzzle) contains one and only cell with a marble.

To see that this is the same thing, just map the original 9x9 Latin square to a new 9x9x9 model in the following way. If the digit Z appears in rXcY of the 9x9 puzzle, place a marble in the 9x9x9 cube at rXcY level Z.

Since, in the 9x9x9 model, there is complete symmetry among the three dimensions (each line in each of the three dimensions contains only one marble), it follows that rows and columns, or rows and shafts, or columns and shafts, can be interchanged without affecting the validity of the puzzle.

But now, when you add the Sudoku box concept, the symmetry is broken. You now have nine 3x3x9 "tubes" with the additional constraint that no two of the nine shafts in any tube can contain more than one marble at the same level.

Bill Smythe
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006


Return to General