If you haven't seen the TV program 'Countdown', here's how it works. One of the games involves the contestants having to use 6 numbers to make a target 3 digit number in 60 seconds.
The 6 numbers are selected from a range of face-down cards. The contestants have some say over the size of numbers as the top row contains higher numbers such as 100,75,50 etc while the lower rows contain low numbers.
This program uses recursion to solve the problem. I have included a JavaScript version on this page. To let the program attempt to solve a particular problem, enter the target number in the box and the 6 numbers to be used to reach that target in the 6 smaller boxes. If the problem can be solved, a brief summary of how the solution was obtained is printed in the solution box.
Please Note: Although this program usually runs very quickly, if you enter an impossible problem you may find it takes over 2 minutes (depending on the speed of your machine) before it realises it can't be done. Also your browser may alert you to the script running for too long.
The source code is shown below. It uses recursion to make the solution a lot easier. One big advantage of coding this type of algorithm in JavaScript is that we do not have to explicitly free all the memory we allocate. Essentially the function called solver takes a list of numbers as an argument. If simply looks at the first two numbers in that list and makes new numbers from them, by adding, subtracting, multiplying and dividing them. If it hits the target, it returns, otherwise it simply calls itself again with a new list of arguments containing the new number it created and the unused numbers. When there are only 2 elements in the list the solver function also will not call itself again. Also, a string is created keeping track of what we have done so far so that the solution can be printed. Although using a recursive solution is memory intensive compared to simple permutations and combinations of operators and numbers, I think that this method is a more elegant solution and gets round the tricky problem of operator precedence issues that the first method has.
function callSolver()
{
var arrNumbers = Object();
arrNumbers.length = 6;
arrNumbers[1] = new Number(document.frmCountdown.txt1.value);
arrNumbers[2] = new Number(document.frmCountdown.txt2.value);
arrNumbers[3] = new Number(document.frmCountdown.txt3.value);
arrNumbers[4] = new Number(document.frmCountdown.txt4.value);
arrNumbers[5] = new Number(document.frmCountdown.txt5.value);
arrNumbers[6] = new Number(document.frmCountdown.txt6.value);
if(Solver(new Number(document.frmCountdown.txtTarget.value), arrNumbers, "") == false)
{
document.frmCountdown.txtSolution.value = "Failed";
}
}
function Solver(lngTarget, arrUse, strMethod)
{
var i;
var j;
var k;
var n;
var arrNew; br>
var lngNew;
for(i = 1; i <= arrUse.length; i++)
{
for(j = i + 1; j <= arrUse.length; j++)
{
//1. addition
lngNew = arrUse[i] + arrUse[j];
if(lngNew == lngTarget)
{
document.frmCountdown.txtSolution.value =
strMethod + arrUse[i] + "+" + arrUse[j] + "=" + lngTarget;
return true;
}
arrNew = Object();
arrNew.length = arrUse.length - 1;
n = 1;
for(k = 1; k <= arrUse.length; k++)
{
if((k != i) && (k != j))
{
arrNew[n] = arrUse[k];
n++;
}
}
arrNew[n] = lngNew;
if(Solver(lngTarget, arrNew,
strMethod + arrUse[i] + "+" +
arrUse[j] + "=" + lngNew + "; ") == true)
{
return true;
}
if(arrUse[i] > arrUse[j])
{
//2. subtraction a-b
lngNew = arrUse[i] - arrUse[j];
if(lngNew == lngTarget)
{
document.frmCountdown.txtSolution.value =
strMethod + arrUse[i] + "-" + arrUse[j] + "=" + lngTarget;
return true;
}
arrNew = Object();
arrNew.length = arrUse.length - 1;
n = 1;
for(k = 1; k <= arrUse.length; k++)
{
if((k != i) && (k != j))
{
arrNew[n] = arrUse[k];
n++;
}
}
arrNew[n] = lngNew;
if(Solver(lngTarget, arrNew,
strMethod + arrUse[i] + "-" +
arrUse[j] + "=" + lngNew + "; ") == true)
{
return true;
}
}
else
{
//3. subtraction b-a
lngNew = arrUse[j] - arrUse[i];
if(lngNew == lngTarget)
{
document.frmCountdown.txtSolution.value =
strMethod + arrUse[j] + "-" + arrUse[i] + "=" + lngTarget;
return true;
}
arrNew = Object();
arrNew.length = arrUse.length - 1;
n = 1;
for(k = 1; k <= arrUse.length; k++)
{
if((k != i) && (k != j))
{
arrNew[n] = arrUse[k];
n++;
}
}
arrNew[n] = lngNew;
if(Solver(lngTarget, arrNew,
strMethod + arrUse[j] + "-" +
arrUse[i] + "=" + lngNew + "; ") == true)
{
return true;
}
}
//4. multiplication
lngNew = arrUse[i] * arrUse[j];
if(lngNew == lngTarget)
{
document.frmCountdown.txtSolution.value =
strMethod + arrUse[i] + "*" +
arrUse[j] + "=" + lngTarget;
return true;
}
arrNew = Object();
arrNew.length = arrUse.length - 1;
n = 1;
for(k = 1; k <= arrUse.length; k++)
{
if((k != i) && (k != j))
{
arrNew[n] = arrUse[k];
n++;
}
}
arrNew[n] = lngNew;
if(Solver(lngTarget, arrNew,
strMethod + arrUse[i] + "*" +
arrUse[j] + "=" + lngNew + "; ") == true)
{
return true;
}
//5. division a/b
//6. division b/a
//these 2 omitted as they are rarely helpful and so
// only serve to slow the process down
// to add them, simply copy the above style.
// nb. don't follow the route if the numbers don't divide to an integer
// also beware of divide by zero
}
}
}
// Mark Heath
// 21 March 2001