Post date: May 29, 2014 12:19:55 AM
"How many routes are there through a 21 point x 21 point grid, from the top left to the bottom right, if you can only go down and right?"
This problem isn't hard to solve using a recursive pathfinding method, but it is too slow at this size. It is a little faster using a constrained combinatorial method, but it is still way too slow. But there is a matrix-based solution for this problem, the kind of thing I haven't touched since linear algebra. It fits the theme of this page, doing things in SQL that were definitely not meant to be done in SQL.
DECLARE @size int = 21, @row int, @col int
CREATE TABLE #Map (x INT NOT NULL, y INT NOT NULL, i BIGINT NOT NULL, PRIMARY KEY (x, y))
-- First row is easy
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < @size - 1
)
INSERT INTO #Map
SELECT i + 1, 1, 1
FROM Integers
-- Same thing for the first column
; WITH Integers (i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < @size - 1
)
INSERT INTO #Map
SELECT 1, i + 1, 1
FROM Integers
WHERE i > 0
-- That's the end of our SQL efficiency. From here it gets ugly.
-- Go through each row starting at row 2.
SET @row = 2
WHILE 1 = 1
BEGIN
-- Fill the columns in the row starting at column 2
SET @col = 2
WHILE 1 = 1
BEGIN
INSERT INTO #Map
SELECT @col, @row, m1.i + m2.i
FROM #Map m1
CROSS JOIN #Map m2
WHERE m1.y = @row AND m1.x = @col - 1
AND m2.y = @row - 1 AND m2.x = @col
SET @col = @col + 1
IF @col > @size BREAK
END -- columns
SET @row = @row + 1
IF @row > @size BREAK
END -- rows
-- The square in the lower right corner of the matrix contains the answer.
SELECT i
FROM #Map
WHERE x = @size
AND y = @size
DROP TABLE #Map