|
9 |
5 |
7 |
1 |
2 |
3 |
6 |
8 |
4 |
|
3 |
1 |
2 |
4 |
6 |
8 |
7 |
9 |
5 |
|
8 |
4 |
6 |
5 |
7 |
9 |
2 |
3 |
1 |
|
2 |
3 |
1 |
8 |
4 |
6 |
5 |
7 |
9 |
|
6 |
8 |
4 |
9 |
5 |
7 |
1 |
2 |
3 |
|
7 |
9 |
5 |
3 |
1 |
2 |
4 |
6 |
8 |
|
4 |
6 |
8 |
7 |
9 |
5 |
3 |
1 |
2 |
|
5 |
7 |
9 |
2 |
3 |
1 |
8 |
4 |
6 |
|
1 |
2 |
3 |
6 |
8 |
4 |
9 |
5 |
7 |
There is a lot of
information on the web about this puzzle and a lot of variations.
But one thing that seems intriguing is that this seems to be
particularly close to the classical theory of "orthogonal latin
squares". A latin square
is an array of n symbols in an n-by-n grid, with each row and each
column having all n symbols appear once and only once. The
solution to a Sudoku puzzle is such a latin square, but with additional
property that all n symbols appear once and only once in each of the
3-by-3 squares as above. Two latin squares are orthogonal if, when they are
superimposed to form a pair of symbols in each box, all n2
possibilities occur. But there is a classical connection between
n-1 orthogonal n-by-n latin squares to a finite projective plane of
order n.
So the following is a
way to understand the Sudoku-type arrays in terms of geometric
objects. Consider the field Z3 = {0, 1, 2} consisting
of three elements. Here 0 + anything = same anything.
1+1=2, 1+2=2+1=0, 2+2 = 1, 0 x anything = 0, 1 x anything = same
anything x 1 = same anything, 2 x 2 = 1. We identify each postion
in the 9-by-9 grid with four coordinates of Z3, a point in Z34.
The first coordinate determines which of the three columns of large
squares the small given box lies in. The second coordinate
determines which of the three columns of small boxes in the larger
boxes the given box lies in. The third and fourth coordinates are
similar but with rows instead of columns. The following shows
these coordinates along the outside.
22 |
|||||||||
21 |
Y |
Y |
Y |
||||||
20 |
X |
X |
X |
||||||
12 |
|||||||||
11 |
Y |
Y |
Y |
2111 |
|||||
10 |
X |
X |
X |
||||||
02 |
|||||||||
01 |
Y |
Y |
Y |
||||||
00 |
X |
X |
X |
||||||
| 00 |
01 |
02 |
10 |
11 |
12 |
20 |
21 |
22 |
A
typical cell is shown with coordinate 2111. The X squares are in
those cells, where the second coordinate is 2, and the fourth
coordinate is 0. The Y squares are in those cells with the first
coordinate equals 1 and the fourth coordinate equals 1.
Each cell in the Sudoku
grid corresponds to point in the 4-dimensional space Z34.
When some pair of coordinates are set equal to constants, the points in
Z34 they define is a 2-dimensional plane
consisting of 9 points. A column corresponds to the plane
determined by setting
the first two coordinates to constants; a row corresponds to the plane
determined by setting the second two coordinates to constants; and the
3-by-3 squares are determined by setting the first and third
coordinates to constants. The X's and Y's are also different
planes determined by setting different pairs of coordinates to
constants.
Two planes in the
4-dimensional space Z34 either coincide,
intersect in a line which has three points, don't intersect at all, or
they intersect in one point. The space Z34
is a vector space and any plane can be translated so that it intersects
the origin 0000. Then any two non-zero vectors, neither one a
multiple of the other, forms basis for the plane, and all the points in
the plane are the 9 linear combinations of the two basis vectors.
If when two planes intersect at the origin, and two basis vectors are
chosen for each, then the two planes will only intersect at the origin
if the 4 basis vectors are independant. When this happens and
each plane is translated separately, any such pair will still only
intersect at one point. When two planes intersect in a single
point, we will say that they are in general position.
So we can create a very
special sort of Sudoku solution by simply choosing a plane in Z34
that is in general position with respect to any plane determined by a
column, a row, or a square, and we might as well take the planes
through the origin 0000. Then by choosing a symbol for each
separate tranlation of that plane we get a Sudoku solution. A
basis for the column planes (where the first two coordinates are fixed)
is {0010, 0001}; a basis for the row space is {1000, 0100}; a basis for
the 3-by-3 squares is {0100, 0001}; a basis for the pattern of Y's
above is {0100, 0010}, a basis for the pattern of Y's above, but
vertically, is {1000, 0001}; and the pattern of X's above is {1000,
0010}.
So if we wish to be
ambitious and want to choose a plane that is in general position with
respect to all six of the planes above, suppose that the plane has a
basis {(a1, a2, a3, a4),
(b1, b2, b3, b4)}.
Then the condition for being in general position is that these two
vectors and any two of the four vectors, mentioned as part of the basis
vectors above for the patterns, be independent. It is easy to see
that this means that aibj-ajbi
is not zero in Z3, where i and j are not equal and
between 1 and 4. But this is the same as saying that the four
ratios ai/bi, i=1,2,3,4, are different. If
we think of infinitiy as a possible ratio, this is possible. The
following is one solution: {0121,1110}. So the
coordinates of the plane spanned by these vectors is {0000, 0121, 0212;
1110, 1201, 1022; 2220, 2011, 2102}. Put the first symbol say "1"
in the cells with those coordinates and then add arbitrary vectors to
the coordinates of those cells. This gives the other eight
symbols corresponding to the translates of the "1" plane. This is
the Sudoku pattern in the first figure above.
We can be even more
ambitious. Suppose that we choose another plane that is in
general position with respect to the first six as well as the last
plane. So we get a new set of two independent vectors such that
when combined with the a's and b's above, it remains independent.
Then when the latin square determined by this last plane is put
together with the first one, all possible ordered pairs of symbols will
appear. This will be a pair of orthogonal latin squares as
mentioned in the beginning. One such possibility is {1120,
0221}. It is easy to check that the four ratios are distinct, and
that the four vectors {0121,1110,1120, 0221} independent over the field
Z3. The plane spanned by the new pair of vectors is
{0000,1120, 2210; 0221,1011, 2101; 0112,1202,2022}. So the
orthogonal latin squares are:
|
96 |
58 |
74 |
19 |
25 |
37 |
61 |
82 |
43 |
|
32 |
13 |
21 |
48 |
64 |
86 |
75 |
97 |
59 |
|
87 |
49 |
65 |
53 |
71 |
92 |
24 |
36 |
18 |
|
23 |
31 |
12 |
84 |
46 |
68 |
57 |
79 |
95 |
|
69 |
85 |
47 |
91 |
52 |
73 |
16 |
28 |
34 |
|
78 |
94 |
56 |
35 |
17 |
29 |
42 |
63 |
81 |
|
45 |
67 |
89 |
72 |
93 |
51 |
38 |
14 |
26 |
|
54 |
76 |
98 |
27 |
39 |
15 |
83 |
41 |
62 |
|
11 |
22 |
33 |
66 |
88 |
44 |
99 |
55 |
77 |
Notice that even the
diagonals have all 9 numbers appear once and only once for both the
first and second digits. This way of creating Sudoku solutions is
very restrictive. Most Sudoku solutions will not have the extra
symmetry that is described here, even after permuting some rows or
columns. The comments here bring up several questions.
1. Are there other
solutions not obtained from planes in Z34 that
have all the symmetries described above?
2. How many solutions are there of the sort described here?
3. If some of the cells are given, is it an interesting puzzle to
determine the rest given all the symmetric patterns, as above, that
have to have all 9 numbers?
4. A seemingly unrelated question: Can you partition
Euclidean 3-space into lines where they are not all parallel?
In the spirit of Sudoku,
here is a partially filled in grid. The problem is to find a
Sudoku-type solution where all the patterns mentioned above have to
have all the numbers from 1 to 9.
| 7 |
||||||||
| 7 |
||||||||
| 6 |
||||||||
| 4 |
3 |
|||||||
| 1 |
5 |
8 |
||||||
| |
2 |
7 |
||||||
| 1 |
4 |
|||||||
| 4 |
||||||||
| 1 |
I am reasonably sure
that there is only one solution.
The following are some
links that I found that are interesting. Enjoy.