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 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 = '

    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 = '

    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 = 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; -- 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