WITH Numbers AS
(
SELECT a.Number + 5*(b.Number-1) AS Number
FROM ((SELECT 1 AS Number UNION SELECT 2 UNION SELECT 3 UNION SELECT 4 UNION SELECT 5) a
CROSS JOIN (SELECT 1 AS Number UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) b)
)
INSERT Throw
SELECT 'S' + CONVERT(VARCHAR, Number), Number, 1, Number
FROM Numbers
WHERE Number <= 20
UNION
SELECT 'D' + CONVERT(VARCHAR, Number), Number, 2, 2*Number
FROM Numbers
WHERE Number <= 20
UNION
SELECT 'T' + CONVERT(VARCHAR, Number), Number, 3, 3*Number
FROM Numbers
WHERE Number <= 20
UNION
SELECT 'SBULL', 25, 1, 25
UNION
SELECT 'BULL', 25, 2, 50
ORDER BY 3,4
Note that the Numbers table is constructed via a cross join of a table with 5 numbers and a table with 4 numbers, which is a bit more efficient than simply enumerating 20 numbers. The last 2 select statements add the single-bull and the bull throws for a total of 62 possible throws.
Now the stage is set to compute 2-dart and 3-dart finishes. By joining the Throw table to itself all possible 2-dart finishes can be computed:
SELECT t1.ThrowName + '-' + t2.ThrowName AS 'Combination',
t1.Score + t2.Score AS Score
FROM Throw t1
CROSS JOIN Throw t2
WHERE t2.Factor = 2
ORDER BY Score DESC, t1.Score DESC
The filter Factor = 2 expresses the fact that the last dart has to be a double. To compute all possible 3-dart finishes simply add an extra join:
SELECT t1.ThrowName + '-' + t2.ThrowName + '-' + t3.ThrowName AS 'Combination',
t1.Score + t2.Score + t3.Score AS Score
FROM Throw t1
CROSS JOIN Throw t2
CROSS JOIN Throw t3
WHERE t3.Factor = 2
AND t2.Score <= t1.Score
ORDER BY Score DESC, t1.Score DESC, t2.Score DESC
The filter t2.Score <= t1.Score is added to remove identical combinations from the resultset because T20-T19-BULL is effectively the same combination as T19-T20-BULL. The query yields a total of 41475 records, so there are no less than 41475 possible combinations for a 3-dart finish. By grouping on Score it can be found that 62 can be finished in most different ways with 3 darts, namely in 721 ways! However, this includes all finishes with more darts then necessary (in fact, none of these 721 finishes is optimal since 62 can be finished with 2 darts).
Obviously, the number of combinations with n darts can be found by joining the Throw table to itself n-1 times. But what if we don't want to fix to the number of throws on beforehand but instead want to determine the minimum number of darts needed to finish a given score and the optimal combinations? The solution to this problem is a recursive CTE!
Let's provide the query does the trick and then discuss how it works. Here it is:
WITH Score AS
(
SELECT 1 AS NumberOfThrows,
Factor,
Score,
Score AS LastScore,
CONVERT(VARCHAR(255), ThrowName) AS Combination
FROM Throw
UNION ALL
SELECT s.NumberOfThrows + 1,
s.Factor + t.Factor,
s.Score + t.Score,
t.Score,
CONVERT(VARCHAR(255), s.Combination + '-' + t.ThrowName)
FROM Score s
CROSS JOIN Throw t
WHERE s.NumberOfThrows <= 1
AND s.Factor + t.Factor >= 3*s.NumberOfThrows
AND t.Score <= s.LastScore
),
Finish AS
(
SELECT s.Score + t.Score AS Score,
s.NumberOfThrows + 1 AS NumberOfThrows,
CONVERT(VARCHAR(255), s.Combination + '-' + t.ThrowName) AS Combination
FROM Score s
CROSS JOIN Throw t
WHERE t.Factor = 2
)
SELECT Score, NumberOfThrows, Combination
FROM Finish f
WHERE NumberOfThrows = (SELECT MIN(NumberOfThrows) FROM Finish WHERE Score = f.Score)
ORDER BY Score DESC