Solving Sudoku in One SQL Query – Part 1

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.

Sudoku

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];

Leave a Reply

Your email address will not be published.