Solving SUDOKU thru SQL Code

  • Jus

    SSCrazy

    Points: 2525

    Recently i cross through one article where it says the following SQL Code used in oracle to solve SUDOKU Puzzles.

    for 9x9 sudoku puzzles, the filled in numbers were passed as a string with a space for every unfilled square"

    in the following example, string passed is '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79' ( One space for every unfilled square, if 3 continuous boxes are unfilled, then there should be 3 spaces)

    The following is the the code in Orcale used for the purpose.

    with x( s, ind ) as

    ( select sud, instr( sud, ' ' )

    from ( select '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79' sud from dual )

    union all

    select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )

    , instr( s, ' ', ind + 1 )

    from x

    , ( select to_char( rownum ) z

    from dual

    connect by rownum <= 9

    ) z

    where ind > 0

    and not exists ( select null

    from ( select rownum lp

    from dual

    connect by rownum <= 9

    )

    where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )

    or z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )

    or z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3

    + trunc( ( ind - 1 ) / 27 ) * 27 + lp

    + trunc( ( lp - 1 ) / 3 ) * 6

    , 1 )

    )

    )

    select s

    from x

    where ind = 0

    /

    I request our SQL experts to convert this code into SQL Server compatible code to solve sudoku puzzles.

    You can check the article about this @ http://technology.amis.nl/blog/6404/oracle-rdbms-11gr2-solving-a-sudoku-using-recursive-subquery-factoring

    Regards

    Jus

  • Lynn Pettis

    SSC Guru

    Points: 442334

    Actually, I think you should give it a try first. If you run into problems, post what you have tried and we'll see what we can do to help you.

    This looks like a good training opportunity to learn how to port code. Always a good thing to know.

  • Jus

    SSCrazy

    Points: 2525

    Lynn..you are right..I should have tried first. But when i saw the code i found few oracle objects like dual , connect which am unaware of...hence posted..this was not for any project..just out of curiosity i posted this....if any one can post solution, i can try comparing oracle vs sql server codes and will learn from there........thanks

  • SQLRNNR

    SSC Guru

    Points: 281243

    Late - but maybe still worth it. I'll be posting a blog on it shortly.

    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

  • weitzera

    Hall of Fame

    Points: 3442

    Just learned this yesterday, so I'll post a quick aside: Dual is a dummy object with one row.

    select 'foo' from dual

    is equivalent to the tsql statement

    select 'foo'

    which is invalid in ansi sql



    Dan Guzman - Not the MVP (7/22/2010)
    All questions have to be prefaced by Server version and 'according to MS Docs' or 'my own personal opinion based on how much detail I felt like digging into at the time.'

  • SQLRNNR

    SSC Guru

    Points: 281243

    Blog post[/url] sneak peek.

    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

  • Lynn Pettis

    SSC Guru

    Points: 442334

    SQLRNNR (8/16/2011)


    Blog post[/url] sneak peek.

    Sneak peek didn't work, at least for me.

  • SQLRNNR

    SSC Guru

    Points: 281243

    Lynn Pettis (8/16/2011)


    SQLRNNR (8/16/2011)


    Blog post[/url] sneak peek.

    Sneak peek didn't work, at least for me.

    Crud - I had hoped it would since it worked for me. It is scheduled to post 8/17 at 6AM (Pacific)

    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

  • nwerner

    Right there with Babe

    Points: 768

    I don't care about solving SUDOKU with T-SQL. -- I like to do that myself. Does anyone have code to create guaranteed solvable SUDOKU puzzles?

  • bc_

    Hall of Fame

    Points: 3106

    That is cool SQLRNNR.

    I don't know if this would always work, but this at least works for the given puzzle to return it in 9 x 9:

    SELECT TOP 9 SUBSTRING(s, ROW_NUMBER() OVER (ORDER BY s) * 9 - 8, ROW_NUMBER() OVER (ORDER BY s) * 9 - (ROW_NUMBER() OVER (ORDER BY s) * 9 - 8))

    FROM x

    WHERE ind = 0

    [font="Arial Narrow"]bc[/font]

  • SQLRNNR

    SSC Guru

    Points: 281243

    bc_ (8/17/2011)


    That is cool SQLRNNR.

    I don't know if this would always work, but this at least works for the given puzzle to return it in 9 x 9:

    SELECT TOP 9 SUBSTRING(s, ROW_NUMBER() OVER (ORDER BY s) * 9 - 8, ROW_NUMBER() OVER (ORDER BY s) * 9 - (ROW_NUMBER() OVER (ORDER BY s) * 9 - 8))

    FROM x

    WHERE ind = 0

    Excellent. I think that should work in all cases.

    Thanks much for the help.

    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

  • aaron.reese

    SSChampion

    Points: 13415

    out of interest, does anyone know what the fewest number of completed squares is you need to be able to complete a sudoku with only one solution?

  • nwerner

    Right there with Babe

    Points: 768

  • Cadavre

    SSC-Forever

    Points: 41690

    SQLRNNR (8/16/2011)


    Blog post[/url] sneak peek.

    Nice! Does this improve the performance a little: -

    DECLARE @SudokuGivens VARCHAR(100)

    SET @SudokuGivens = '53 7 6 195 98 6 8 6 34 8 3 17 2 6 6 28 419 5 8 79'

    ;WITH x( s, ind ) AS (

    SELECT @SudokuGivens, Charindex(' ', @SudokuGivens, 1)

    UNION ALL SELECT CAST(Substring(s, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(s, ind + 1, 81) AS VARCHAR(100)),

    Charindex(' ', s, ind + 1)

    FROM x, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)

    WHERE ind > 0

    AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)

    WHERE N = Substring(s, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)

    OR N = Substring(s, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)

    OR N = Substring(s, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1))

    )

    SELECT s

    FROM x

    WHERE ind = 0


    Forever trying to learn
    My blog - http://www.cadavre.co.uk/
    For better, quicker answers on T-SQL questions, click on the following...http://www.sqlservercentral.com/articles/Best+Practices/61537/
    For better, quicker answers on SQL Server performance related questions, click on the following...http://www.sqlservercentral.com/articles/SQLServerCentral/66909/

  • SQLRNNR

    SSC Guru

    Points: 281243

    Testing it now - on a puzzle with fewer givens.

    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

Viewing 15 posts - 1 through 15 (of 28 total)

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