The Countdown game is one of the oldest TV show running in the world. It started broadcasting in 1972 on the french television as "des chiffres et des lettres", literally "numbers and letters" with a numbers round called "Le compte est bon", literally "the count is good". It started broadcasting in 1982 on British channel 4 as Countdown, and it has been running since in both countries.
The numbers round of the game is extremely simple: 6 numbers are drawn from a set of 24 which contains all numbers from 1 to 10 (small numbers) twice plus 25, 50, 75 and 100 (large numbers). Then, with these six numbers, the contestants have to find a number randomly drawn between 101 and 9991, or, if it is impossible, the closest number to the number drawn. As soon as a number has been used, it can't be used again. For example, if the six numbers drawn are 1,1,4,5,6,7 and the number to find is 899 the answer is:
6x5=30 30+1=31 4x7=28 28+1=29 29*31=899
There are usually different ways to find a solution. The simplest answer is usually defined as the answer using the least number of operations, and if two solutions have the same number of operations, a possible refinement is to keep the one having the smallest highest number.
As odd as it might seem, the game, while extremely popular, never received any serious scientific attention. Many websites in France and in Great Britain discuss the game and how to program it, with lot of code, lot of statistics, and sometimes lot of errors. There are many commercial or free programs developed for this game. Some of them are bugged or use incomplete or incorrect algorithms.
The goal of this
article is to do a scientific
analysis of the game regarding its complexity and to provide a set of
cutting edge algorithms and codes to solve it properly. It is a long
preprint (17 pages), quite technical, that will be submitted, if I
have the time, to a conference or a journal, probably in a reduced
form (Update: A slightly shorter version has been accepted for
publication at
GCAI 2015.
The proceedings are available
here
in the EPiC Series in Computer Science). It is also available
on
arxiv.
The code needs to be
cleaned up a little bit, and will then be made available on this
page. However, the main program has been written to run on linux with
MPI, a configuration that may not be accessible to everyone.
There is an html version of this article
here.
Mathematical formulas are however looking better in the pdf.
This article also discusses various improvements to turn the game into
a more difficult one, such as selecting difficult problems, or
changing the pool from which to pick numbers.
It also introduces a variant of the game where it is
possible to use a new operation, the square operation. Each
remaining number may be replaced by its square in a calculation. For
example, finding 999 with 1,2,3,4,5,6 is impossible in the standard
game, while it is possible in this variant:
Operations Remaining numbers
{1,2,3,4,5,6}
3 x 6 = 18 {1,2,4,5,18}
18 x 18 = 324 {1,2,4,5,324}
4 + 5 = 9 {1,2,9,324}
324 + 9 = 333 {1,2,333}
1 + 2 = 3 {3,333}
333 x 3 = 999 {999}
With this modification, the game is no longer decidable, or at least decidability is not clear. Solutions can now be very long. For example to find 862 with 1,10,19,25,75 and 100, 14 steps are needed, using numbers as large as 400000000.
Operations Remaining numbers
{1,10,10,25,75,100}
10 - 1 = 9 {9,10,25,75,100}
100 x 100 = 10000 {9,10,25,75,10000}
9 x 9 = 81 {81,10,25,75,10000}
10 x 10 = 100 {81,100,25,75,10000}
100 x 100 = 10000 {81,10000,25,75,10000}
10000 + 10000 = 20000 {81,20000,25,75}
75 x 75 = 5625 {81,20000,25,5625}
5625 x 5625 = 31640625 {81,20000,25,31640625}
20000 x 20000 = 400000000 {81,400000000,25,31640625}
400000000 - 31640625 = 368359375 {81,368359375,25}
25 x 25 = 625 {81,368359375,625}
625 x 625 = 390625 {81,368359375,390625}
368359375 / 390625 = 943 {81,943}
943 - 81 = 862 {862}
There are only 49 instances of the game which have currently no solution. This does not mean that there are no solution, but only that with the current numerical bounds used in the program no solutions were found. These 49 instances are:
1 1 10 10 25 100: 858 1 1 10 10 25 75: 863 1 1 10 10 50 100: 433 453 547 683 773 853 1 1 10 10 50 75: 793 853 978 1 1 10 10 75 100: 433 453 457 478 547 618 653 682 708 718 778 793 822 853 892 907 958 978 1 1 10 25 75 100: 853 863 1 1 10 50 75 100: 793 813 853 978 1 1 5 5 25 100: 813 953 1 1 7 7 50 100: 830 1 1 8 8 9 9: 662 1 1 9 10 10 100: 478 573 587 598 1 1 9 9 10 100: 867 1 9 9 10 10 100: 867 947 957 958 967
The following programs solve the classical game, with a "smart" sort of the complete set of solutions (read the article):
The following program is the one used for computing all the statistics presented in the article. The Linux 64 bits version takes 13s on an i7 980X computer (the linux 32 bits version computes the result in 23s; windows version are slightly slower). To truly appreciate the speed of the algorithm, this web site presents the same result computed in 60 days (!) while kitsune (one of the best public domain program) computes these results in a few hours.
The program must be used in command line mode, and takes 4 arguments:
For example under windows:
stats64.exe 6 100 1000 1000generates the statistics for the problem with 6 numbers, looking for solutions between 101 and 999, and looking for approximate solutions as far as necessary (the "classic" game).
The program has been heavily tested in a Linux 64 bits environment. The other programs work for 6 numbers, but have not been really tested and bugs might still be there (expecially under windows because of memory allocation problems).
The program generates 3 files:
For those who have a special nostalgy for the amiga computer, here is the C and assembly code of the first program (according to my knowledge) which solved almost properly (see in the article) the game in the allotted amount of time. The amiga executable is here.
This page has been read
times (in english or in french).
The download and use of documents or photographies from this site is allowed
only if their provenance is explicitly stated , and if they are only
used for non profit, educational or research activities.
All rights reserved.
Last modification: 09:49, 02/22/2024