The New Sudoku Players' Forum

[RW]

How many essentially different (non-isomorphic) such puzzles are there?

201105135151764480 possible grids. I'm not sure if the number of essentially different DG grids has been calculated.

RW

[Smythe Dakota]

Now, can we go even further, and not only interchange rows, columns, boxes, and plums, but also digits? ....

.... A 9x9 latin square can be viewed in another way, as well -- as a subset L of the set T of all ordered triples (x,y,z) .... To translate the standard view of a latin square to this ordered-triple view, just consider the triple (x,y,z) to be in L if and only if, in the traditional view, the cell at row x, column y contains the digit z. ....

If we throw in boxes and/or plums, and still wish to retain three-way row-column-digit interchangeability, we must abandon ordered triples of 1-9 and instead go for ordered 6-tuples of 1-3.

The translation would be as follows: In the 6-tuple (u,v,w,x,y,z):

u is the band number 1-3.
v is the row number 1-3 within the band.
w is the stack number 1-3.
x is the column number 1-3 within the stack.
y is the high component 1-3 of the digit.
z is the low component 1-3 of the digit.

In the 6-tuple view of life, the subset L would contain the 6-tuple (u,v,w,x,y,z) if and only if, in the traditional view, the cell at row (u,v), column (w,x) contains the digit (y,z).

To explain high and low components of digits, each digit 1-9 would be divided into its high and low components as follows:

1 becomes (1,1)
2 becomes (1,2)
3 becomes (1,3)
4 becomes (2,1)
5 becomes (2,2)
6 becomes (2,3)
7 becomes (3,1)
8 becomes (3,2)
9 becomes (3,3)

For a vanilla sudoku, the constraints on our subset L would be:

A. No two distinct elements of L can have the same 1st, 2nd, 3rd, and 4th coordinates. (Translation: No cell can contain more than one digit.)

B. No two distinct elements of L can have the same 1st, 2nd, 5th, and 6th coordinates. (Translation: No digit can appear twice in the same row.)

C. No two distinct elements of L can have the same 3rd, 4th, 5th, and 6th coordinates. (Translation: No digit can appear twice in the same column.)

D. No two distinct elements of L can have the same 1st, 3rd, 5th, and 6th coordinates. (Translation: No digit can appear twice in the same box.)

-- And, if we also throw in the plum constraint:

E. No two distinct elements of L can have the same 2nd, 4th, 5th, and 6th coordinates. (Translation: No digit can appear twice in the same plum.)

But D and/or E create asymmetries which prevent us from generating equivalent puzzles by interchanging rows and digits, or columns and digits. The 5th and 6th coordinates always "stick together", i.e. in each constraint, either both appear, or neither appears. Not so with the 1st and 2nd coordinates, or with the 3rd and 4th.

To attempt to restore row-digit or column-digit interchangeability (which existed in latin squares, i.e. before constraint D and/or E was added), we'd need more constraints, such as:

F. No two distinct elements of L can have the same 1st, 3rd, 4th, and 5th coordinates. (Translation: Within any mini-column (3-cell column within a box), no two digits can have the same high component.)

G. No two distinct elements of L can have the same 2nd, 3rd, 4th, and 6th coordinates. (Translation: Within any plum-column (3-cell column within a plum), no two digits can have the same low component.) (Example of a plum-column: r1c1, r4c1, r7c1.)

H. No two distinct elements of L can have the same 1st, 2nd, 3rd, and 6th coordinates. (Translation: Within any mini-row (3-cell row within a box), no two digits can have the same low component.)

J. No two distinct elements of L can have the same 1st, 2nd, 4th, and 5th coordinates. (Translation: Within any plum-row (3-cell row within a plum), no two digits can have the same high component.) (Example of a plum-row: r1c1, r1c4, r1c7.)

NOW, have we achieved enough symmetry? The "sticking together" asymmetry has been removed. For example, the 5th and 6th coordinates both appear in (and only in) constraints B, C, D, E. The 1st and 2nd coordinates both appear in (and only in) constraints A, B, H, J. The 3rd and 4th coordinates both appear in (and only in) constraints A, C, F, G.

So, with any luck, with all of the above constraints in place, it should be possible to come up with equivalent "super-constrained" sudokus by interchanging, for example, rows with digits. In grid X, row (u,v) column (w,x) would contain the digit (y,z) if and only if, in grid Y, row (y,z) column (w,x) contains the digit (u,v).

Anybody care to try this?

Bill Smythe

[udosuk]

I think dukuso has done something along these lines 18 months ago:

http://forum.enjoysudoku.com/viewtopic.php?t=2151

[Smythe Dakota]

Of course, with so many constraints, the total number of valid grids is greatly reduced. In addition, the number of ways two grids can reasonably be considered isomorphic greatly increases. Thus, there is a danger that the number of isomorphic puzzles may become equal to the number of valid puzzles, i.e. that the number of isomorphism classes will become 1, i.e. that there is essentially only one solution.

The following "generic grid" satisfies all nine of the constraints (A-J) in my earlier post:

Code: Select all

1  2  3     4  5  6     7  8  9
4  5  6     7  8  9     1  2  3
7  8  9     1  2  3     4  5  6

2  3  4     5  6  7     8  9  1
5  6  7     8  9  1     2  3  4
8  9  1     2  3  4     5  6  7

3  4  5     6  7  8     9  1  2
6  7  8     9  1  2     3  4  5
9  1  2     3  4  5     6  7  8

Would anyone care to investigate whether this is essentially the ONLY solution, i.e. whether any grid satisfying all the constraints is isomorphic (in some reasonable sense) to the above?

Bill Smythe

[Smythe Dakota]

Of course, with so many constraints, the total number of valid grids is greatly reduced. In addition, the number of ways two grids can reasonably be considered isomorphic greatly increases. ....

Oops, I just realized the last sentence above may not be true. For example, with the plum constraint added to a vanilla sudoku, interchanging two complete rows within a band will no longer generate an additional valid grid.

Bill Smythe

[Drjsguo]

Great job! This is certainly a super constrained Sudoku, no doubt about it.

However I do not think it is the only one of it kind. Will you agree the following is another solution?

9,1,2,3,4,5,6,7,8
3,4,5,6,7,8,9,1,2
6,7,8,9,1,2,3,4,5
7,8,9,1,2,3,4,5,6
1,2,3,4,5,6,7,8,9
4,5,6,7,8,9,1,2,3
8,9,1,2,3,4,5,6,7
2,3,4,5,6,7,8,9,1
5,6,7,8,9,1,2,3,4

By applying Dieluohan Big Bang theorem (www.chinasudoku.com) we get many other solutions. Same thing is true if the high or low digits are randomly shuffled among themselves. Simultaneously perform six rows or six columns exchange so that row, column, box, and plum restrictions are still remaining intact, is another ways to get a complete different solution. Switching bands or stacks gets similar result.

I found several Jia Zi (甲子, means 60 years in Chinese, I borrow this name for the total of 60 all 9-digits constrains) Sudokus (www.chinasudoku.com) with row, column, box, plum, San, Chuan, and diagonal constrains. Jia Zi Sudoku requires minimum 8 clues to solve.

I wonder if you could include an additional diagonal variable in your model. Diagonal constrain is a powerful limitation which denies all possible row, column, box, and plum exchanges. This approach may enable us finding the biggest “super constrained” Sudoku.

I am not optimistic for finding a single solution Sudoku without adding one most important factor, i.e. an “orderly arrangement” as a condition. However, an orderly arrangement, such as the construction of nine rows into a single number to be the greatest, by itself is already enough to build a unique Sudoku without a clue.

Drjsguo 5-24-2007