12,946,658 members (51,763 online)
Add your own
alternative version

#### Stats

35.2K views
1.7K downloads
32 bookmarked
Posted 10 Mar 2014

# Countdown Number Puzzle Solver

, 14 May 2017 CPOL
 Rate this:
Please Sign up or sign in to vote.
Describes an algorithm that solves the Countdown number puzzle written in c#

## Introduction

Countdown is 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 numbers and then has to build an equation from them that equals a randomly generated target during a 30 second countdown. If you haven't seen the program the rules are available here

This puzzle is an ideal candidate to be solved by a computer. It won't ever forget which numbers it's already used and it will 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.

## The UI

With no multiplayer capability or localizable UI it's not up to commercial standards however it provides enough functionality to play the game and exercise the solver. It could be useful as a training aid.

The Choose button generates tiles and the target values.

The Start Timer button starts a 30 second timer.

The Solve button starts the `SolvingEngine`.

## 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 which removes the need for parentheses and this considerably simplifies the problem. A map is used to define how the postfix equations are constructed.

The models `Solve()` method is shown below:

```public static SolverResults Solve(int[] tiles, int target)
{
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();

SolverResults results = new SolverResults();

for (int k = 2; k <= tiles.Length; k++)
{
Combinations<int> combinations = new Combinations<int>(tiles, k);

foreach (List<int> combination in combinations)
{
Permutations<int> permutations = new Permutations<int>(combination);

Parallel.ForEach(permutations,
// the partitions local solver
() => new SolvingEngine(target, k),
// the parallel action
(permutation, loopState, solvingEngine) =>
{
solvingEngine.Solve(permutation);
return solvingEngine;
},
// local finally
(solvingEngine) => results.AggregateData(solvingEngine));
}
}

stopWatch.Stop();
results.Elapsed = stopWatch.Elapsed;

return results;
}```

As you can see, it loops choosing successive k combinations of the 6 tiles. For each combination it calculates all its permutations and for each permutation it evaluates all possible postfix equations in a parallel foreach loop. Each parallel partition has its own solving engine. The engines `Solve()` method runs the engine for the given permutation, working though each map entry.

```public void Solve(List<int> permutation)
{
foreach (List<int> mapEntry in map)
SolveRecursive(-1, mapEntry, 0, permutation, 0, 0);
}```

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(recursion_depth)
{
// 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(recursion_depth + 1)
}
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 results are 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. To make the code reusable I've written them using generics.

Both classes use Donald Knuth documented 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. In addition, I've modified the algorithm to filter out duplicate combinations produced when the source collection itself contains duplicates.

## Postfix Map

Postfix equations are built up of a repeating sequence of pushing digits on to a stack followed by executing operators. All equations start by pushing 2 digits followed by executing 0 or 1 operator, then another digit followed by 0 to 2 operators etc. There is always be one less operator than digits and equations always end with an operator.

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

In the first column the O represents the position of operators within the equation. The code generates column two, a count of the operators in that position. 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 operators 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 a Dell Inspiron 5578 with an I7-7500 dual core processor (2.7 GHz) and 16 GB of memory running windows 10. Note that the timings were taken when the solver was started via the keyboard. Clicking took approximately 20ms longer, presumably due to an additional background process run by the system.

## Letters Game

In version 3.0 I've added the letters and conundrum games. I'd always intended too, but the problem was finding suitable word lists. Then I came across SOWPODS scrabble word lists. These don't contain proper nouns, hyphenated words, spelling errors etc. Pretty good, since checking the validity of 159,946 words isn't really a practical proposition.

To implement the game I preprocess the word list into a dictionary containing a list of anagrams. Once in anagram form the order of the letters within the words isn't relevant, so I use a sorted list of the letters as the dictionary key. The combination enumerator produces lexicographical combinations so to solve the puzzle it is simply a case feeding the users chosen letters into the combinator and using its output as a key for the dictionary.

The word list is preprocess in a separate project within the solution. It reads the word list text file(s) and writes the anagrams to a compresses text file using deflate compression. This file is built into the Countdown application as an embedded resource and it is converted back into a dictionary when the application starts in a background task. I haven't set up any pre/post build steps to copy the compressed text file into the application build, you'll have to do that manually if you use your own word lists. A compressed text file is included in the solution download.

The UI is straight forward:

You can either type letters or click the Vowel or Consonant buttons. The frequency of the vowels and consonants selected can be edited in the Settings tab. To see if your word is valid you can type it in to the text box above the list. A green tick is displayed if the word is in the list and clicking the arrow button will select it, expanding its group and scrolling it into view.

I originally used a tree view control to display the results but it proved too difficult to style a list box, list view and tree view control all to have a similar look and feel. In the end it was much easier to just settle on using a list view control for all of the lists. I liked the tree view expanders though so I styled the group headers accordingly.

## Conundrum Game

This is just a subset of the letters game using anagrams with only one solution. The choose button will always pick a valid conundrum. If you type in letters then the solve button will only be enabled if there is a valid solution.

## Conclusion

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

I had intended to port version 2.0 to android using Xamarin but got side tracked when I found the word lists. May be that will be my next project.

Using the application to find longer words than Susie is definitely cheating.

## History

• 3.1 - Bug Fix. The Choose button on the Letters tab didn't clear any pre-existing errors.

• 3.0 - Implement the letter games. Update the Combination and Permutation enumerators to work with nullable types. Update the number game solver to use a parallel foreach loop. Update the solution to VS 2017.

• 2.0 - Replace the winforms UI with WPF. Refactor the code to the MVVM design pattern. Update the solution to VS 2015. Move the unit test code in to a unit test project. Rewrite the unit tests and add new view model tests.

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

• 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[^]

Encyclopaedic Countdown facts website
http://www.thecountdownpage.com/index.htm[^]

Postfix equations also known as Reverse Polish Notation
https://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
After working with digital hardware for 10 years I moved over to the software side. For 15 plus years I have been writing desktop applications and system software for Macs and Windows machines in Pascal, Java, C, C++ and my favourite C# from .Net1.0 onwards.

 Pro

## 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
 Re: Neat DavidHancock21-Mar-14 1:57 DavidHancock 21-Mar-14 1:57
 Thanks. I'm pleased you liked it.
 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: 24-May-17 0:00 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170518.1 | Last Updated 14 May 2017
Article Copyright 2014 by DavidHancock
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid