May 1, 2008 at 2:45 pm
Comments posted to this topic are about the item A Sudoku solution with set based T-SQL utilizing binary operators.
June 9, 2009 at 1:53 pm
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
July 14, 2009 at 10:18 am
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
This website stores cookies on your computer.
These cookies are used to improve your website experience and provide more personalized services to you, both on this website and through other media.
To find out more about the cookies we use, see our Privacy Policy