Countdown
numbers game solver
version
3K,
2024-02-06
In the UK Channel 4 TV Countdown show’s Numbers Game, contestants have 30 seconds to work out how to calculate a given random target number (or get as close as possible) by applying addition, subtraction, multiplication or division to some or all of the numbers, each used once only, from a partially random list of six. This document describes a computer program that solves the game. It is the author’s personal endeavour and is in no way affiliated.
The program reads the list of numbers and the target. It finds and displays in human-friendly form all distinct ways of calculating the best possible solution.
It is just one of many such programs to be found online today. It started as a 1988 Christmas break project under Xenix on a 12 MHz Intel 80286 CPU. It was a challenge then to write code that would find any solution within half a minute if there was one. Version 1 did this but it took several minutes to conclude with no result when there was no exact solution. Now updated for Linux, the same core solver runs much more quickly on a modern processor. Functional updates have improved completeness and human-friendliness.
The program’s essential elements (covered later in more detail) are:
find all sufficiently close candidate solutions by brute-force search;
discard those containing ineffectiveness;
keep but mark those containing over-complexity;
discard those that duplicate a solution found earlier; and
present those that remain in human-friendly fashion.
The baseline code reads a problem from its command line and prints the solutions. There is also a text-graphic interface version (not provided).
At the program’s core, a brute force recursive search procedure takes the list of numbers, selects all unordered pairs and applies all allowed arithmetic operations to each pair. For each result it updates a record of how the complete calculation arrived there. The latest version of the program also finds single number solutions from the list without any arithmetic. This accommodates a target of 100 when 100 is present in the original list of numbers (seen, for example, on 2023-11-29, contradicting a minimum of 101 stated by some sources).
Whenever an operation produces an interesting result – one close enough to the target – a display procedure gets called. This procedure checks the calculation record. If it is a good candidate solution it is stored in displayable form along with a computed key unique to the arithmetic of that solution. “Interesting” starts at “10 away”. This reduces whenever a better result is found. Less interesting candidate solutions found thus far get discarded.
If a result is equal to the target, the search procedure returns to its caller. Otherwise it continues the search by calling itself recursively, with a shorter numbers list where the selected pair of numbers is replaced by the result.
Stored solutions are printed when the search is complete.
The program’s search procedure discards candidate solutions containing ineffectiveness. The display procedure keeps but marks candidate solutions containing an over-complexity so the user can decide if these are useful or not. It also detects duplication and discards candidate solutions that exactly duplicate one previously found. These are details of the concepts:
Ineffectiveness: This arises when an operation makes no progress towards the target. The first type is multiplying (or dividing) a number by one; the second is subtracting two identical numbers; the third (arguably just an arithmetic fundamental) is a division that does not produce an integer result. Whenever one of these happens, onward search is terminated. A fourth type, detected by the display procedure, is an unconnected sub-calculation – some arithmetic which does not get used in obtaining the final result. Such sub-calculations get ignored when processing and storing a candidate solution.
Over-complexity: This arises when an operation, or a connected sequence of operations, generates a result which duplicates an input into its calculation. Examples include 6–3=3 and 9/3=3 which, in effect, simply discard a number. More convoluted and possibly disputable, the example sequence 8–6=2 then 2x3=6 in effect just discards 8 and 3; or 4x4=16 then 16/8=2 effectively discards a 4. The sequence 3+3=6 then 6+3=9 (i.e. 3+3+3=9 vs 3x3=9) effectively discards a 3 but is not marked because it does not duplicate one of its inputs and so does not qualify according to the current definition. This may need further study.
Duplication: The brute-force search generates arithmetically identical candidate solutions more than once, amplified by any duplicated numbers in the list. Duplicate candidate solutions have the same key as a stored one, and are discarded.
A question remains about whether the availability of choice in a calculation can lead to duplication or over-complexity. For example, a partial calculation which generates a number that’s still available from the list so you can then choose which to use. Alternatively, generating the same number from two partial calculations. This is for further study. There are some comments below on the examples.
In the display procedure, connected sequences of calculations involving just addition and subtraction are merged into a single sub-calculation when displayed. Contestants seem to do this. Merging can also be done for sequences containing just multiplication and division. This is less commonly done by contestants and its human-friendliness may be questioned. By default this particular merge is not done.
Human-friendliness is enhanced by selecting from each set of arithmetically identical solutions the one whose displayed sub-calculation order has the lowest heuristic “distance score” which preserves arithmetically narrative order – such as a contestant might use to explain a solution. The lowest distance score means that as many sub-calculations as possible are displayed immediately after the sub-calculations that make the results they use. The distance score code also has an element that encourages a sub-calculation display order which prefers approaching the target as quickly as possible, as contestants often seem to do.
Finally, distinct solutions are scored according to a heuristic “user score” for complexity. Solutions with the lowest complexity score are displayed first.
Install a Linux operating system with gcc. Compile from a command line with gcc -O3 -o numbers-tty numbers-tty.c.
To solve example 1 below run “./numbers-tty 1 5 7 9 10 25 =261” from a command line. The problem’s numbers and target may appear in any order with the target identified by a preceding “=”.
There are game policy switches in the code for turning on or off validity checks for the numbers list and for setting its acceptable length. The range of acceptable target values can be specified. The minimum must be 1 or more. A maximum of 0 is interpreted as unlimited. The maximum difference between result and target that makes a solution interesting can be set.
There are constants for enabling or disabling sub-calculation merging (both types) and the heuristic scoring. The user score heuristic can be tuned. Quite a few solution display options can be changed if desired.
To test speed, run “time numbers-tty <problem X> >/dev/null” and record user time.
<problem A>: 1 1 2 2 3 4 =959 (tests searching only – there are no close enough solutions to display)
<problem B>: 2 4 6 8 10 75 =750 (tests searching plus processing to display 225 distinct solutions)
<problem C>: 1 2 3 4 5 6 =7 (tests searching plus processing to display 1015 distinct solutions – needs the default minimum target reduced)
On 2023-11-05 with an Intel Celeron processor N5015: problem A: 8-13 ms; problem B: 33-38 ms; problem C: 127-142 ms.
Reproduced below is a selection from a bigger suite of examples used for testing. If “*” is tagged onto to the solution number it contains an over-complexity. Note that the numbering of solutions depends on the “tuning” of the heuristic scoring. This might have changed since the examples were created.
For comparison, the excellent solver at https://www.greem.co.uk/solver or https://www.greem.co.uk/quantumtombola (source code at https://github.com/elocemearg/numsolver) seems to be exactly equivalent at rejecting duplication if asked to find all solutions. It does not print most over-complex solutions as defined here but it does print some. This difference has not been investigated to see if there’s a good reason or not. The differences in examples 1, 2, 3, 7 and 8 are noted below.
Target 261 from 1 5 7 9 10
25
[1] 25+5-1=29 29x9=261
[2] 25+10+1-7=29
29x9=261
[3]* 25+10-5-1=29 29x9=261
[4] 25x10=250
250+7+5-1=261
[5] 25x10=250 250+9+7-5=261
[6]
25+9-5=29 10-1=9 29x9=261
[7] 25x9=225 7x5=35
225+35+1=261
[8] 25+10+1=36 36x7=252 252+9=261
[9]
10+1=11 25x11=275 275-9-5=261
[10] 25+5=30 30x9=270
270+1-10=261
[11] 25+7-5=27 27x10=270 270-9=261
[12]*
10/5=2 25+7-2-1=29 29x9=261
[13] 9-7=2 25x5x2=250
250+10+1=261
[14] 25-1=24 24x10=240 240+9+7+5=261
[15]
25x7=175 10x9=90 175+90+1-5=261
[16] 25+7=32 9-1=8 32x8=256
256+5=261
[17] 25+5=30 10-1=9 30x9=270 270-9=261
[18]
7x5=35 35-9=26 26x10=260 260+1=261
[19]* 7-5=2 10/2=5
25+5-1=29 29x9=261
[20] 7+1=8 8x5/10=4 25+4=29
29x9=261
[21] 25-7=18 10+5=15 18x15=270 270-9=261
[22]
25+10+7=42 5+1=6 42x6=252 252+9=261
[23]* 25+7=32 9-1=8
32x8=256 256+10-5=261
[24] 25x7=175 10-1=9 9x9=81
175+81+5=261
[25] 7+5=12 25x12/10=30 30-1=29 29x9=261
[26]*
25x9=225 10-5=5 7x5=35 225+35+1=261
[27] 25x10=250 9-7=2
5x2=10 250+10+1=261
[28] 25+1-10=16 9+7=16 16x16=256
256+5=261
[29] 10x5=50 50-9=41 41x7=287 287-25-1=261
[30]
25-1=24 24x9=216 7x5=35 216+35+10=261
[31] 25-7=18
10+5-1=14 18x14=252 252+9=261
[32] 25-9=16 10+7-1=16
16x16=256 256+5=261
[33] 25-7=18 9+5=14 18x14=252
252+10-1=261
[34]* 25x7/5=35 35-9=26 26x10=260 260+1=261
[35]
25-10=15 7-5=2 15x2=30 30-1=29 29x9=261
[36] 10x7=70
70-25=45 5+1=6 45x6=270 270-9=261
[37] 10-7=3 9x3=27
27+25=52 52x5=260 260+1=261
[38] 10+7=17 9-1=8 17x8=136
25x5=125 136+125=261
[39] 7x5=35 35-9=26 10+1=11 26x11=286
286-25=261
Target 679 from 3 5 7 9 10
50
[1] 10x5=50 50+50-3=97 97x7=679
[2] 50x10/5=100
100-3=97 97x7=679
[3] 50x9/5=90 90+10-3=97 97x7=679
[4]
9+5=14 50x14=700 7x3=21 700-21=679
[5] 50+7=57 9+3=12
57x12=684 684-5=679
[6]* 10x5=50 9/3=3 50+50-3=97
97x7=679
[7] 50x9/5=90 90+7=97 10-3=7 97x7=679
[8]*
50x10/5=100 9/3=3 100-3=97 97x7=679
[9] 10x9=90 50/5=10
90+10-3=97 97x7=679
[10] 50+3=53 53x10/5=106 106-9=97
97x7=679
[11]* 10+9-5=14 50x14=700 7x3=21 700-21=679
[12]*
50+7=57 9+3=12 57x12=684 684+5-10=679
[13] 50x7/5=70
70-3=67 67x10=670 670+9=679
[14] 10x7=70 70-3=67
67x50/5=670 670+9=679
[15] 50+10=60 60x5=300 300-9=291
291x7/3=679
[16] 50x7=350 350-9=341 341x10/5=682
682-3=679
[17] 10+9=19 50x19x5=4750 4750+3=4753
4753/7=679
[18] 10x9=90 90+7=97 50/5=10 10-3=7
97x7=679
[19] 10x9=90 90+50=140 140x5=700 7x3=21
700-21=679
[20] 10x9=90 90+5=95 95x50=4750 4750+3=4753
4753/7=679
Target 477 from 8 4 7 4 3
50
[1] 50+3=53 8+4+4-7=9 53x9=477
[2] 50+7-4=53
8+4-3=9 53x9=477
[3] 50+3=53 8/4=2 7+2=9 53x9=477
[4]
50+3=53 4/4=1 8+1=9 53x9=477
[5] 50+3=53 4x4=16 16-7=9
53x9=477
[6]* 50+3=53 8/4=2 7+4-2=9 53x9=477
[7]*
50+3=53 4x4/8=2 7+2=9 53x9=477
[8] 50-7=43 8+3=11
43x11=473 473+4=477
[9] 50+3=53 7x4=28 28+8=36
53x36/4=477
[10] 50x8=400 4+4+3=11 11x7=77 400+77=477
[11]
50-8-4=38 38x4=152 152+7=159 159x3=477
[12]* 50+3=53 8-4=4
4x4=16 16-7=9 53x9=477
[13] 50x8=400 7+4=11 4+3=7 11x7=77
400+77=477
[14] 4+4=8 50x8=400 8+3=11 11x7=77
400+77=477
[15] 4+4=8 8x8=64 64-3=61 61x7=427 427+50=477
Target 718 from 3 5 3 7 10
75
[1] 75-3=72 72x10=720 720+5-7=718
[2] 75-3=72
72x10=720 720+3-5=718
[3] 75x10=750 7x5=35 750+3-35=718
[4]
75+3-7=71 71x10=710 710+5+3=718
[5] 75x3x3=675 10x5=50
675+50-7=718
[6] 75-5=70 70x10=700 7x3=21 700+21-3=718
[7]
75x10=750 5+3=8 7-3=4 8x4=32 750-32=718
[8] 75-3=72
72x10=720 7+3=10 10/5=2 720-2=718
[9] 75-3=72 7+3=10
72x10=720 10/5=2 720-2=718
Target 778 from 10 4 1 7 7
75
[1] 75x10=750 7x4=28 750+28=778
[2] 75+1=76
76x10=760 760+7+7+4=778
[3] 75x10=750 4+1=5 7x5=35
750+35-7=778
[4] 75x10=750 4-1=3 7x3=21 750+21+7=778
[5]*
75x10=750 7+1-4=4 7x4=28 750+28=778
Target 505 from 75 3 9 1 6
8
[1] 9x8x6=432 432+75+1-3=505
[2] 75+9=84 84x6=504
504+1=505
[3] 75-9-3=63 63x8=504 504+1=505
[4] 6+1=7
75x7=525 525-9-8-3=505
[5] 75+9+1=85 85x6=510
510+3-8=505
[6] 75+8=83 83x6=498 498+9+1-3=505
[7]*
75+3-9-6=63 63x8=504 504+1=505
[8] 6x3=18 75-18=57
57x9=513 513-8=505
[9] 75-3=72 6+1=7 72x7=504
504+9-8=505
[10] 75+8=83 9-3=6 83x6=498 498+6+1=505
[11]
75-3=72 9+6-8=7 72x7=504 504+1=505
[12]* 75+9=84 8-6=2
84x3x2=504 504+1=505
[13] 9+1=10 10x8x6=480 75/3=25
480+25=505
[14] 75-3=72 72x6=432 9x8=72 432+72+1=505
[15]
9x6=54 75-54=21 21x8x3=504 504+1=505
[16] 75x9=675
675-3=672 672x6/8=504 504+1=505
[17]* 75+9=84 6/3=2 8-2=6
84x6=504 504+1=505
Target 794 from 25 100 2 3 2
6
[1] 100-2-2=96 96x25/3=800 800-6=794
[2] 25x6x2=300
300+100-3=397 397x2=794
[3] 3x2=6 6+2=8 100x8=800
800-6=794
[4] 6+2=8 100x8=800 3x2=6 800-6=794
[5]
6-2=4 100x4=400 400-3=397 397x2=794
[6] 2x2=4 100-4=96
96x25/3=800 800-6=794
[7] 2/2=1 25-1=24 100x24/3=800
800-6=794
[8] 100+2=102 6+2=8 102x8=816 816+3-25=794
[9]
25x6x2=300 300-2=298 298x3=894 894-100=794
[10] 100+2=102
102/3=34 34-2=32 32x25=800 800-6=794
Target 973 from 75 2 10 9 6
5
[1] 10+9-6=13 75x13=975 975-2=973
[2] 75x9=675
10x6x5=300 675+300-2=973
[3] 75-10=65 9+6=15 65x15=975
975-2=973
[4] 9x6=54 75+54+10=139 5+2=7 139x7=973
[5]
9+6-2=13 75x13=975 10/5=2 975-2=973
[6] 10/5=2 9+6-2=13
75x13=975 975-2=973
[7] 75-10=65 9-6=3 65x5x3=975
975-2=973
[8] 6x5=30 75+30+2=107 107x9=963 963+10=973
[9]
10x9=90 90+75-2=163 163x6=978 978-5=973
[10] 9+6=15
15/5=3 10+3=13 75x13=975 975-2=973
Solutions marked as over-complex:
In [3], [23] and [26] 10-5=5 is a simple over-complexity.
In [34] 25/5=5 is a simple over-complexity.
In [12] 10/5=2 and 7-2=5 is a compound over-complexity.
In [19] 7-5=2 and 10/2=5 is a compound over-complexity.
Solutions that duplicate a list value (for investigation):
In [3], [6], [10], [17] and [28] a simple list-duplicate 9 is made with 10–1=9.
In [24] a simple list-duplicate 9 is made with 10-1=9 as above; but note that its use later in 9x9=81 creates no alternative.
In [13] and [27] a compound list-duplicate 10 is made with 9-7=2 and 5x2=10.
Solutions that create non-list duplicate values (for investigation):
In [28], [32] two non-list 16s are made but are used as 16x16=256 so there’s no alternative.
The Greem solver gives 36 solutions [2022-03-12]. It includes the 33 unmarked solutions above plus [3]*, [12]* and [19]*.
Solutions marked as over-complex:
In [6] and [8] 9/3=3 is a simple over-complexity.
In [11] and [12] 10-5=5 is a simple over-complexity.
Solutions that duplicate a list value (for investigation):
In [7] and [9] a simple list-duplicate 7 is made with 10-3=7.
In [18] a simple list-duplicate 10 is made with 50/5=10.
The Greem solver gives 17 solutions [2022-03-12]. It includes the 16 unmarked solutions above plus [12]*.
Solutions marked as over-complex:
[6] 4-2=2.
[7] 4x4/8=2 (vs. 8/4=2).
[12] 8-4=4 over-complexity & list value.
Solutions that duplicate a list value (for investigation):
[10] 4+3=7 (list) and 4+4=8 (list) – but in a merged sub-calculation.
[12] 8-4=4 list value and over-complexity simultaneously.
[13] 4+3=7 (list) and separate 7+4=11 vs 3+4+4=11.
[14] 4+4=8 (list) and 8+3=11 vs non-merged 3+4+4=11.
[15] 4+4=8 (list) but 8*8=64 so no choice.
The Greem solver gives 13 solutions [2022-03-12]. It includes the 12 unmarked solutions above plus [7]*.
Solutions [8] and [9] may look identical. But written for a “mathematical eye” they are different:
[8] (75-3)x10-(7+3)/2=718.
[9] (75-3)x(7+3)-(10/2)=718.
The Greem solver gives 5 solutions [2022-03-12]. It includes the 4 unmarked solutions above plus [5]*.
Solutions marked as over-complex:
[7] 6-3=3 (over-complexity) and 9-6=3 (list) and 9-3=6 (list) cf [3].
[12] 8-6=2 and 2x3=6 (compound over-complexity and compound list value) - cf [2].
[17] 6/3=2 and 8-2=6 (compound over-complexity and compound list value).
Solutions that duplicate a list value (for investigation):
[6] 9-3=6 (list) – cf [10] – see below.
[7] 9-6=3 (list) and 9-3=6 (list) cf [3].
[9] 9-8=1 (list) – cf [11].
[10] 9-3=6 (list) – cf [6] – see below.
[11] 9-8=1 (list) – cf [9].
[12] 8-6=2 and 2*3=6 (compound list value and compound over-complexity) – cf [2].
[17] 6/3=2 and 8-2=6 (compound list value and compound over-complexity).
Solutions that create non-list duplicate values (for investigation):
[1] vs [14] where 72 gets made in a partial calculation – see below.
Evaluation of potential duplication:
Solutions [10] and [6] are related if you take the list 6 for the
second sub-calculation in place of the made 6, and the made 6 for
the second in place of the list 6. But written for a “mathematical
eye” they are different:
[6] (75+8)x6+9-3+1=505.
[10]
(75+8)x(9-3)+6-1=505.
Solution [14] becomes solution [1] if you swap the partial
calculations that both result in 72. But written for a “mathematical
eye” they are different:
[1] 9x8x6+75-3+1=505.
[14]
(75-3)x6+9x8+1=505.
The Greem solver gives 17 solutions [2022-03-12]. The 14 unmarked plus [7]*, [12]* and [17]*. It includes all potentially duplicate solutions. I conclude these are actually distinct. See examples 11 and 13.
Does [3] duplicate [4]?
[3] 3x2=6 6(made)+2=8 100x8=800 800-6(list)=794.
[4] 6(list)+2=8 100x8=800 3x2=6 800-6(made)=794.
These look potentially identical as written (ignoring the “list number” and “made number” source distinctions). Also they have the same key if the source of the operands is not distinguished so they then would be considered as duplicates.
However, the program’s key generation does distinguish operand source. How does that matter? It seems to be about the way of writing the solution. The solutions do look distinct when written for a “mathematical” eye:
[3] (3x2+2)x100-6=794.
[4] (6+2)x100-3x2=794.
The Greem solver includes both solutions. I conclude these are actually distinct. See examples 8 and 13.
Does [5] duplicate [6]?
The Greem solver includes both solutions. I conclude these are actually distinct. See examples 8 and 11.
John Phillips