InstantForum.NET v2.9.0SQLServerCentralhttp://www.sqlservercentral.com/Forums/notifications@sqlservercentral.comSun, 26 May 2013 01:34:20 GMT20http://www.sqlservercentral.com/Forums/Topic493912-1264-1.aspxHi SSC Journeyman,Thanks for your great comments. I haven't updated this post for a while. Following is a new version that I should have posted. But I still found puzzles that cannot be solved by this solution (see the examples). More elimination logic needs to be added.Cheers,Kevin Duan[code]USE [tempdb]GOIF 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)ASSET NOCOUNT ONDECLARE @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 rulesSET @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 inputWITH 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 respectivelySELECT @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" onlyshows 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 subrangeSELECT @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 aJOIN ( 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=1WHILE @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 aboveto 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 >0SELECT 'TotalMilliSeconds' = datediff(ms, @datetime, getdate()), @Rule2ExecTimes AS 'Rule2ExecTimes'GO -- An puzzle that could not be solved by this solution, need more elimination logic--EXEC uspSolveSudoku '100600000760080000004000260030706009900508001400201030053000900000010052000002008',1 -- 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 -- Code Cleaning:-- IF OBJECT_ID(N'dbo.uspSolveSudoku', N'P') IS NOT NULL DROP PROCEDURE dbo.uspSolveSudoku;[/code]Tue, 14 Jul 2009 10:18:50 GMTKevin Duanhttp://www.sqlservercentral.com/Forums/Topic493912-1264-1.aspxThis was pretty close to an automated solution.In testing with a new puzzle not provided in the article, the first quadrant was all muddled up. The solution provided was not the actual solution - and the puzzle did have a real solution. I needed to change the numbers for three of the cells.Tue, 09 Jun 2009 13:53:13 GMTSQLRNNRhttp://www.sqlservercentral.com/Forums/Topic493912-1264-1.aspxComments posted to this topic are about the item [B]<A HREF="/scripts/Sudoku/62978/">A Sudoku solution with set based T-SQL utilizing binary operators.</A>[/B]Thu, 01 May 2008 14:45:45 GMTKevin Duan