# A Sudoku solution with set based T-SQL utilizing binary operators.

• Comments posted to this topic are about the item A Sudoku solution with set based T-SQL utilizing binary operators.

• This 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.

Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events

• Hi 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

`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-2 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 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 "" refers to a row,`

`a column or a block. The "" refers to a subset of cells in a .`

`------ RULE #1.1 ------`

`Eliminate determined(d=1) values from un-determined cells in the same range`

`-----------------------`

`*/`

`SET @s-2 = '`

` UPDATE #s`

` SET v = v - (v & sumv)`

` FROM ( SELECT AS 1, sum(v) AS sumv`

` FROM #s WHERE d = 1`

` GROUP BY`

` ) AS t`

` WHERE = t.1 AND d >1;'`

`-- Repeat the range with r, c, b respectively`

`SELECT @SQL1= ISNULL(@SQL1, '')+ REPLACE(@S, '', 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-2 = '`

` UPDATE s`

` SET v = v- (v & vBin)`

` FROM #s s`

` JOIN ( SELECT , vBin, MAX() AS`

` FROM #s`

` JOIN #num AS n ON (v & vBin)>0`

` GROUP BY , vBin`

` HAVING COUNT(DISTINCT ) =1`

` ) AS t ON s. = t. AND`

` s. t. AND (v & vBin)>0 ; '`

`-- Repeat the query for all possible combinations of different range and subrange`

`SELECT @SQL1 = @SQL1+`

` REPLACE( REPLACE(@S, '', a.[Range]),`

` '',`

` 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 AS 1, vBin`

` FROM #s CROSS APPLY (SELECT * FROM #num WHERE (v & vBin)>0) AS vb`

` WHERE d >1`

` GROUP BY , vBin HAVING count (*) =1`

` ) AS t`

` WHERE ( = 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 AS 1, v AS v2`

` FROM #s`

` WHERE d= 2`

` GROUP BY ,v HAVING COUNT(*) =2`

` ) AS t`

` WHERE 1 = AND vv2; '`

`/*`

`==========================================`

`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-2 = REPLACE(`

` CASE WHEN (@Rule2ExecTimes % 6) <3 THEN @SQL3 ELSE @SQL2 END,`

` '',`

` 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-2; -- 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 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;`

Viewing 3 posts - 1 through 2 (of 2 total)

You must be logged in to reply to this topic. Login to reply