Please read the inline comments.
Please read the inline comments.
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;