A set based T-SQL Solution for Sudoku Puzzle

USE [tempdb]
GO
IF OBJECT_ID(N'dbo.uspSolveSudoku', N'P') IS NOT NULL DROP PROCEDURE dbo.uspSolveSudoku;
GO

CREATE PROCEDURE [uspSolveSudoku] (
 @t VARCHAR(81), -- An 81 characters string representing the puzzle
 @Trace INT = 0 -- the flag for tracing execution information
)
AS
SET NOCOUNT ON
DECLARE
 @datetime DATETIME,
 @S VARCHAR(max), -- temp variable for building sql query strings
 @SQL1 VARCHAR(max), -- query for basic elimination rules
 @SQL2 VARCHAR(max), -- first query for second elimination rules
 @SQL3 VARCHAR(max) -- second query for second elimination rules
SET @datetime = GETDATE(); -- For tracing the execution time

/*
==========================================
Step 1: Create related tables:
==========================================
*/
-- #num table:
-- vInt: sequential number 1,...,9
-- vBin: power(2, vInt-1)

WITH n (vInt, vBin ) AS --
( SELECT 1, 1
 UNION ALL
 SELECT 1+vInt, power(2, vInt) FROM n WHERE vInt < 9
) SELECT * INTO #num FROM n;

--Create working table (9X9 = 81 rows)
CREATE TABLE #s (
 i INT, -- identity number for each cell
 r INT, -- sudoku row numer
 c INT, -- sudoku column number
 b INT, -- sudoku block number
 v INT, -- current possible value(s) using bitmap,
 -- first bit represents 1, second bit for 2 and so on...
 -- A blank cell (all possible values) will be 511(1+2+...+256)
 d AS v%2+v/2%2+v/4%2+v/8%2+v/16%2+v/32%2+v/64%2+v/128%2+v/256%2) ;
 -- the # of possible values in v (i.e., # of bits = "1")
 -- cells having d=1 are determined cells.

-- Load the puzzle working table from input
WITH n (i, r, c, b, v) AS (
 SELECT 1,
 1,
 1 ,
 1,
 CASE WHEN substring(@t,1,1)>0 THEN power(2, substring(@t,1,1)-1) ELSE 511 END
 UNION ALL
 SELECT i+1,
 i/9 +1,
 (i % 9) +1,
 (i / 27)*3 + ((i%9)/3+1) , 
 CASE WHEN substring(@t, i+1,1)>0 THEN power(2, substring(@t, i+1,1)-1) ELSE 511 END
 FROM n
 WHERE i < 81
) INSERT INTO #s (i,r,c,b,v) SELECT * FROM n OPTION (MAXRECURSION 80);

/*
==========================================
Step 2: Build the queries:
==========================================
In the following dynamic queries, the placeholder "<%Range%>" refers to a row,
a column or a block. The "<%SubRange%>" refers to a subset of cells in a <%Range%>.

------ RULE #1.1 ------
Eliminate determined(d=1) values from un-determined cells in the same range
-----------------------
*/SET @S = '
 UPDATE #s
 SET v = v - (v & sumv)
 FROM ( SELECT <%Range%> AS <%Range%>1, sum(v) AS sumv
 FROM #s WHERE d = 1
 GROUP BY <%Range%>
 ) AS t
 WHERE <%Range%> = t.<%Range%>1 AND d >1;'

-- Repeat the range with r, c, b respectively
SELECT @SQL1= ISNULL(@SQL1, '')+ REPLACE(@S, '<%Range%>', SUBSTRING('rbc', vInt,1))
FROM #num WHERE vInt <=3

/*
------ RULE #1.2 ------
If a value only shows in a subrange of a range, then remove it from other 
cells in the same subrange (of different ranges). E.g., if in row #1, "9" only
shows in block #1 (cell[1,1~3]), then it should be removed from other blocks 
in block #1 (cell[2,1..3] and cell[3, 1..3])
-----------------------
*/SET @S = '
 UPDATE s
 SET v = v- (v & vBin)
 FROM #s s
 JOIN ( SELECT <%Range%>, vBin, MAX(<%SubRange%>) AS <%SubRange%>
 FROM #s
 JOIN #num AS n ON (v & vBin)>0
 GROUP BY <%Range%>, vBin
 HAVING COUNT(DISTINCT <%SubRange%>) =1
 ) AS t ON s.<%SubRange%> = t.<%SubRange%> AND 
 s.<%Range%> <> t.<%Range%> AND (v & vBin)>0 ; '

-- Repeat the query for all possible combinations of different range and subrange
SELECT @SQL1 = @SQL1+
 REPLACE( REPLACE(@S, '<%Range%>', a.[Range]),
         '<%SubRange%>',
         b.SubRange
 )
FROM ( SELECT SUBSTRING('rbc', vInt,1) AS [Range]
 FROM #num
 WHERE vInt <=3
 ) AS a
JOIN ( SELECT SUBSTRING('rbc', vInt,1) AS SubRange
 FROM #num
 WHERE vInt <=3
 ) AS b ON a.[Range]<> b.SubRange

/*
------ RULE #2.1 ------
A cell that solely contains a possible value in a range should be determined
-----------------------
*/SET @SQL2 = '
 UPDATE #s SET v = vBin
 FROM ( SELECT <%Range%> AS <%Range%>1, vBin
 FROM #s CROSS APPLY (SELECT * FROM #num WHERE (v & vBin)>0) AS vb
 WHERE d >1
 GROUP BY <%Range%>, vBin HAVING count (*) =1
 ) AS t
 WHERE (<%Range%> = <%Range%>1) AND d >1 AND(v & t.vBin >0);'

/*
------ RULE #2.2 ------
If two cells in a range have and only have the same pair of possible values,
eliminate this pair of values from other cells in the same range
-----------------------
*/
SET @SQL3 = '
 UPDATE #s
 SET v = v- (v & v2)
 FROM ( SELECT <%Range%> AS <%Range%>1, v AS v2
     FROM #s
 WHERE d= 2
 GROUP BY <%Range%>,v HAVING COUNT(*) =2
 ) AS t
 WHERE <%Range%>1 = <%Range%> AND v<>v2; '


/*
==========================================
Step 3: Solve the puzzle!
==========================================
*/
Declare @Before SMALLINT, -- # of solved cells before updates
 @After SMALLINT, -- # of solved cells after updates
 @Rule2ExecTimes INT ;
SELECT @Before = 0, @Rule2ExecTimes = 0;
SELECT @After = COUNT(*) FROM #s WHERE d=1
WHILE @After < 81 AND @Rule2ExecTimes < 100 BEGIN
 WHILE @Before <> @After AND @After < 81 BEGIN
 SELECT @Before = COUNT(*) FROM #s WHERE d = 1
 EXEC (@SQL1); 
 SELECT @After = COUNT(*) FROM #s WHERE d = 1;
 END;
 --Run @SQL2 and @SQL3 on rows/columns/blocks in turn (6 combinations)
 If @After < 81 BEGIN
 SET @S = REPLACE( 
 CASE WHEN (@Rule2ExecTimes % 6) <3 THEN @SQL3 ELSE @SQL2 END, 
 '<%Range%>', 
 substring('rcb', (@Rule2ExecTimes % 3)+1, 1)
 )
 EXEC (@S); 
 SELECT @After = COUNT(*) FROM #s WHERE d = 1;
 SELECT @Rule2ExecTimes = @Rule2ExecTimes + 1
 IF @Trace = 1 AND @Before<> @After PRINT @S; -- Debug
 END;
END ;

/*
==========================================
Step 4: Output the Solution
==========================================
You could also add "GOTO OutputSudoku" anywhere above
to stop the calculation and see the interim results.
*/
OutputSudoku: 
WITH a AS 
( SELECT 'R'+ltrim(str(r)) AS '_', 
 'C'+ltrim(str(c)) as C,
 v = CASE WHEN @Trace = 0 AND d>1 THEN '_'
 ELSE ( SELECT ltrim(str(vInt))
 FROM #num
 WHERE v & vBin >0
 FOR XML PATH('')
 )
 END
 FROM #s
) 
SELECT *
FROM a 
pivot ( max(v) for c in ([C1],[C2],[C3],[C4],[C5],[C6],[C7],[C8],[C9])
 ) AS p

If @Trace >0
SELECT 'TotalMilliSeconds' = datediff(ms, @datetime, getdate()),
 @Rule2ExecTimes AS 'Rule2ExecTimes'
GO


-- An evil level puzzle:
EXEC uspSolveSudoku '080001000030750000100000027000004301400000006701300000520000004000049070000800090',1 

-- Other examples:
-- EXEC uspSolveSudoku '080700000902000000300090020060800200750109043009004070040050009000000706000007030',1
-- EXEC uspSolveSudoku '200060000000900871740008006006080030003000100090030400300700018972005000000090002' ,1
-- EXEC uspSolveSudoku '029000008030000010000520097070056100000000000006310070760041000050000020800000630' , 1
-- EXEC uspSolveSudoku '080700000902000000300090020060800200750109043009004070040050009000000706000007030',1
-- EXEC uspSolveSudoku '060104050008305600200000001800407006006000300700901004500000002007206900040508070',1

-- An puzzle that could not be solved by this solution, need more elimination logic
--EXEC uspSolveSudoku '100600000760080000004000260030706009900508001400201030053000900000010052000002008',1

-- Code Cleaning:
-- IF OBJECT_ID(N'dbo.uspSolveSudoku', N'P') IS NOT NULL DROP PROCEDURE dbo.uspSolveSudoku;