Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase

A Sudoku solution with set based T-SQL utilizing binary operators. Expand / Collapse
Author
Message
Posted Thursday, May 1, 2008 2:45 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Thursday, March 17, 2011 9:46 AM
Points: 5, Visits: 72
Comments posted to this topic are about the item A Sudoku solution with set based T-SQL utilizing binary operators.
Post #493912
Posted Tuesday, June 9, 2009 1:53 PM


SSCoach

SSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoachSSCoach

Group: General Forum Members
Last Login: Yesterday @ 6:12 PM
Points: 18,083, Visits: 16,117
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
Post #731833
Posted Tuesday, July 14, 2009 10:18 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Thursday, March 17, 2011 9:46 AM
Points: 5, 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;


Post #752844
« Prev Topic | Next Topic »

Add to briefcase

Permissions Expand / Collapse