Sudoku Variants

I’m finally starting to think about sudoku, and am having a lot of fun with it.

I’m taking an online class on artificial intelligence with udacity, and sudoku is being used to illustrate some ideas used to solve constraint satisfaction problems.

Naturally, before solving sudoku puzzles by using the algorithms described in the online course, I thought about what I could do with a brute force approach, which naturally led me to think about variants of sudoku where brute force is a feasible approach. And that’s what I’ll write about here.

But first, let’s recap the basics. To begin with, what is sudoku?

It’s a puzzle that was popularized about thirty years ago in Japan. The word “sudoku” is Japanese (数独) and means “single number”: “su” means number and “doku” means single.

It’s a puzzle that involves a grid of grids, namely a 3 by 3 grid where each cell is itself a 3 by 3 grid (i.e. a sub grid), so that ultimately we have a 9 by 9 super grid. There are various ways of placing the 9 numbers 1, 2, 3, 4, 5, 6 , 7, 8, 9 in each 3 by 3 sub grid (without repetitions) so that the columns and rows of the 9 by 9 super grid each have no repetitions.

A sudoku puzzle takes a partially filled super grid as input and asks for a filled super grid as output.

As you might guess, there’s nothing special about the number 3, and we could just as easily do all of the above with the number 2, with the only change being that the 9 numbers from 1 to 9 are replaced with the 4 numbers 1, 2, 3, 4 To make the discussion easier, I’ll continue for a while with the 2 by 2 variant of sudoku, instead of the 3 by 3 classic sudoku that everyone knows.

An example of a 2 by 2 sudoku puzzle would be

4 3
2 1
3
2

and a solution (actually the only solution) would be

4 1 2 3
3 2 4 1
1 4 3 2
2 3 1 4

For programming purposes, I’m going to encode the puzzle as a sequence of 16 characters that correspond to scanning the 4 by 4 super grid from left to right and top to bottom. That results in the sequence

4..3...1..3.2...

where the missing numbers are indicated by a period.

A similar encoding is done for the solution, namely

4123324114322314

With that in mind, let’s consider a simple brute force approach to solving the puzzle.

Given an input sequence s, for example “4..3…1..3.2…”, the first step would be to construct the collection of all possible filled super grids F The second step would be to consider every element f of F in turn, and check to see if f and s are the same if we ignore the periods in s If we find such an f we can stop with a solution f And if we don’t find an f after going through F, then there is no solution.

It’s pretty straightforward, and a nice little implementation bonus is that we can use the input as a regular expression pattern, since a period represents any character in regular expressions.

To see how feasible this might be, let’s try to get some idea of how large F might be.

An elementary upper bound \#(F) \leqslant 4^{16} \approx 10^9 holds because each of the 16 entries in the super grid is restricted to 4 possibilities. This is something that computers can handle, and it looks like a brute force approach will work.

Note that for “classic” sudoku, the corresponding upper bound is {9}^{81} \approx {10}^{77} which is not something that computers can handle.

And, we can do much better than that. By considering just the upper left sub grid, there are 24 = 4! possibilities. A neighboring sub grid is then restricted to 4 =(2\cdot 1 \cdot 2!) values, so that we have an upper bound of 24\cdot 4^3 = 1536 There’s now no question: this can be done by brute force.

It’s easy enough to code this up, find all the elements of F, and count them to get 288. I did just that and you can see the code on github. Just execute “python list_all_22.py | wc -l” at the command line to get 288. It takes 0.039 seconds on my computer.

And, of course, I’m not the first person who’s been down this road. This result is well known, and can be seen at numerous places, including wikipedia.

To finish up this post, I’d like to mention a few related items.

Firstly, the same reasoning I used to find a a bound of 1536 in the 2 by 2 case can be used to find a bound of 9!(6 \cdot 5 \cdot 4 \cdot 6!)^3 (3!3!3!)^5 \approx 10^{32} for the 3 by 3 case. And, the actual value of \#(F) in the classic 3 by 3 case is known: it’s 6670903752021072936960 \approx 10^{22} Brute force isn’t going to cut it.

Secondly, generalized sudoku super grids are square, but the sub grids can be rectangular. An m by n sudoku consists of a super grid of mn rows and mn columns using the mn numbers 1, 2, 3 \ldots mn. The super grid is viewed as an m by n grid where each cell is an n by m sub grid. The case where m=1 is the case of n by n latin squares, which have been studied in mathematics for over two centuries. Sudoku is a fairly recent puzzle, but it’s not completely without precedent.

Thirdly, 2 by 2 sudoku puzzles are out there. One source is at worksheets.com

Finally, a big shout out to udacity. I’ve had an account there for five years, have tried out a number of their courses, and am very impressed with their quality.

Author: Walter Vannini

Hi, I'm Walter Vannini. I'm a computer programmer and I'm based in the San Francisco Bay Area. Before I wrote software, I was a mathematics professor. I think about math, computer science, and related fields all the time, and this blog is one of my outlets. I can be reached via walterv at gbbservices dot com.

Leave a Reply

Your email address will not be published.