Sudoku structure

Posted by Dan on Jan 27th, 2008
2008
Jan 27

These images are all from the same sudoku, except that the colors have been isolated, showing, for example, all the red squares, then all the blue squares, etc. (With a numeric sudoku, this is like showing all the ones, then all the twos, then all the threes.) Occasionally you’ll see an image of the full sudoku, with all the colors filled in.There are 46,656 different patterns for a single color, or a single digit, in a sudoku. Yes, I counted them. Yes, I have a complete list. Note that each pattern, by itself, meets the sudoku criteria:

  • Exactly one square in each row
  • Exactly one square in each column
  • Exactly one square in each 3-by-3 block

You can think of a sudoku as a sort of jigsaw puzzle. Suppose you have a box with 46,656 different pieces in it. To make a sudoku, all you have to do is find 9 of those pieces, any 9, that will fill up a 9-by-9 grid without overlapping or spilling outside the edges. Since each piece, individually, meets the sudoku criteria, any group of 9 pieces that fit together will, collectively, meet the sudoku criteria.

There are 1,046,724,517,021,560,845,728,968,107,999,437,741,056,000 different ways to pick 9 pieces from a box of 46,656. Of these, only a tiny fraction, a mere 6,670,903,752,021,072,936,960, will fit together and form a sudoku. No, I don’t have a list.

If you have a sudoku, you can turn it clockwise 90 degrees, and it’s still a sudoku, and in a sense it is the same sudoku. Or you can swap all the sevens and fives and it still has the same structure. So that 6,670,903,752,021,072,936,960 counts a lot of sudokus more than once. If you eliminate all the double counting and consider only sudokus that are structurally different, there are 5,472,730,538 different sudokus. Five and a half billion. This is a much more manageable number. It is less, for example, than the number of people on the planet. No, I don’t have a list. But I could. It would fit on a 500 gigabyte hard drive.