Several times I have run into a conversion where I have needed to take a table that stores key value pairs into a table that lists all values for a given record.

The table look something like this:

What I really wanted was something like this:

This is kind of like a PIVOT function, but since there can be a varied number of distinct records in the FIELD column, a pivot won’t always work.

What we can do is create a dynamic sql statement that will scan the distinct FIELD column and create a table for us based on the elements in the column.

DECLARE @selectpiece VARCHAR(1000)
   ,@field VARCHAR(1000)
   ,@columnDef VARCHAR(1000)
   ,@selectquery VARCHAR(MAX)
   ,@insertQuery VARCHAR(MAX)
   ,@createQuery VARCHAR(MAX)
         
SET @createQuery = 'CREATE TABLE dbo.TempElements (ITEM_ID INT'
SET @selectQuery = 'SELECT ITEM_ID'
SET @insertQuery = 'INSERT INTO dbo.TempElements (ITEM_ID'
 
DECLARE cur CURSOR FAST_FORWARD READ_ONLY
FOR
SELECT DISTINCT
        ',MAX(CASE WHEN [ELEMENT_DESC] = ''' + [ELEMENT_DESC] + '''
            THEN COALESCE([EL].[LIST_DESC],[DETAIL_VALUE])
            ELSE NULL
          END) AS [' + [ELEMENT_DESC] + ']' AS fieldSelect
       ,',[' + [ELEMENT_DESC] + ']' AS ColumnName
       ,',[' + [ELEMENT_DESC] + '] VARCHAR(MAX)' AS ColumnDef
FROM    [dbo].[ATTRIBUTE_ELEMENT] AS AE
WHERE   [ELEMENT_ID] IN (SELECT [ELEMENT_ID]
                         FROM   [ITEM_DETAIL] AS ID)
 
OPEN cur
FETCH NEXT FROM cur INTO @selectpiece, @field, @columnDef
WHILE @@FETCH_STATUS = 0
    BEGIN
     
        SET @createQuery += @columnDef
        SET @insertQuery += @field
        SET @selectQuery += @selectpiece
 
        FETCH NEXT FROM cur INTO @selectpiece, @field, @columnDef
    END
 
CLOSE cur
DEALLOCATE cur
 
SET @createQuery += ')'
 
SET @insertQuery += ')' + @selectquery + '
         FROM   [dbo].[ITEM_DETAIL] AS ID
                LEFT JOIN [dbo].[ELEMENT_LIST] AS EL
                    ON [ID].[ELEMENT_ID] = [EL].[ELEMENT_ID]
                       AND [ID].[LIST_ID] = [EL].[LIST_ID]
                JOIN [dbo].[ATTRIBUTE_ELEMENT] AS AE
                    ON [ID].[ELEMENT_ID] = [AE].[ELEMENT_ID]
            GROUP BY ITEM_ID'
 
EXEC sp_sqlexec @createQuery
EXEC sp_sqlexec @insertQuery

Okay, now that we have the general framework we can start writing the pieces that deal with the values that were given to us in the puzzle. The first thing I’m going to do is create a table that contains each possible value for each cell based on the values that are already in the solution.

Possibilities
  AS (
      SELECT    [g].[Row] -- first select just sets the value for the given locations.
               ,[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] -- I join to the given values to exclude these below
                        ON [g].[Col] = [locations].[col]
                           AND [g].[Row] = [locations].[row]
                 CROSS APPLY (
                              SELECT * FROM [Cnt] -- Join to all values 1-9
                             ) AS [possibleValue]
                 WHERE  [g].[Data] IS NULL --Exclude cells already defined in the given set
                ) AS [possibility]
      WHERE     [possibility].[val] NOT IN -- At this point, every cell not in the given set is
            (
                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]
            )
     ),

First we get all the cells that are already given to us. These cells will only have one valid option. Next we need to union those with all the possible values for all the other cells. We could just include all values 1 thru 9 for each of these cells, but we already know that some values will be impossible because they already exist in a group that the cell belongs to. So to reduce our sample space, we do a check to see if the value already exists in any of the cells that are a member of a group that our cell is a member of.

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]
            )
     ),

In this post, I’ll be diving deep into the code that was presented in this post.

Recursive CTEs

My solution utilizes a lot of recursive common table expressions (CTEs). CTEs are a simple way of defining a temporary projection in T-SQL that can be referenced multiple times later on in a query. Their real power, however, lies in their ability to be self-referencing and thus recursive. In a recursive CTE, we define an initial projection and UNION ALL that with a projection that references the table currently being defined.

Since this puzzle is all about digits 1 through 9, I need to make something that will get me those values to work with.

;WITH Cnt AS 
(
   SELECT 1 AS [val]
     UNION ALL
   SELECT [val] + 1
   FROM Cnt -- This is the table I'm creating right now, A SELF-REFERENCING DEFINITION!!!
   WHERE [val] < 9
)

/*
val
1
2
...
8
9
*/

This is an easy way to get the digits we need without having to list them all out. The first statement in the expression gives the basis of the recursion (1), then we UNION ALL to the Cnt table, selecting the value in the table + 1. Initially Cnt has a single record with [val] = 1. Then we union that with a record that is [val] + 1 = 2. This continues until the constraint on the second selection is no longer true. Once [val] = 9, we cannot union it again and we end up with a table of values 1 through 9.

Assigning Each Cell

Next, I want to get a set of all the possible locations in the grid with values ranging from 1 to 81. I could do another CTE like the one I just did, but I already have values 1 to 9, I can utilize my Cnt table to create my location table.

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 ( val FROM [Cnt] ) AS [col]
	 ),

/* locations table contents
row	col	loc
1	1	1
1	2	2
...
...
9	8	80
9	9	81
*/

Assigning Cells to Groups

In the game of Sudoku, each cell contains a digit that is unique within the row, column, and square that the cell is a member of. In order to facilitate checking that the value is unique, we will create a table that defines all the groups that each cell is a member of. The row and column groups are fairly easy to define, but the nine 3×3 boxes are a bit more difficult. In order to better set these groupings apart, I prefix the row groupings with a 10, the column groupings with a 20 and the box groupings with a 30.

This will allow us to cross-reference any locations to see if a particular value already exists. For instance, if I’m looking at the value in location 19, I’ll need to look at all the locations that are part of the groupings 103, 201, and 301 to see if the value I want to put in that location is already in any of the other locations in those groups.

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
     ),

The first two select clauses are retrieving the row and column groupings respectively, then the third grouping is creating groups for the nine 3×3 boxes in the grid. With these available to us, the job of building up a valid solution will be much easier.

/*
grouping  loc
101      1  -- Rows
101      2
...      
101      8
101      9
102      10
..       
102      18
103      19
...      
109      81
201      1  -- Columns
201      10
201      19
201      28
201      37
201      46
201      55
201      64
201      73
202      2
...      
202      74
203      3
...      
209      81
301      1  -- Squares
301      2
301      3
301      10
301      11
301      12
301      19
301      20
301      21
302      4
...      
302      24
303      7
...      
309      81
*/

Now I have all the framework I need to begin solving the sudoku puzzle. I have each of the 9 digits that I need; I have have given each cell in the grid a unique value; and I have made a listing of the groupings of cells that need to contain each of the 9 digits. In the next post I will walk through the code that takes the given values and builds out the correct solution.

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