Making a(ll) Sudoku(s)

So it turns out Sudokus are pretty fun, who knew.¹ If you read a bit about their history on Wikipedia, you’ll find out that they’re not actually a Japanese invention but were invented by an American guy in the 80s.

A quick recap of the basics: You get a grid of 9x9² squares, each can hold one number between 1 and 9. Each row and column should have all numbers between 1 and 9 exactly once, the same goes for the nine 3x3 grids that the main grid is also seperated into. As a start, you get a bunch of numbers, you are supposed to fill in the rest yourself. That is the fun part.

So I was wondering who actually creates these sudokus and how they do it. Back on the Wikipedia page, it says that in 2003 a Hong Kong judge introduced sudokus back to the Western world with a computer program to efficiently calculate puzzles that took him six years to develop. That sounds complicated. Without looking at his solution, let’s see how efficient we can get.

Now, one important observation first: there is a finite number of sudokus out there. The grid has a static size of only 9x9 and only 9 numbers are possible for each field. That leads to a 9 to the power of 81 possible combinations, or about… 2 with 77 zeros at the end. That’s quite a lot of combinations. That is our upper limit: finite, but a lot.

But thankfully we have a bunch of restrictions that we can consider. Let’s go row by row, first. Remember, a row can only cont For the first row, we start with 9 possible numbers in the first cell, then 8 in the next, 7 in the one after that, and so on. That makes 9! (9 faculty) possible rows. And we have nine of them in each puzzle, making 9! to the power of 9 our new limit, 1 with 50 zeroes. Now, that’s a lot more reasonable. Kind of. Let’s take a break to solve a sudoku and then get back to writing.

Ok, I’m done. That took a while. Anyway, here is another observation that could help us: if you take a valid, finished sudoku and switch around all 1s with 9s and vice versa, you still have a valid sudoku. The same goes for switching 1s with 8s, 7s with 2s, etc. There is no inherit ordering in those numbers, they are merely symbols. You could also use letters A to I or greek letters or mix letters and numbers and mathematical symbols. As long as every symbol appears only once in each row, column, and subsquare, we’re fine. So a sudoku always follows a pattern, and numbers are placed into it. Let’s call these patterns the sudoku’s archetype because that’s the name that I just made up. If we take our 1 with 50 zeroes possible (and impossible - remember, we didn’t apply any of the constraints yet) sudokus, we can further divide them by the number of switcharoos we can make: I can switch out all 1s with 1 to 9, then 2s with 2 to 9 and so on, leaving us with 9! (9 faculty.. again?) variations of the same archetype, which means there are only (9!^9)/9! archetypes, which is 9! to the power of 8, or 3 with 44 zeroes. Already a lot less, I guess. Still too many to reasonably brute-force. Hm. I can see why the efficient algorithm took six years.

Let’s take another step. Given a row X that starts with a number n from 1-9, the next row can only start with a number n' ≠ n. The row after that can only start with a number n'' ≠ n' and n'' ≠ n. So for the second row, we lose 8! possible rows, for the third we lose another 8! and so on, until the last row can only start with a single possible number, which means that there are only 8! possibilities for that last row. This leaves us with the following number of possible sudokus (which we can later reduce to the number of archetypes):

(9! - 0x8!) x (9! - 1x8!) x (9! - 2x8!) x … (9! - 8x8!)

Or, in written another way:

product 9! - (n-1)x8!, n=1…9

A number that has only 47 zeroes. Divide that again by 9! and we get down to 41 zeroes!

Of course, we can do this for all columns. The second cell of the first column has 8 possible numbers, the one after that has 7 possible numbers (can’t be the one above and not the one in the first column, second row, and can’t be the one in the top left corner, because that would break the rule of the subsquares having every number exactly once, until we get to a border between subsquares,…). Wait, this is getting complicated. Ugh, math. What a thing to do on a Sunday afternoon. I’m confused.

Okay, I think there’s another way we can describe it: to fill a cell, we need to first look at three things. First, the numbers above that cell, the ones in the column we have already filled. Second, the numbers to the left of that cell, the ones we have already filled here. And third, the numbers we have already put in the subsquare of that cell. These numbers can overlap, but don’t have to. All of these leave us with a set of possible entries for that field. And now we consider only the size smallest set of all of these. I’m too confused to write that down properly, let’s just calculate it.

package main

import "fmt"

func main() {

    /*
    *
    * Our grid is a 9x9 field of numbers:
    * for every cell, we want to know the
    * amount of possible numbers.
    *
     */
    output := "Possibilities:\n"
    output += "    1   2   3   4   5   6   7   8   9  \n"
    output += "---------------------------------------\n"
    total := 1

    for i := 0; i <= 8; i++ {
        output += fmt.Sprintf("%d |", i+1)
        for j := 0; j <= 8; j++ {
            // first, the number of numbers above that field:
            numAbove := 9 - j
            min := numAbove

            // then, the number of numbers to the left of that field:
            numLeft := 9 - i

            if numLeft < min {
                min = numLeft
            }

            // finally, the number of numbers within the subsquare:
            // as we write from left to right, we consider a subsquare
            // as three rows that we fill out like this:
            //       - col0 - col1 - col2
            // row0  -   0  -   1  -   2
            // row1  -   3  -   4  -   5
            // row2  -   6  -   7  -   8
            // so to calculate the index, just take:
            // row_n * 3 + col_n

            subSqRow := i % 3
            subSqCol := j % 3
            subSq := 9 - ((subSqRow * 3) + subSqCol)

            if subSq < min {
                min = subSq
            }

            output += fmt.Sprintf(" %d |", min)
            total = total * min
        }
        output += "\n"
    }

    output += fmt.Sprintf("Total: %d\n", total)

    print(output)
}

And we get the following output:

Possibilities:
    1   2   3   4   5   6   7   8   9
---------------------------------------
1 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
2 | 6 | 5 | 4 | 6 | 5 | 4 | 3 | 2 | 1 |
3 | 3 | 2 | 1 | 3 | 2 | 1 | 3 | 2 | 1 |
4 | 6 | 6 | 6 | 6 | 5 | 4 | 3 | 2 | 1 |
5 | 5 | 5 | 4 | 5 | 5 | 4 | 3 | 2 | 1 |
6 | 3 | 2 | 1 | 3 | 2 | 1 | 3 | 2 | 1 |
7 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 1 |
8 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
9 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Total: 4880492422162808832

That’s about 18 zeroes.³ Still a lot, but manageable. Divided by 9! to get the number of archetypes makes about 13 zeroes.

Of course, there are a bunch of other optimizations still left. Here, we consider only one of the sources cells above, cells to the left, and cells in this sub-square as limiting the set of possible entries for a particular cell. But of course, it is all of these sources combined that determine this limit. But that isn’t that easy, since these sets aren’t necessarily distinct.

But even with 13 zeroes as an upper limit for generating all sudokus, if every sudoku was only a 100 bytes, we’d need a petabyte of storage to store all of them. Take that times 9! to store all sudokus. And that times who-knows-what to store all the possible sudoku quizzes, which have almost all of the numbers missing.

So that makes my plan of generating all sudokus impossible.⁴ Let’s write a sudoku generator anyway, but generate only one sudoku.

There are two steps to generating a sudoku the primitive way: First, generate a 9x9 grid of numbers where each cell follows the sudoku rule. Second, hide almost all of those numbers.⁵

Ok, I tried to write it the primitive way but it’s much harder than I anticipated. Selecting a possible number at random and then marking this number impossible in this row and column and sub-square, then moving on to the next cell and repeating that process (but only using the set of possible numbers) doesn’t really work. It always fails somewhere in the seventh row or so because we’re running out of numbers.

It’s getting a bit late for my taste, so I’ll go read about how that Hong Kong dude did it.

Ok, wow, what the hell. This is terribly complicated and I got a lot wrong I guess. Apparently, there is a need for at least 17 clues for a sudoku. I did not see that coming, but this paper actually proves it. Then, there are only 6.67×10 with 21 zeroes possible complete sudoku grids. That’s way more than I thought it would be. But with symmetry taking into account, it’s only 5,472,730,538, which is a terribly small set.

This article also summarizes sudoku generation a bit. Most keep their generation algorithms secret, however, as they make their money that way.

But sometimes we fail, I guess.