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