Solving Sudoku in One SQL Query – Part 3 – Solving the Puzzle

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

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]

)

Æther

A blog

Solving Sudoku in One SQL Query – Part 3 – Solving the Puzzle

0 Comments

Leave a Reply Cancel reply