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

Coding Countdown: The Letters Round

For the benefit of the uninitiated, Countdown is a long-running British TV game show comprising of multiple ‘letters’ and ‘numbers’ rounds, and concluding with an anagrams game called the ‘conundrum’. If, unlike me, you didn’t spend your entire childhood watching it with your grandparents, find out more here.

This blog post is about cheating in the letters round with the help of a bit of Python code. It seemed worth writing about as the obvious solution is far from optimal, and the optimal solution is far from obvious (to me, anyway). I’ll talk you through how to find all of the possible five-, six-, seven-, eight- and nine-letter English words in under 0.2 seconds.

Setting Up the Problem

Obviously, any algorithm is going to need some way of finding out whether or not some fudged combination of letters is a (British) English word.  For this purpose, I downloaded a spell-checking text file containing around 80,000 words from here.

For the purposes of testing, I also thought it would be best to simulate the drawing of vowels and consonants at the beginning of each game. Allegedly, ‘the frequencies of the letters within each pile are weighted according to their frequency in natural English, in the same manner as Scrabble. Candidates are allowed to choose how many vowels and consonants go on the board, to a total of nine, but typically pick between two and four vowels.

Some basic code to start us off, then, is going to look like this:

from random import sample, randint
from sys import argv

def solve(letters):
    '''
    Function to return the 'winning' countdown words
    for a given string of letters.
    '''
    words_file = open('brit-a-z.txt')
    # We'll write code to find the winning words here

# Allow the option for the user to pass their own letters.
# If none are given, generate nine random letters.
try:
    letters = argv[1]
except IndexError:
    VOWELS = 'eeeeeeeeeeeeaaaaaaaaaiiiiiiiiioooooooouuuu'
    CONSONANTS = 'nnnnnnrrrrrrttttttllllssssddddgggbbccmmppffhhvvwwyykjxqz'
    n_vowels = randint(2,4)
    vowels = sample(VOWELS, n_vowels)
    consonants = sample(CONSONANTS, 9 - n_vowels)
    letters = vowels + consonants
# Pass these letters to 'solve' function.
solve(letters)

The Obvious Way

The obvious way to solve this problem is to look at every possible permutation of the nine letters, and check each one against the word list. Python’s itertools.permute function will handle this nicely for us.

Supposing we were interested in words of five letters or more, we can calculate the number of possible permutations as follows (‘nPr’ denotes the number of r-permutations of n):

9P9 + 9P8 + 9P7 + 9P6 + 9P5 = 362880 + 362880 + 181440 + 60480 + 15120 = 982800

As for looking up words in the list, we could read the words file into a Python list using the ‘readlines’ method, loop over the permutations, then ask the computer to check if each permutation was in the list. This would be a bad idea for two reasons:

  • Lookups take a long time in large lists as they are O(n) operations.
  • Some of the words in the dictionary have fewer than five letters, and some have more than nine, meaning that we’re wasting time flicking through extraneous words.

As a solution, we could do something like this:

valid_words = set(word.strip() for word in f.readlines()
    if len(word) > 4 and len(word) < 10)

Here, we use a list comprehension to filter out words with too many or too few letters, and put them all in a set, in which lookup is close to O(1). (The .strip() method removes any newline and whitespace characters from the words.)

Even better, since the list of words isn’t going to change each time we run the program, we could pickle the valid_words set to a file and then just load it up again each time we run the program. Always try to avoid repeated effort, whether it’s yours or the computer’s! Our ‘solve’ function now looks like this, and takes around 0.6 seconds to solve a typical countdown letters round.

def solve(letters):
    '''
    Function to return the 'winning' countdown words
    for a given string of letters.
    '''
    valid_words = pickle.load( open('word_set.p') )
    for i in xrange(5, 10):
        print '\nLooking for %s letter words...\n'%(i)
        log = set()
        for permuted_letters in permutations(letters, i):
            word = ''.join(permuted_letters)
            if word in valid_words:
                log.add(word)
        found_words = ', '.join(
            sorted(word for word in log))
        print found_words

A Better Way

I grant that 0.6 seconds isn’t all that bad. However, the algorithm doesn’t scale well. What if we wanted to play ‘Super-Countdown’ with 12 letters? 12 letters have 12! permutations, which is over 479 million. We would, literally, be here all day.

A much more sophisticated method is to remove the requirement to permute the letters by sorting them. Let me demonstrate using the letters a, p and t.

There are 3! = 6 ways of permuting these letters. If we went through all six, we would find that we could spell ‘apt‘, ‘pat’ and ‘tap‘. However, what if we had a pre-sorted dictionary which told us every word that could be spelt using the letters a, p and t? We would only need to make one check, not six. This is crucial. This changes the problem from a permutations problem to a combinations problem. We can calculate the number of possible combinations for five to nine letters from nine as follows (‘nCr’ denotes the number of r-combinations of n):

9C9 + 9C8 + 9C7 + 9C6 + 9C5 = 1 + 9 + 36 + 84 + 126 = 256

Yes, we just reduced the search space by a factor of almost 4000.

Now, about that pre-sorted dictionary. We could quickly pickle something to do this. Note that dictionary lookup is also ~ O(1). You can read about the ‘-1′ argument to pickle.dump here, or simply think of it as magic and move on.

import cPickle as pickle

f = open('brit-a-z.txt')
valid_words = {}
for word in f:
    word = word.strip()
    l = len(word)
    if l < 5 or l > 9 or "'" in word:
        continue
    sorted_word = ''.join(sorted(word))
    if sorted_word not in valid_words:
        valid_words[sorted_word] = [word]
    else:
        valid_words[sorted_word].append(word)
# Improve performance slightly by storing the
# valid words as tuples instead of lists.
for key, value in valid_words.items():
    valid_words[key] = tuple(value)
pickle.dump(valid_words, open('word_dict.p', 'w'), -1)

Our finished Python code looks like this. It solves the Countdown letters round in about 0.11 seconds on an Intel i5 Apple Mac; most of which is taken up through loading the valid_words dictionary into memory.

from random import sample, randint
from sys import argv
from itertools import combinations
import cPickle as pickle

def solve(letters):
    '''
    Function to return the 'winning' countdown words
    for a given string of letters.
    '''
    valid_words = pickle.load( open('word_dict.p') )
    letters = sorted(letters)
    for i in xrange(5, 10):
        print '\nLooking for %s letter words...\n'%(i)
        log = set()
        for combined_letters in combinations(letters, i):
            sorted_word = ''.join(combined_letters)
            if sorted_word in valid_words:
                for word in valid_words[sorted_word]:
                    log.add(word)
        found_words = ', '.join(
            sorted(word for word in log))
        print found_words

# Allow the option for the user to pass their own letters.
# If none are given, generate nine random letters.
try:
    letters = argv[1]
except IndexError:
    VOWELS = 'eeeeeeeeeeeeaaaaaaaaaiiiiiiiiioooooooouuuu'
    CONSONANTS = 'nnnnnnrrrrrrttttttllllssssddddgggbbccmmppffhhvvwwyykjxqz'
    n_vowels = randint(2,4)
    vowels = sample(VOWELS, n_vowels)
    consonants = sample(CONSONANTS, 9 - n_vowels)
    letters = vowels + consonants
# Pass these letters to 'solve' function.
solve(letters)

Do you have any ideas on how this could be optimised further? Let me know!

The full source code can be downloaded as a zip file by clicking the following link:
countdown_letters