At 03:36 PM 5/1/2006, Henry Baker wrote:
I did a Google search on "sudoku" and "direct product", but didn't come up with anything interesting.
Since 9=3*3, isn't it possible that at least some Sudoku's are direct product constructions?
Aren't at least some Sudoku's the product table of a 9-element group?
To answer my own question, the answer is probably "no", at least if group tables are considered. Since each of the subsquares has to have all 9 elements, none of the subsquares can be the product table for a subgroup, because the subgroup must be closed. However, I was able to go backwards -- take the straightforward direct product of Z3xZ3, whose product table is (you'll have to mentally relable i with i-1 to see that this is Z3xZ3): [ 1 2 3 4 5 6 7 8 9 ] [ 2 3 1 5 6 4 8 9 7 ] [ 3 1 2 6 4 5 9 7 8 ] [ 4 5 6 7 8 9 1 2 3 ] [ 5 6 4 8 9 7 2 3 1 ] [ 6 4 5 9 7 8 3 1 2 ] [ 7 8 9 1 2 3 4 5 6 ] [ 8 9 7 2 3 1 5 6 4 ] [ 9 7 8 3 1 2 6 4 5 ] If you then "mix" the columns, by taking the 1st, 4th, 7th, 2nd, 5th, 8th, and then 3rd, 6th, 9th columns (BTW, "mix" is its own inverse), you get: [ 1 4 7 2 5 8 3 6 9 ] [ 2 5 8 3 6 9 1 4 7 ] [ 3 6 9 1 4 7 2 5 8 ] [ 4 7 1 5 8 2 6 9 3 ] [ 5 8 2 6 9 3 4 7 1 ] [ 6 9 3 4 7 1 5 8 2 ] [ 7 1 4 8 2 5 9 3 6 ] [ 8 2 5 9 3 6 7 1 4 ] [ 9 3 6 7 1 4 8 2 5 ] This matrix now satisfies the Sudoku criteria. It also has a very simple structure. I now wonder how many (what % of) sudoku squares can be generated from the direct product of two 3-element groups, followed by some sort of "mix"-ing operation, such as the one above.