I’ve seen a couple examples of using SQL to solve sudoku puzzles, but most of the ones I’ve seen have used loops or cursors to cycle through and create a correct answer. I feel like if you make a solution that’s procedural like that, you might as well have done it in a language that’s designed to be procedural. The real trick is to write a query that really makes use of a relational database’s parallel projection capabilities to solve a sudoku challenge

We’ll start with the fairly simple sudoku puzzle below.

## The Solution

For those looking for a tl;dr, here is the complete solution for solving a sudoku puzzle with a single query. The first two query simply define and populate the given values of a puzzle, then the last query evaluates and returns a solved sudoku grid. I’ll be posting a couple more times with in depth looks at various sections of the query.

DECLARE @given AS TABLE (Row INT, Col INT, Data INT);
INSERT INTO @given
(Row, Col, Data)
VALUES (2, 1, 9), (3, 1, 2), (4, 1, 5), (6, 1, 6), (8, 1, 3),
(9, 1, 8), (5, 2, 1), (6, 2, 3), (8, 2, 2), (4, 3, 2),
(8, 3, 4), (9, 3, 6), (2, 4, 3), (5, 4, 8), (6, 4, 1),
(7, 4, 2), (3, 5, 8), (5, 5, 9), (7, 5, 4), (3, 6, 7),
(4, 6, 4), (5, 6, 5), (8, 6, 6), (1, 7, 3), (2, 7, 5),
(6, 7, 8), (2, 8, 4), (4, 8, 1), (5, 8, 6), (1, 9, 8),
(2, 9, 2), (4, 9, 7), (6, 9, 4), (7, 9, 5), (8, 9, 1);
WITH Cnt
AS (
SELECT 1 AS [val]
UNION ALL
SELECT [val] + 1
FROM Cnt
WHERE [val] < 9
),
locations
AS (
SELECT [row].[val] AS [row]
,[col].[val] AS [col]
,(([row].[val] - 1) * 9) + [col].[val] AS [loc]
FROM Cnt AS [row]
CROSS APPLY (
SELECT val FROM [Cnt]
) AS [col]
),
groups
AS (
SELECT -- Groups of Rows
FLOOR(([loc] - 1) / 9) + 101 AS [grouping]
,[loc]
FROM [locations]
UNION
SELECT -- Groups of Columns
(([loc] - 1) % 9) + 201 AS [grouping]
,loc
FROM [locations]
UNION
SELECT -- Groups of 3x3 Squares
FLOOR(([row] - 1) / 3) * 3 + FLOOR(([col] - 1) / 3) + 301 [grouping]
,[locations].[loc]
FROM locations
),
Possibilities
AS (
SELECT [g].[Row]
,[g].[Col]
,[locations].[loc]
,[g].[Data]
FROM @given AS [g]
JOIN [locations]
ON [locations].[col] = [g].[Col]
AND [locations].[row] = [g].[Row]
UNION ALL
SELECT [possibility].[row]
,[possibility].[col]
,[possibility].[loc]
,[possibility].[val]
FROM (
SELECT [locations].*
,[possibleValue].[val]
FROM [locations]
LEFT OUTER JOIN @given AS [g]
ON [g].[Col] = [locations].[col]
AND [g].[Row] = [locations].[row]
CROSS APPLY (
SELECT * FROM [Cnt]
) AS [possibleValue]
WHERE [g].[Data] IS NULL --Exclude any cells that are already defined in the given set
) AS [possibility]
WHERE [possibility].[val] NOT IN
(
SELECT [existingCell].[Data]
FROM (
SELECT [locations].[loc]
,[g].[Data]
FROM @given AS [g]
JOIN [locations]
ON [locations].[row] = [g].[Row]
AND [locations].[col] = [g].[Col]
) AS [existingCell]
JOIN [groups] [existingCellGroup]
ON [existingCellGroup].[loc] = [existingCell].[loc]
JOIN [groups] [possibleValueGroup]
ON [existingCellGroup].[grouping] = [possibleValueGroup].[grouping]
AND [existingCellGroup].[loc] != [possibleValueGroup].[loc]
WHERE [possibleValueGroup].[loc] = [possibility].[loc]
)
),
rowStrings
AS (
SELECT CAST([Possibilities].[Data] AS VARCHAR(MAX)) AS string
,[Possibilities].[loc]
FROM [Possibilities]
WHERE [Possibilities].[loc] = 1
UNION ALL
SELECT [rowStrings].[string] + '' + CONVERT(VARCHAR(1), [Possibilities].[Data])
,[Possibilities].[loc]
FROM (
SELECT * FROM [rowStrings] WHERE LEN ([string]) = [loc]
) AS [rowStrings]
JOIN [Possibilities]
ON [rowStrings].[loc] + 1 = [Possibilities].[loc]
WHERE [Possibilities].[Data] NOT IN
(
SELECT SUBSTRING([rowStrings].[string], [g1].[loc], 1)
FROM [groups] [g1]
JOIN [groups] [g2]
ON [g2].[grouping] = [g1].[grouping]
AND [g2].[loc] = [Possibilities].[loc]
AND [g1].[loc] < [Possibilities].[loc]
)
),
correctAnswer
AS (
SELECT [l].[row] AS [Row]
,[l].[col] AS [Col]
,SUBSTRING(string, l.[loc], 1) AS [Val]
FROM (
-- If any of the recursive groups gets to and prints the 81 location, that means
-- everything before it is valid
SELECT * FROM rowStrings WHERE [rowStrings].[loc] = 81
) [cte]
CROSS APPLY (
SELECT * FROM [locations]
) [l]
)
SELECT [Row],[1],[2],[3],[4],[5],[6],[7],[8],[9]
FROM (
SELECT * FROM correctAnswer
) AS SourceTable PIVOT
( MAX([Val]) FOR [Col] IN ([1], [2], [3], [4], [5], [6], [7], [8], [9]) ) AS PivotTable
ORDER BY [Row];