11,646,838 members (73,828 online)

# Countdown Number Puzzle Solver

, 17 Jun 2015 CPOL 16.6K 947 24
 Rate this:
Please Sign up or sign in to vote.
Describes an algorithm that solves the Countdown number puzzle written in c#

## Introduction

I occasionally watch Countdown, a popular day time television game show on Channel 4 in the UK. One of the games is a number puzzle where a contestant picks 6 random numbers and then has to build an equation from them that equals a randomly generated target during a 30 second countdown.

I like playing along to this game but I find that after using up 4 or 5 numbers, I tend to forget which numbers I’ve already used. I could use a pen and paper to keep track but I don’t take it that seriously. This is however just the sort of puzzle that is an ideal candidate to be solved by a computer. It won't ever forget which numbers it's used and it can always find the really obvious solution that's staring you right in the face but just cannot see.

This article documents the algorithm that I came up with. As with most algorithms, the trick is doing it quickly.

## Game Rules

The contestant picks numbers by choosing 6 tiles from 24 placed face down in a grid pattern. The first row of the grid contains 4 large value tiles having values 25, 50, 75 and 100. The remaining grid contains two sets of tiles with values of 1 to 10. The contestant can choose none or up to 4 large tiles from the first row and the remaining tiles from the rest of the grid.

The random target number is generated in the range of 101 to 999 inclusive.

Only positive integer arithmetic is allowed using add, subtract, divide and multiply operators e.g. (75/5) is ok but (3/4) and (3-4) would be invalid.

Each tile can only be used once but not all tiles need to be used.

## The UI

The UI for the Number Puzzle application is simply functional, only providing the basic features required to play the game and exercise the solver. It isn't up to commercial standards.

The Choose button picks tiles and the target according to the games rules and the tile options combo box. You can also type in whatever combination of tiles and target you want.

The Start Timer button starts a 30 second timer. The exclamation system sound is played when your time is up.

The Solve button starts the `PostFixSolvingEngine` with the results being displayed in the list box in order of complexity. This has a context menu allowing the results to be copied to the clipboard.

## How the Solving Engine Works

This uses a simple brute force approach where every possible equation is evaluated. The equations are constructed in postfix form. That removes the need for parentheses and this considerably simplifies the problem. The code knows how to construct the postfix equations by using a map which defines the sequence of pushing numbers onto the stack followed by executing an operator.

The solving engine `Solve()` method is shown below:

```public void Solve()
{
for (int k = 2; k <= tiles.Length; k++)
{
// get all the combinations for k tiles
Combinations<int> combinations = new Combinations<int>(tiles, k);
// get the associated map
List<List<int>> map = postfixMap[k];

foreach (List<int> combination in combinations)
{
// get all the permutations for the combination
Permutations<int> permutations = new Permutations<int>(combination);

foreach (List<int> permutation in permutations)
{
foreach (List<int> mapRow in map)
SolveRecursive(-1, mapRow, 0, permutation, 0, 0);
}
}
}
} ```

As you can see, it loops choosing successive k combinations of the 6 tiles and gets the postfix map entry for that number of tiles. Then for each combination, it then calculates all the permutations for that combination. Then for each permutation, it tries to solve the puzzle by creating and solving all possible postfix equations using the map entries for that number of tiles.

The solving engine `SolveRecursive()` method is the main work horse. The code is rather long winded due to functions being manually inlined, so I've shown the equivalent pseudo code:

```SolveRecursive()
{
// get the stack for this recursion depth
stack = stacks[recursion_depth] ;

while (mapEntry > 0)   // push tiles onto the stack as per map
{
stack.push ;
--mapEntry ;
}

left_digit = stack.pop ;
right_digit = stack.peek ;

foreach (operator in {*, +, -, /})
{
result = evaluate (left_digit operator right_digit) ;

if (there are more map entries)
{
// set up stack for next recursion
next_stack = stacks[recursion_depth + 1]
copy stack to next_stack
next_stack.poke = result ;

SolveRecursive()
}
else
{
if (result == target)
{
record equation ;
break ;
}

if (no targets found and result is close enough)
record closest equation;
}
}
}```

The method implements a sequence of pushing zero or more tiles onto the stack before executing an operator. It then recurses executing another sequence. Each recursive call gets its own copy of the current stack so that when the recursion unwinds, the caller can simply continue with the next operator. The recursion ends when the map is completed.

Although it is a linear function conceptually it can be thought of as a tree. Each sequence splits into 4 branches, one for each operator, and for each recursion every branch further splits into 4 more branches. This repeats until the end of the map is reached when the final result is obtained for the 4 operators. After the first equation is executed, subsequent equations are evaluated by executing only one operator rather than the complete equation. The same principal applies for each node in the tree as the recursion unwinds. Tree structures and recursion are a thing of beauty.

## Combinations and Permutations

The Combinations and Permutations collection classes are implemented using the common pattern where the class's enumerator provides the next combination or permutation on demand. This is the only code that can realistically be reused so I've written them using generics.

Both classes use Donald Knuth algorithms to generate the data in lexicographic order. I think I can safely assume they are good solutions. The permutation algorithm is actually a port of the C++ standard template library function `std::next_permutation()`.

The combination algorithm doesn't produce duplicates if the source collection contains unique values. In addition, I've modified the algorithm to filter out duplicate combinations produced when the source collection itself contain duplicates (when two tiles have the same value). The source is sorted and the combinations are generated in lexicographic order. So to remove duplicates, it's simply a case of comparing the current combination with the previous. If it's greater, it's not a duplicate and that is the combination returned by the enumerator. If not, then the enumerator gets successive combinations until one is. I'm not an expert on combinatorics so I expect there may be more efficient ways of doing that.

## Postfix Map

The `PostfixMap` class is used to direct the solving engine on how to construct all the possible postfix equations for each digit count. Postfix equations are built up of a repeating sequence of pushing digits on to a stack followed by executing operators. The diagram below shows the possible postfix equations for 6 tiles:

The digits represent tiles and the dots represent possible operator positions. All equations will start by pushing 2 digits followed by executing 0 or 1 operator, then another digit followed by 0 to 2 operators etc. There will always be one less operator than digits as you move from left to right and the final map entry will always be an operator.

Consider the case for 4 digits, there will be 5 map sub entries, one for each possible postfix equation:

Here the "o" represents actual operator positions within the postfix equation shown in the first column. The code that generates the map first counts all the variations of operators in the possible operator locations as shown in column two. It then converts these counts into a map entries where numbers greater than zero means push that number of digits onto the stack and zeros indicates that an operator should be executed.

## So How Many Equations Are There?

It's the sum of the number of equations for each number of tiles k. If there are no duplicate tiles, then this is straight forward.

The last term is the product of the operators. So we have:

This gives a total of 33,665,400 equations. Note that k = 6 accounts for 92% of the total.

However, according to the rules of the game, there can be one or two pairs of duplicate tiles. The problem then starts with calculating the number of combinations. Google found this elegantly explained solution[^]. Of course, some of the combinations produced would then also contain duplicates which in turn affects the number of permutations. I've left that problem for the mathematicians and just put some instrumentation into the code. The results are:

In practice, the number of equations fully evaluated will be considerably smaller due to the positive integer arithmetic rules of the game. If an equation fails one of the rules, it is discarded as soon as it fails.

In addition, I also discard any equation where an identity operation is performed, that is divide or multiple by one, since it will be a duplicate equation.

I also filter out duplicate equations by detecting if the operator is acting on tile values directly rather than any intermediately derived value. If the operator is commutative, that is addition and multiplication; I discard the equation if the left digit is greater than the right.

The final filter is that multiplication is the first operator evaluated. If the equation is complete and the result is less than the target, then the other operators are skipped.

Ultimately, it will be dependent on the value of the tiles chosen and the target as to how many equations are evaluated fully.

For typical sets of tiles and targets:

The solver was run on my seven year old Sony Vaio laptop with a T5500 1.66MHz dual core processor with 1Gb of memory running vista.

## Conclusion

Is there any point to this? Not really. It was just a fun academic exercise.

There are a few solvers out there already including commercial countdown training programs but I haven't found any that publishes the algorithm it uses.

The code was developed using Visual Studio 2010 Express and targets NET 3.5. Thanks to Microsoft for providing VS Express for free.

## History

• 1.3 - Fix a bug found by CodeProject member WideBoyDixon[^] . The solving engine failed to find solutions that required two tiles of the same value to be divided.

• 1.2 - The countdown team at Channel 4 kindly replied to my email confirming that the target range starts at 101 rather than 100 so a single tile solution is not possible. The code and article have been updated accordingly.

• 1.1 - Move the timing code outside of the solving engine so that it's clear what is being measured. Complete the exception handling in the test code. The tests passed so unfortunately that area was neglected. Various small code refactoring. No bug fixes.

• 1.0 - Initial release

## References

Countdown Program website
http://www.channel4.com/programmes/countdown[^]

Postfix equations also known as Reverse Polish Notation
http://en.wikipedia.org/wiki/Reverse_Polish_notation[^]

Introduction to Combinations and Permutations
http://www.mathsisfun.com/combinatorics/combinations-permutations.html[^]

Algorithm L in C++ by Thomas Guest
http://wordaligned.org/articles/next-permutation#tocimplementation[^]

Algorithm L in python by Björn Edström
http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html[^]

Counting combinations containing duplicates
http://mathforum.org/library/drmath/view/56197.html[^]

Permutations, Combinations, and Variations using C# Generics by Adrian Akison
http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G[^]

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Software Developer United Kingdom
I started off working with digital hardware but after 10 years I moved over to the software side. I've written code for more then 15 years, working at several companies, writing desktop applications in Pascal, Java, C, C++ and my favourite C# from .Net1.0 onwards. A few years ago I decided it was time for a change and I'm now a self employed qualified electrician.

## Comments and Discussions

 First Prev Next
 Is it over-optimised? WideBoyDixon5-Jun-15 0:11 WideBoyDixon 5-Jun-15 0:11
 Re: Is it over-optimised? DavidHancock16-Jun-15 8:52 DavidHancock 16-Jun-15 8:52
 Re: Is it over-optimised? DavidHancock16-Jun-15 9:30 DavidHancock 16-Jun-15 9:30
 Other published algorithms... Graham Toal9-Jan-15 18:09 Graham Toal 9-Jan-15 18:09
 Re: Other published algorithms... DavidHancock13-Jan-15 2:11 DavidHancock 13-Jan-15 2:11
 Re: Other published algorithms... Graham Toal13-Jan-15 8:38 Graham Toal 13-Jan-15 8:38
 You, sir, are a freakin' GENIUS! smoore49-Jan-15 7:11 smoore4 9-Jan-15 7:11
 Re: You, sir, are a freakin' GENIUS! DavidHancock13-Jan-15 2:09 DavidHancock 13-Jan-15 2:09
 My vote of 5 Member 1107268025-Oct-14 19:00 Member 11072680 25-Oct-14 19:00
 Is it possible to compile it without VS? Member 1107268016-Sep-14 21:52 Member 11072680 16-Sep-14 21:52
 Re: Is it possible to compile it without VS? Member 1107268025-Oct-14 18:56 Member 11072680 25-Oct-14 18:56
 Re: Is it possible to compile it without VS? PIEBALDconsult8-Jan-15 7:37 PIEBALDconsult 8-Jan-15 7:37
 Neat Mike Ellison17-Mar-14 11:36 Mike Ellison 17-Mar-14 11:36
 The puzzle game sounds like fun. Nice job on the article & solution. www.MishaInTheCloud.com
 Re: Neat DavidHancock21-Mar-14 1:57 DavidHancock 21-Mar-14 1:57
 Functional version using Haskell Jon Clare10-Mar-14 7:46 Jon Clare 10-Mar-14 7:46
 Re: Functional version using Haskell DavidHancock10-Mar-14 8:13 DavidHancock 10-Mar-14 8:13
 And the alternative version? DaveAuld10-Mar-14 5:58 DaveAuld 10-Mar-14 5:58
 Last Visit: 31-Dec-99 18:00     Last Update: 3-Aug-15 23:56 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150731.1 | Last Updated 17 Jun 2015
Article Copyright 2014 by DavidHancock
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid