Every now and then I try to create programs to solve puzzles as a way to introduce myself to new ideas & test my coding skills. My latest self-challenge was to write SQL code to solve the Countdown Numbers Round. The idea is; given 6 random numbers (each of which may be used at most once) and using only basic arithmetic (i.e. addition, subtraction, multiplication and division) to get to a randomly generated target number. e.g. Given the numbers **3, 7, 9, 10, 50 & 75**, and the target **396** one solution would be: **3 * (75 + 50 + 7)**.

Here’s how I approached it in T-SQL:

Run this solution at SQL Fiddle

create procedure dbo.CountdownNumberSolver ( @target int output --output used to allow these to be referenced outside of the proc if rnd numbers are generated , @number1 int output , @number2 int output , @number3 int output , @number4 int output , @number5 int output , @number6 int output ) as begin --if the user didn't specify values randomly pick some. -- Small Number (1-10): 1 + 10 * rand() -- Large Number (25,50,75,100): floor(1 + 4 * rand()) * 25 -- Target (1-999): 1 + (999 * rand()) select @target = ISNULL(@target, 1 + (999 * rand())) --I assume 0 isn't a valid solution in countdown? , @number1 = ISNULL(@number1,1 + 10 * rand()) , @number2 = ISNULL(@number2,1 + 10 * rand()) , @number3 = ISNULL(@number3,1 + 10 * rand()) , @number4 = ISNULL(@number4,1 + 10 * rand()) , @number5 = ISNULL(@number5,floor(1 + 4 * rand()) * 25) , @number6 = ISNULL(@number6,floor(1 + 4 * rand()) * 25) --output question /* commented out as sql fiddle only returns first result set select @target [target] , @number1 [#1] , @number2 [#2] , @number3 [#3] , @number4 [#4] , @number5 [#5] , @number6 [#6] */ --records combinations tried so far / partial equations create table #solutions ( id bigint not null identity(1,1) primary key clustered , binaryFlags tinyint not null , number float not null , equation nvarchar(256) not null ) create index ix_solutions_number on #solutions(number) --start with the given values - the id stuff is just to make it easy to reuse this procedure should we want a different # of source numbers insert #solutions select power(2,id) , number , CAST(number as nvarchar(3)) from (values (0,@number1) ,(1,@number2) ,(2,@number3) ,(3,@number4) ,(4,@number5) ,(5,@number6) )x(id, number) declare @previousCount bigint = 0 , @newCount bigint = (select COUNT(1) from #solutions) , @tempCount bigint while @previousCount < @newCount --repeat whilst there are still untried combos and not exists (select top 1 1 from #solutions where number=@target) --and we're still looking for a solution begin set @tempCount = @newCount insert #solutions select a.binaryFlags | b.binaryFlags , case x.o when '+' then a.number + b.number when '-' then a.number - b.number when '*' then a.number * b.number when '/' then a.number / b.number end , '(' + a.equation + ' ' + x.o + ' ' + b.equation + ')' from #solutions a inner join #solutions b on a.binaryFlags & b.binaryFlags = 0 --ensure we're not reusing source numbers and a.id != b.id --minor (potential) optimisation and --no point comparing things we've already checked (this may allow for some performance improvement- it doesn't affect the logic) ( a.id > @previousCount or b.id > @previousCount ) inner join --doing things this way means we only need to find the new combinations from a&b once, not 4 times ( values ('+'), ('-'), ('*'), ('/') ) x(o) on not(x.o = '/' and b.number = 0) --avoid div 0 errors and not(x.o = '-' and a.number - b.number = 0) --don't create 0 value entries (if 0's not an allowed solution this result just adds overhead without value) and not(x.o = '+' and a.number + b.number = 0) --don't create 0 value entries (if 0's not an allowed solution this result just adds overhead without value) and not(x.o = '+' and a.id > b.id) --commutative function optimisation and not(x.o = '*' and a.id > b.id) --commutative function optimisation set @previousCount = @tempCount select @newCount = COUNT(1) from #solutions end --limited to one answer to fit with the game / avoid the assumption that all possible solutions would be listed --(since we exit the above loop the moment we have an answer rather than continuing to check all combos) select top 1 @number1 [#1] , @number2 [#2] , @number3 [#3] , @number4 [#4] , @number5 [#5] , @number6 [#6] , @target [target] , equation [solution] from #solutions where number = @target order by len(equation) --show the shortest equation as that's probably simplest option (fast 1) if object_id('tempdb..#solutions','U') is not null drop table #solutions return 0 end

Here’s an example of how to run it:

--run the proc using random numbers (the proc replaces nulls with random #s) exec dbo.CountdownNumberSolver null, null, null, null, null, null, null --run the proc on user defined values exec dbo.CountdownNumberSolver 396, 7, 3, 10, 9, 50, 75

Advertisements

[…] http://www.dilan4.com/maths/countdown.htm http://www.danieltebbutt.com/countdown.html T-SQL https://developer42.wordpress.com/2013/07/28/countdown-numbers-round-solver-in-t-sql/ […]

Pingback by iOS Countdown Game and Solver Ideas | Alex Hedley — 2013-09-02 @ 19:23