Solving Sudokus

I’ve just (re)discovered the need to code up sudoku puzzles for a Project Euler question. For those who don’t know, a sudoku is a 9×9 grid of numbers that is said to be ‘solved’ when each row, column and 3×3 ‘box’ contains the numbers 1-9 exactly once. This article is about developing an efficient but simple sudoku-solving algorithm in Python. I also talk about the relative merits of logic-based and brute-force approaches.

Setting Up the Problem

I have a text file (‘sudokus.txt’) containing 50 sudoku grids that need solving, in the following format (zeroes denote uncompleted cells):

Grid 01
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
Grid 02
200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003
etc…

I started by writing a ‘parser’ function using a regular expression to separate out these grids into strings of 81 numbers. Each grid is then passed to a ‘solve’ function which, as yet, does nothing. Here is the code:

import re

def solve(grid):
    pass

def parser(text_file_name):
    ''' Parse a text file containing sudokus '''
    f = open(text_file_name,'r')
    grids = re.findall('Grid.+\n([\d+\n]{89})',f.read())
    for grid in grids:
        rows = [row.strip() for row in grid.split()]
        yield ''.join(rows)

if __name__ == '__main__':
    grids = parser('sudokus.txt')
    for i, grid in enumerate(grids):
        soln = solve(grid)
        print 'Solution to grid %s found'%(i+1)

Now, let’s work out what to do with that ‘solve’ function.

Option 1: Pure Logic

Sudokus are intended to be solved by humans without trial and error. Instead, each move comes from logical deductive patterns that I’m sure are described in tortuous detail elsewhere on the internet. Option 1, then, would be to encode the entirety of this logic in a computer program. The result would probably be quite efficient, but extremely verbose, difficult to understand, and, if it was me doing it, probably wrong. I didn’t fancy this approach much, but I would be intrigued to see some code capable of solving puzzles this way. Let’s keep going.

Option 2: Brute Force

Computers, in contrast to humans, excel at trial and error, because of the speed in which trials can be carried out. In computer programming, trial and error is better known as ‘brute force‘. Our second option might use brute force in the following way:

  • Find the first empty cell
  • ‘Pencil’ in the first number that does not appear in the same row, column or box
  • Advance to the next empty cell, etc., until no more moves are possible.
  • If there are no blank squares, then we have solved the puzzle
  • Else, go back a cell and try the next possible number, until the problem is solved

I like this algorithm because it’s almost beautifully simple. It’s known as a depth-first search, as it goes as far as possible down the rabbit-warren of each potential solution before reversing back up again. It will solve any sudoku, easy or hard, given enough time (my implementation takes about a hundred milliseconds on average, but can take up to a minute to solve puzzles designed to trip up this kind of approach). Here’s the ‘solve’ function I wrote based on the above.

import cPickle as pickle
f = open('affected_cells_list.p')
related = pickle.load(f)
NUMBERS = {'1', '2', '3', '4', '5', '6', '7' ,'8', '9'}

def solve(grid):
    ''' Recursive, depth first, brute force
    solver function '''
    def r(a):
        i = a.find('0')
        if i == -1:
            # Raise the solution as an exception
            raise Exception('\n'.join(
                [a[j*9:j*9+9] for j in xrange(9)]))
        excluded_numbers = {a[j] for j in related[i]}
        for m in NUMBERS - excluded_numbers:
            # At this point, m is not excluded
            # by any row, column, or box.
            # Let's place it and recurse.
            r(a[:i]+m+a[i+1:])
    try:
        r(grid)
    except Exception, e:
        return str(e)

Perhaps one or two aspects of this code require explaining. Firstly, the unusual function-within-a-function, ‘r’. This is a recursive function, i.e. it calls itself repeatedly until a termination criterion (i == -1, i.e. there are no more zeroes left in the grid) is reached. Once the puzzle is solved, ‘r’ spits out the result as an exception (with some formatting), as there is no other way of returning it directly. This is handled by the code in ‘solve’ outside ‘r’ to return the answer as normal.

When ‘r’ is called on an incomplete solution, we move on to a check for ‘excluded numbers’.  The code here assembles a set of numbers that appear in the related cells to i using a list of tuples called ‘related’. For example, the related cells of cell 0 (the top-left cell) are cells 1-8 (the top row), cells 9, 18, 27, 36, 45, 54, 63 and 72 (the left column) and cells 10, 11, 19 and 20 (the top-left box). I pre-pickled the list using a bit of quick-and-dirty code for maximum efficiency. Any value m that is a member of NUMBERS but not of excluded_numbers is a candidate for cell i, and is tested.

On my computer (2010 iMac), this algorithm solves the 50-sudoku problem in 4.6 seconds, and makes 932828 calls to the ‘r’ function in the process.

Option 3: Algorithm X

If this isn’t the first article you’ve read about sudoku solvers, you may be aware that sudokus are a subtype of a broader class of discrete mathematical problem called Exact Cover. Donald Knuth published Algorithm X as an efficient method of solving Exact Cover problems, and many sudoku solvers rely on this technique. Algorithm X (along with a large body of Knuth’s work) is well worth reading up on; however, I didn’t use it here for the following reasons:

  • It is nothing more than an efficient brute force algorithm. It doesn’t do anything clever with sudoku logic, and is therefore never going to be the ‘best’ algorithm. (I played around with some other people’s Python code using Algorithm X to solve the 50 sudokus problem and found that it was about four times faster than option 2, but half the speed of option 4, which we’ll look at shortly).
  • Applying it to sudokus requires a large amount of abstraction, making the code difficult to understand.
  • ‘Dancing Links’, Knuth’s proposed implementation technique, is too complicated for my small brain.

For those interested, Sebastian Raaphorst has posted a supposedly highly-efficient Python/Algorithm X sudoku solver on his website.

Option 4: A Hybrid Approach

The fourth option – my favourite, and the most efficient I’ve coded – is a hybrid of options 1 and 2. I knew I couldn’t implement a full and bulletproof logic-driven solver; however, that didn’t mean that I couldn’t add a basic rule or two to my brute-force solver to help it along. Here is the code, which computes the solutions to Project Euler’s 50 grids in around 0.4 seconds.

import cPickle as pickle
f = open('affected_cells_list.p')
related = pickle.load(f)
NUMBERS = {'1', '2', '3', '4', '5', '6', '7' ,'8', '9'}

def solve(grid):
    ''' Recursive, depth first, brute force
    solver function with heuristics '''
    def r(a):
        i = a.find('0')
        if i == -1:
            # Raise the solution as an exception
            raise Exception('\n'.join(
                [a[j*9:j*9+9] for j in xrange(9)]))
        excluded_numbers = {a[j] for j in related[i]}
        target_exclusion = 9
        while len(excluded_numbers) < target_exclusion:
            next_zero = a[i+1:].find('0')
            if next_zero == -1:
                target_exclusion -= 1
                i = a.find('0')
            else:
                i += 1 + next_zero
            excluded_numbers = {a[j] for j in related[i]}
        for m in NUMBERS - excluded_numbers:
            # At this point, m is not excluded
            # by any row, column, or box.
            # Let's place it and recurse.
            r(a[:i]+m+a[i+1:])
    try:
        r(grid)
    except Exception, e:
        return str(e)

The changes begin at the line that reads ‘target_exclusions = 9′. The logic that follows searches through all of the zeros to find cells in which all but one number is excluded. This is a much more efficient way of proceeding that simply writing numbers in the first empty cell. If no cells have all but one number excluded, we settle for the first cell with all but two excluded, etc. This reduces the number of ‘r’ function calls down from 932828 to just 7926 whilst solving all 50 puzzles.

Concluding Remarks

I’m sure that there are as many sudoku-solving algorithms as people who have tried to write them. There is no one ‘right’ way of solving the problem. I’d be intrigued to see yours.

Code

Can be downloaded from here, if you’re interested: sudoku