SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


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


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

Author
Message
Kevin Duan
Kevin Duan
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 Visits: 72
Comments posted to this topic are about the item A Sudoku solution with set based T-SQL utilizing binary operators.
SQLRNNR
SQLRNNR
SSC-Dedicated
SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)SSC-Dedicated (33K reputation)

Group: General Forum Members
Points: 33480 Visits: 18560
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

Kevin Duan
Kevin Duan
Grasshopper
Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)Grasshopper (15 reputation)

Group: General Forum Members
Points: 15 Visits: 72
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 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 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;



Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search