Saturday, June 06, 2009

Determinant sudoku

Some friends of mine have trouble finding sufficiently difficult sudoku puzzles to keep them occupied. So one day while daydreaming I came up with Determinant Sudoku, in which you take the determinant of each square within a valid sudoku and make a super-square in which no row or column repeats a determinant.

In base-4 sudoku, such a Determinant Sudoku is a grid of 12x12 numbers, not too much larger than a base-10 ordinary sudoku. But I wasn't sure if any valid base-4 Determinant Sudoku actually existed, so I wrote a program to help me check.

I did manage to construct a valid base-4 Determinant Sudoku, but I'm not sure how many others exist.

Here is the source code to enumerate all base-4 sudoku and print their determinants, and I've copied the comment header below which includes more explanation and the base-4 determinant sudoku I found:


// This program enumerates all the base-4 sudoku and calculates
// their determinants.
//
// The idea is this: start with base-4 sudoku, so that you get
// 2x2 squares which have the numbers 0,1,2,3 with none repeated.
// Create a 2x2 grid of those 2x2 squares, so that each row and column
// has the numbers 0,1,2,3. (Ordinary sudoku, but 4x4 instead of 9x9).
//
// Here's an example of a valid base-4 sudoku:
// 01 23
// 23 01
//
// 10 32
// 32 10
//
// There appear to be 288 distint base-4 sudoku, without removing isomorphisms.
//
// My idea was to take the determinant of each of those 2x2 matrices and create
// a "determinant sudoku".
//
// In matrix math, the determinant of
// a b
// c d
// is a*d - b*c.
//
// There are six possible determinants of the 2x2 blocks.
//
// To construct a base-4 determinant-sudoku, make a 3x3 grid of 4x4 base-4
// sudoku blocks. There will be six rows and six columns of 2x2 squares.
//
// How many base-4 determinant-sudoku blocks exist?
// This program almost answers that question, but not quite.
//
// Of the 288 base-4 sudoku, 168 have the same determinant, leaving 120
// base-4 sudoku that could contribute to a base-4 determinant-sudoku.
//
// I constructed one base-4 determinant-sudoku by hand:
//
// 01 23 | 01 32 | 02 31
// 23 01 | 32 01 | 31 02
// | |
// 10 32 | 10 23 | 20 13
// 32 10 | 23 10 | 13 20
//
// ----------------------
//
// 01 32 | 02 31 | 01 23
// 32 01 | 31 02 | 23 01
// | |
// 10 23 | 20 13 | 10 32
// 23 10 | 13 20 | 32 10
//
// ----------------------
//
// 02 31 | 01 23 | 01 32
// 31 02 | 23 01 | 32 01
// | |
// 20 13 | 10 32 | 10 23
// 13 20 | 32 10 | 23 10
//
//
// Determinants:
//
// -2 2 -3 3 -6 6
// 2 -2 3 -3 6 -6
//
// -3 3 -6 6 -2 2
// 3 -3 6 -6 2 -2
//
// -6 6 -2 2 -3 3
// 6 -6 2 -2 3 -3
//
// Each 4x4 block is a valid base-4 sudoku. And the 6x6 grid of 2x2 blocks
// has no repeated determinants in any row or column.
//
// (This base-4 determinant sudoku isn't very nice, since it repeats the
// same 3 base-4 sudoku 3 times each.)
//
// So the question remains open: how many base-4 determinant sudoku are there?

No comments: