Sudoku: Creating Identity Boards

I’m building a Sudoku generator. There’s just enough wicked math in there to make things interesting. One thing that caught my attention was that there is a sort of “identity” board that you should be able to build for any dimension of sudoku. For the standard 3×3 matrix, it looks like this:

+------+------+------+
| 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 1| 5 6 4| 8 9 7|
| 5 6 4| 8 9 7| 2 3 1|
| 8 9 7| 2 3 1| 5 6 4|
+------+------+------+
| 3 1 2| 6 4 5| 9 7 8|
| 6 4 5| 9 7 8| 3 1 2|
| 9 7 8| 3 1 2| 6 4 5|
+------+------+------+

The way you write an identity board is this: You write the digits 1..9 in order in the top left sector and across the top line of the puzzle. If you look at it in terms of triplets, however, you build the top line by copying the 2nd triplet row (4 5 6) and then the 1st triplet row (7 8 9) across the top line.

The second row starts with (4 5 6) so you naturally continue with (7 8 9) in the next sector, and then roll around to the beginning to end with (1 2 3). The third row then follows naturally: (7 8 9) (1 2 3) (4 5 6).

You can build the entire board this way if you do the same thing vertically. Copying the first sector’s columns down the board’s first column, you get (1 4 7), (2 5 8), (3 6 9). Do this across the entire board and you end up with the completed puzzle.

The really neat part of this for me is that it works with any dimension of sudoku. For example, here’s a 2×2 and a 4×4 identity board built the same way:

+-----+-----+
| 0 1 | 2 3 |
| 2 3 | 0 1 |
+-----+-----+
| 1 0 | 3 2 |
| 3 2 | 1 0 |
+-----+-----+

+---------+---------+---------+---------+
| 0 1 2 3 | 4 5 6 7 | 8 9 A B | C D E F |
| 4 5 6 7 | 8 9 A B | C D E F | 0 1 2 3 |
| 8 9 A B | C D E F | 0 1 2 3 | 4 5 6 7 |
| C D E F | 0 1 2 3 | 4 5 6 7 | 8 9 A B |
+---------+---------+---------+---------+
| 1 2 3 0 | 5 6 7 4 | 9 A B 8 | D E F C |
| 5 6 7 4 | 9 A B 8 | D E F C | 1 2 3 0 |
| 9 A B 8 | D E F C | 1 2 3 0 | 5 6 7 4 |
| D E F C | 1 2 3 0 | 5 6 7 4 | 9 A B 8 |
+---------+---------+---------+---------+
| 2 3 0 1 | 6 7 4 5 | A B 8 9 | E F C D |
| 6 7 4 5 | A B 8 9 | E F C D | 2 3 0 1 |
| A B 8 9 | E F C D | 2 3 0 1 | 6 7 4 5 |
| E F C D | 2 3 0 1 | 6 7 4 5 | A B 8 9 |
+---------+---------+---------+---------+
| 3 0 1 2 | 7 4 5 6 | B 8 9 A | F C D E |
| 7 4 5 6 | B 8 9 A | F C D E | 3 0 1 2 |
| B 8 9 A | F C D E | 3 0 1 2 | 7 4 5 6 |
| F C D E | 3 0 1 2 | 7 4 5 6 | B 8 9 A |
+---------+---------+---------+---------+

The neatness of this pleased me, but when I tried to implement it in code it got hopelessly complicated very fast. On the drive home from work last week, I found an elegant mathematical function to produce this board. Can you guess it? I’ll post it tomorrow. If you can’t wait, dig around in my twitter feed–the entire function is less than 72 characters.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s