A new set-based T-SQL solution for Sudoku puzzle

  • Scormer

    SSC Enthusiast

    Points: 184

    Comments posted to this topic are about the item A new set-based T-SQL solution for Sudoku puzzle

  • Scormer

    SSC Enthusiast

    Points: 184

    Sorry, a correction: in the last paragraph in the first section, it should be:

    Its logic is straight forward, and does NOT use any "not exists" logic....

  • Scormer

    SSC Enthusiast

    Points: 184

    Another version of interest:

    You might notice that, in the following update clause

    UPDATE sdk SET Val=Val-(val & combo)

    FROM #Sudoku AS sdk

    JOIN #MapRange r on sdk.id =r.id

    JOIN x ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0

    for each cell, it will only get updated at most once (on the first match if there is any), other impossible values (combo) for the same cell won't be taken out in this iteration. It's a kind of waste. To "fix" this, you can find all distinct impossible values and hash them into one decimal value before the update. This will ensure all found impossible values to be taken out in the same iteration, and will in turn reduce the iteration number. Below is the script. Unfortunately, when looking at the performance, it's even slower!

    USE [tempDB]

    GO

    SET ANSI_NULLS ON

    GO

    SET QUOTED_IDENTIFIER ON

    GO

    CREATE PROCEDURE [dbo].[usp_SolveSudoku_ComboBased_V2] ( @Input VARCHAR(81), @TraceFlag INT = 0 ) AS BEGIN

    SET NOCOUNT ON;

    IF LEN(@Input)<>81 RETURN;

    DECLARE @datetime DATETIME, @UpdateCount INT, @Iterations INT;

    SELECT @datetime = GETDATE(), @UpdateCount = 1, @Iterations = 0;

    --=====>Setup working tables

    CREATE TABLE #num( vInt INT, vBinary INT);

    WITH n (vInt, vBit ) AS (

    SELECT 1, 1 UNION ALL

    SELECT 1+vInt, POWER(2, vInt) FROM n WHERE vInt < 9

    ) INSERT INTO #num SELECT * FROM n;

    CREATE TABLE #Sudoku (id INT, row INT, col INT, blk INT, Val INT, NumOfValues INT);

    WITH n (id, row, col, blk, val) AS (

    SELECT 1, 1, 1 , 1, CASE WHEN SUBSTRING(@Input,1,1)>0 THEN POWER(2, SUBSTRING(@Input,1,1)-1) ELSE 511 END

    UNION ALL

    SELECT id+1, id/9 +1, (id % 9) +1, (id / 27)*3 + ((id % 9)/3+1) ,

    CASE WHEN SUBSTRING(@Input, id+1,1)>0 THEN POWER(2, SUBSTRING(@Input, id+1,1)-1) ELSE 511 END

    FROM n

    WHERE id < 81

    ) INSERT INTO #Sudoku (id,row,col,blk,Val) SELECT * FROM n OPTION (MAXRECURSION 80);

    CREATE TABLE #Combo (Combo INT IDENTITY(1,1), NumOfChoices INT);

    INSERT INTO #Combo SELECT TOP 511 0 FROM SYS.all_parameters;

    UPDATE #Combo set NumOfChoices = (SELECT COUNT(*) FROM #num WHERE Combo & vBinary >0);

    CREATE TABLE #MapRange (ID INT, Range INT);

    INSERT INTO #MapRange SELECT ID, row FROM #Sudoku;

    INSERT INTO #MapRange SELECT ID, col*10 FROM #Sudoku;

    INSERT INTO #MapRange SELECT ID, blk*100 FROM #Sudoku;

    --=====>Solving the puzzle

    WHILE @UpdateCount >0 BEGIN

    -- find all fit combo for each cell

    SELECT s.id, c.combo, c.NumOfChoices

    INTO #temp

    FROM #Sudoku s

    JOIN #Combo c ON s.val -(c.combo & s.val) = 0;

    ;WITH

    -- Put fit combo in all three range context

    a AS (SELECT m.Range, t.Combo, t.NumOfChoices FROM #temp t JOIN #MapRange m ON t.id =m.ID)

    -- Find all enclosed combo in each range

    ,x AS ( SELECT Range, combo FROM a GROUP BY Range, combo HAVING MAX(NumOfChoices) = COUNT(*))

    -- gather all impossible values for each cell

    ,y as ( select sdk.id, (val & combo) as impossibleValues

    FROM #Sudoku AS sdk

    JOIN #MapRange r on sdk.id =r.id

    JOIN x ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0)

    --find distinct impossible binary values for each cell

    ,z as (select distinct id, vBinary from y join #num n on y.impossibleValues & vBinary>0 )

    -- aggregate the impossible binary values so we can subtract them in one-shot

    ,takeOut as (select ID, SUM(vbinary) as toTakeOut from z group by id)

    update sdk set val = val -toTakeOut from #sudoku sdk join takeOut on takeOut.id=sdk.id

    ----------------------------------------------------------------------------------------------

    SELECT @UpdateCount = @@ROWCOUNT, @Iterations = @Iterations+1

    DROP TABLE #temp;

    END

    IF @TraceFlag >0 SELECT 'TotalMilliSeconds' = DATEDIFF(ms, @datetime, GETDATE()), @Iterations AS 'NumberOfIterations';

    --=====>Output the Solution

    UPDATE #Sudoku SET NumOfValues = (SELECT COUNT(*) FROM #num WHERE val & vBinary >0 );

    WITH a AS ( SELECT Row,

    Col,

    v = CASE WHEN @TraceFlag = 0 AND NumOfValues > 1 THEN '_'

    ELSE (SELECT LTRIM(STR(vInt)) FROM #num WHERE val & vBinary >0 FOR XML PATH('')) END

    FROM #Sudoku

    ) SELECT * FROM a PIVOT ( MAX(v) FOR Col in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) AS pvt

    END

    go

    EXEC [usp_SolveSudoku_ComboBased_V2] '029000008030000010000520097070056100000000000006310070760041000050000020800000630' , 1

    BTW, if T-SQL has a bitwise aggregation function (for "&" and "|") , the script can be more elegant and faster.

  • Scormer

    SSC Enthusiast

    Points: 184

    Following is a procedural approach written in Javascript with a HTML wrapper:

    <HTML><script type="text/javascript">

    var currentCell, direction;

    function Doit(){

    currentCell=-1; direction = 1;

    strSudoku=document.getElementById("Input").value;

    a=strSudoku.split(''); // the working Sudoku array

    b=strSudoku.split(''); // the original Sudoku array

    for (i=0; i<81; i++) {a=parseInt(a);}

    while (FindNextCell())

    { a[currentCell]+=1; fit=false;

    while (!fit && a[currentCell]<10) // as long as not a fit and less than 10

    { if (IsValid(currentCell,a)) { fit=true; direction=1;} // if it's a fit, keep going forward

    else a[currentCell]+=1; // not a fit? try next number

    }

    if (!fit && a[currentCell]== 10) {a[currentCell]=0; direction=-1; } //wipe the current cell and going backward

    }

    OutputSudoku(b, "Q", "The original Sudoku is:");

    OutputSudoku(a, "A", (currentCell>80 ? "The solution is:" : "Cannot find a solution:"));

    }

    function FindNextCell()

    { for(var j=currentCell+direction; ;j+=direction)

    { if (j>80 || j<0 ) {currentCell=j; return false;} // beyond boundary

    if (b[j]=="0") // if it is an originally empty cell

    { if (direction==1) {currentCell=j; return true;} // if to find forward

    else { if (a[j]<9) {currentCell=j; return true;} else a[j]=0; } // if backward

    } } }

    function IsValid(x)

    { Xr = Math.floor(x/9)*9; //Row base

    Xc = x % 9; //Column base

    Xb = (Math.floor(x / 27)) * 27 + ( (Math.floor((x % 9)/3)) *3 ); //Block base

    t=a[x];

    for (i = 0; i < 3; i++)

    { for (j = 0; j < 3; j++)

    { if (((Xr+i*3+j) != x) && (a[Xr+i*3+j] ==t)) return false;

    if (((Xc+(i*3+j)*9)!= x) && (a[Xc+(i*3+j)*9] ==t)) return false;

    if (((Xb+i*9 + j) != x) && (a[Xb+i*9 + j] ==t)) return false;

    } }

    return true;

    }

    function OutputSudoku(arrSudoku, targetElement, strHeading )

    { var line = "---------+--------+--------<BR/>";

    strHTML ="<BR/>"+strHeading+"<BR/>"+line;

    for (i = 0; s="|", i < 9; i++) // Row i

    { for (j = 0; j < 9;j++) // Column j

    { s += " " + (arrSudoku==0 ? "_" : arrSudoku)+((j%3==2) ? " |" : "");}

    strHTML += s + "<BR/>"+(i%3 == 2 ? line : "");

    }

    document.getElementById(targetElement).innerHTML=strHTML;

    }

    </script>

    <Body><h1>Sudoku Solution</h1>

    <input ID="Input" type="text" maxlength="81" size="90" name="fname" value="029000008030000010000520097070056100000000000006310070760041000050000020800000630"/>

    <br/><button type="button" onclick="Doit();">Resolve</button>

    <br/><table><tr><td ID="Q"></td><td width="20"></td><td ID="A"></td></tr></table>

    </Body></HTML>

  • brad.mason5

    Hall of Fame

    Points: 3299

    Nice article. I tried it out for 2 puzzle. 1 "extreme" puzzle and looks like SQL has bug. Or I messed up the numbers but looked over it twice.

    http://www.sudoku.ws/extreme-20.htm

    Tried both versions and get same result

    EXEC [usp_SolveSudoku_ComboBased] '600000040005002007729000003090040001000060000400080070300000165200400800050000004',1

    EXEC usp_SolveSudoku_ComboBased_v2 '600000040005002007729000003090040001000060000400080070300000165200400800050000004',1

  • Scormer

    SSC Enthusiast

    Points: 184

    Hi brad.mason5,

    Thanks very much for your comments. You are right. I will take a look see if I can fix this.

    Regards,

    Kevin

  • akljfhnlaflkj

    SSC Guru

    Points: 76202

    Looks great. Think I'll wait a bit for you to get out any issues others find. Thanks.

  • akljfhnlaflkj

    SSC Guru

    Points: 76202

    Iwas Bornready (7/9/2015)


    Looks great. Think I'll wait a bit for you to get out any issues others find. Thanks.

    Same for me too.

  • radek.celuch

    Default port

    Points: 1430

    Hey Kevin! This is really great stuff pointed there! Nice idea to take care of Sudoku in SQL.

    I tried your solution on the harder-hardest-sudoku-ever and it seems to not working properly, but it's really fast, though.

    This post recalled me that I have an attempt to this problem a while ago. My try was to get the answer without using any recursion, loops etc. Just do it with pure-set-based solution.

    So you can find what I did in Sudoku.zip. There are 2 scripts. Sudoku_create.sql creates all the objects. In the script there also are some sudoku boards you can test by truncating Sudoku. Board and inserting there a template. The second script Sudoku_query.sql - as you might guess - is the actual query that returns the solution.

    I wanted to try another attempt with a little different and more normalized design of Sudoku.Board that you can find in Sudoku_2.zip. However, have not got time nor will to do this. But now - thanks to your article I actually might try again.

    And also, I very like the idea of using binary algebra with #num/#combo/#maprange. I am going to check it out in my solution if you don't mind.

    I will appreciate any ideas and suggestions to pure-set-based solution.

  • Scormer

    SSC Enthusiast

    Points: 184

    Hi Radek,

    Thanks for reading this post. Seems you've done a lot on this already. I am really happy that my thoughts can contribute a little bit to your solution. I will be looking forward to it!

    Regards,

    Kevin Duan

  • Michael Meierruth

    SSChampion

    Points: 10051

    On occasion I do the Sudoku in the International New York Times. This version has four additional 3x3 squares (slightly gray) inside the 9x9 puzzle area. Thus instead of 27 areas to be filled with 1-9 you have 31.

    When I get a chance I will adapt your solution to this variant of the puzzle.

  • awen.kerzreho

    SSC Rookie

    Points: 41

    Hi Scormer,

    First of all, thanks for sharing, that was really interesting (and difficult...) to understand the logic behind that piece of code.

    I managed to get a slight improvement on the part where you update the sudoku table. There is not much difference in the execution time (2% to 10% depending on grids and runs, but never longer than original version) but my variation usually cuts the number of iterations by about 30% 😀 .

    In your code, replace lines 54-57

    UPDATE sdk SET Val=Val-(val & combo)

    FROM #Sudoku AS sdk

    JOIN #MapRange r on sdk.id =r.id

    JOIN x ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0

    by

    , y as (

    select distinct sdk.id, sdk.Val, n.vBinary

    from #Sudoku AS sdk

    join #MapRange r on sdk.id =r.id

    join x ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0

    join #num n on combo & vBinary >0

    )

    , z as (

    select id, sum(vBinary) as combo from y group by id

    )

    update sdk set Val = Val-(Val & Combo)

    from #Sudoku as sdk

    inner join z on z.id = sdk.id

    I noticed that your code uses only one (random) enclosed combo to substract it from a cell's value. The idea behind my code is to combine all the enclosed combos that can be subtstracted from the cell's value into one single combo. Since there is no easy way to bitwise-OR all the combos associated to a single cell (or at least, I don't know any), I just extract all the distinct bits (join #num) from all combos in table "y", sum them in table "z" to get the combined combo, and finally update the cell.

    Test grids I used:

    declare @grid char (81)

    set @grid = '029000008030000010000520097070056100000000000006310070760041000050000020800000630' -- Scormer

    set @grid = '600000040005002007729000003090040001000060000400080070300000165200400800050000004' -- brad.mason5 - still failing

    set @grid = '800020907007100005020704000080900070604000809050006030000302060200007300703050002'

    set @grid = '900570100008400000070000900103700009200906003400005201001000050000007600006023004'

    set @grid = '000000700000150000056800009837040605020000070905070234400001520000032000009000000'

  • radek.celuch

    Default port

    Points: 1430

    What about solving a sudoku where there are no combos? Like this one?

  • Scormer

    SSC Enthusiast

    Points: 184

    radek.celuch (5/24/2016)


    What about solving a sudoku where there are no combos? Like this one?

    Yes, I am stuck on some hardest ones, there are some extra logic needs to be applied, just couldn't figure out. Sorry.

    Scormer

Viewing 14 posts - 1 through 14 (of 14 total)

You must be logged in to reply to this topic. Login to reply