The objective of the Countdown numbers game is to make a target number (a randomly generated integer between 100 and 999) from six other pseudo-randomly selected numbers in the set [100, 75, 50, 25, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. The numbers 1-10 may appear more than once, and contestants have some say in their distribution, for example ‘one large (i.e. in the 25-100 group) and five small (i.e. in the 1-10 group)’.

The following rules apply:

- Only the operations +, -, x and / (plus, minus, times, divide) are allowed.
- Brackets may be used, e.g. (1+3) x 10 = 40.
- All intermediately calculated numbers must be positive integers, e.g. (5 / 2) * 10 = 25 is not permissible as 5 / 2 = 2.5; however, (5 * 10) / 2 = 25 is fine. Similarly, (5 – 10) + 50 = 45 is unacceptable as 5 – 10 = -5; however, (5 + 50) – 10 is fine.
- A number may only be used as many times as it appears in the initial set of six.
- It is not necessary to use all of the numbers.

This article is about using efficient Python code to quickly calculate all possible ways of reaching a target number (not necessarily between 100 and 999) from a group of smaller numbers (not necessarily 6), adhering to the Countdown rules described above. Along the way we’ll look at tree construction and search based on Python dictionaries.

*n.b. the rule concerning not having to use all of the numbers is glossed over until the very end of the article for the sake of simplicity in explanation.*

I thought I had cracked this one in double-quick time. I considered the option of running through every possible permutation of the numbers and, for each permutation, slotting in every possible permutation of the operators, then evaluating left-to-right. If, at any stage, the rules were violated, that particular permutation would be abandoned. Given that there are 6! = 720 ways of permuting 6 numbers without replacement, and 1020 ways of permuting four operators five times *with* replacement, this gives a maximum of 734400 expressions to evaluate, which, to a computer, is no big deal. Bingo!

But, as a trivial example can show, this algorithm does not generate every possible solution. Consider the case of target number 144 with working numbers [11, 11, 11, 11, 11, 11].

The only way of doing this is ((11/11) + 11) * ((11/11) + 11) = 144. The brackets are crucial. No possible arrangement of left-to-right operations can give 144. Back to the drawing board.

I like to go about solving complicated problems by solving simpler ones first. So, rather than throwing myself straight into the James Martin 952 problem, I tried to make 6 from [1, 2, 3].

To establish all of the different ways of making 6, I drew something like this:

What’s going on here is that I’m considering pairs of numbers (let’s call them A and B) in turn. I consider every way of reducing [1, 2, 3] into [*x*, 3], [*x*, 2] and [*x*, 1]. It turns out that there are between two and four values for x in the general case:

- Addition and multiplication will never violate the rules. They are commutative operations, so there is no need to consider A + B and B + A separately.
- Subtraction is not commutative; however, if A is greater than B, then A – B will always give a positive integer. Conversely, if A is less than or equal to B, A – B will never give a positive integer.
- Division is not commutative; however, if A is less than B, then A / B will never give a positive integer. We will accept A / B if A is greater than or equal to B and the result is an integer.

To start us off in Python, here is some code that returns all of the possible values of x from A and B. It also returns a string representation of the operation, so we can retrace how each *x* was constructed later. The code requires A <= B to be valid, which we will address later. Note the use of the ‘yield’ statement, which should be interpreted by non-Python programmers as ‘return *x* and keep going’.

def all_results_from(a, b): ''' Yield all of the possible positive integer results from applying +, -, * and / to a and b as tuples. The first element is a string representation of the operation. The second is an integer. We assume b > a. Depending on a and b, there may be 2 - 4 possible results. ''' # Addition and multiplication are commutative. yield '+', a + b yield 'x', a * b # Subtraction and division are not commutative. c = b - a if c > 0: yield '-', c if b % a == 0: yield '/', b / a

The diagram continues to reduce the tree in this way until the ‘leaves’ are single integers. These ‘leaves’ can be shown to be *every* possible outcome from the original numbers, as each pair combination is effectively a ‘bracketed’ operation. A bit of thought will tell you that we could make 144 from the [11, 11, 11, 11, 11, 11] example with this method.

The tree can be constructed with a bit of recursive code. This article about Python graphs represents a graph as a dict of lists; however, I used a dict of dicts as I needed to store information on the ‘connecting lines’, i.e. how *x* was made from A and B. The dictionary keys are tuples of numbers available for selection, henceforth referred to as nodes. My first stab went something like this:

def solve(numbers, target): numbers = tuple(sorted(numbers)) graph = defaultdict(dict) def r(numbers): l = len(numbers) for pair, rejects in pairs_and_rejects(l): a, b = numbers[pair[0]], numbers[pair[1]] rejects = [numbers[i] for i in rejects] for op, c in all_results_from(a, b): node = tuple(sorted(rejects + [ c ])) graph[node][numbers] = ((a, b), op, c) r(node) r(numbers)

I’ve already shown you the ‘all_results_from’ function, so the only thing new here is ‘pairs_and_rejects’. ‘Pairs’ here refers to the A and B we have set aside to operate on. ‘Rejects’ is a list of what’s left over. Note the use of the built-in ‘sorted’ function, which allows us to guarantee A <= B, and avoids the code interpreting (3, 2) as being different from (2, 3). Also, the function is called ‘solve’, and accepts ‘target’ as an argument, but we haven’t done any solving yet.

This code works OK, but there are two problems, both caused by the dictionary keys (i.e. node names) not being unique in the current system.

- The code does not consider the possibility of two
*DIFFERENT*parent nodes ((3, 3) and (2, 3)) arriving at the same node (6). This is a serious problem as, when we retrace our steps later and enquire how many ways of making 6 were found, we will be told ’1′. We’re also wasting computational effort if the common node has a subtree of its own to calculate. - Referring to my hand-drawn tree, you will see that there are multiple ways of arriving at (2, 3) from the
*SAME*parent node (i.e. (1, 2, 3)) and the code above overwrites old ones as as it goes. This is a less serious problem that will normally only manifest itself when 1s and 2s are involved, e.g. 2 x 1 = 2 / 1 = 2. You may be able to think of other special cases.

To counter the first problem, we need to ask whether or not a node already exists in the graph. To counter the second problem, we need to allow the facility to store multiple paths between two nodes. We will use a set to guarantee the uniqueness of these paths.

Finally, for reasons of efficiency, let’s add a conditional statement when we get down to just two numbers, A and B, at a node. If A x B is less than our target, or B / A (remember, A <= B) is greater than our target, then it’s not worth bothering trying + and -.

Here is the finished graph construction function:

def solve(numbers, target): numbers = tuple(sorted(numbers)) graph = {} def r(numbers): l = len(numbers) if l == 2: a, b = numbers[0], numbers[1] if b / a > target or a * b < target: return for pair, rejects in pairs_and_rejects(l): a, b = numbers[pair[0]], numbers[pair[1]] rejects = [numbers[i] for i in rejects] for op, c in all_results_from(a, b): node = tuple(sorted(rejects + [ c ])) if node in graph: graph[node][numbers].add(((a, b), op, c)) else: graph[node] = defaultdict(set) graph[node][numbers].add(((a, b), op, c)) r(node) r(numbers)

So far, we’ve glossed over the fact that we don’t have to use all of the numbers. This can be overcome by using the itertools.combinations function to extend the graph such that all possibilities are included, like so:

for i in xrange(len(numbers)): for numbers_combination in combinations(numbers, i+1): r(numbers_combination)

Now we’ve constructed our tree, we need to work backwards to find all of the paths from our target to the original numbers (both the full set and subsets thereof). Fortunately, the hard labour has already been done for us, and a simple copy-paste of an official Python example function called find_all_paths will do the trick nicely.

From there, it’s a matter of formatting the output, which is a fairly unglamourous process. One detail to be aware of is that, in terms of tree traversal, the following solutions will be considered unique:

‘Make 750 from [25, 5, 3, 2]‘:

1:

25 x 2 = 50

5 x 3 = 15

50 x 15 = **750**

2:

5 x 3 = 15

25 x 2 = 50

50 x 15 = **750**

Of course, they are not, so we only show solutions whose *intermediate* numbers are different. This doesn’t preclude (2 x 3 = 6, 6 x 4 = 24) being interpreted as different to (3 x 4 = 12, 12 x 2 = 24). Some people may disagree; however, I would argue that these solutions are in fact unique.

Let’s set our code loose on James Martin’s 952 game. We learn that there are, in fact, seven possible solutions! (James picked option 3). Perhaps he’s not such a genius after all!

Blakes-iMac:countdown_math Blake$ time python maths.py SOLUTION 1 FROM (3, 6, 25, 50, 75, 100) 100 + 6 = 106 106 x 75 = 7950 7950 x 3 = 23850 23850 - 50 = 23800 23800 / 25 = 952 SOLUTION 2 FROM (3, 6, 25, 50, 75, 100) 75 x 3 = 225 100 + 6 = 106 225 x 106 = 23850 23850 - 50 = 23800 23800 / 25 = 952 SOLUTION 3 FROM (3, 6, 25, 50, 75, 100) 100 + 6 = 106 106 x 3 = 318 318 x 75 = 23850 23850 - 50 = 23800 23800 / 25 = 952 SOLUTION 4 FROM (3, 6, 25, 50, 75, 100) 100 + 3 = 103 103 x 75 = 7725 7725 x 6 = 46350 46350 / 50 = 927 927 + 25 = 952 SOLUTION 5 FROM (3, 6, 25, 50, 75, 100) 100 + 3 = 103 103 x 6 = 618 618 x 75 = 46350 46350 / 50 = 927 927 + 25 = 952 SOLUTION 6 FROM (3, 6, 25, 50, 75, 100) 100 + 3 = 103 75 x 6 = 450 450 x 103 = 46350 46350 / 50 = 927 927 + 25 = 952 SOLUTION 7 FROM (3, 6, 25, 50, 75, 100) 75 x 6 = 450 450 / 50 = 9 100 + 3 = 103 103 x 9 = 927 927 + 25 = 952 real 0m1.492s user 0m1.307s sys 0m0.107s

I don’t think 1.5 seconds is too bad for this! I feel as if, though, someone might be able to do better. Do you have any ideas? Let me know!

]]>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.

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.

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.

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.

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.

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.

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

]]>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.

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 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

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