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.
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
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.
94 95 96 97 98 99 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] ) ), |
0 Comments