Solve Sudoku with T-SQL - Part 1

  • bevanward

    SSC Eights!

    Points: 855

    Comments posted to this topic are about the item Solve Sudoku with T-SQL - Part 1

  • Geoff Johns

    SSC Veteran

    Points: 265

    Interesting article - thank you - I couldn't find the code download link .. is it me or the website ?
    KR Geoff Johns

  • bevanward

    SSC Eights!

    Points: 855

    Geoff Johns - Tuesday, February 20, 2018 12:49 AM

    Interesting article - thank you - I couldn't find the code download link .. is it me or the website ?
    KR Geoff Johns

    Hi Geoff
    It appears not to be there so have sent to admin so hopefully they can re-add otherwise is attached for your reference

    Hope you enjoy - next part of article includes optimisation and is much much faster!!!

    Thanks for mentioning
    Cheers
    Bevan

  • bevanward

    SSC Eights!

    Points: 855

    bevanward - Tuesday, February 20, 2018 1:11 AM

    Geoff Johns - Tuesday, February 20, 2018 12:49 AM

    Interesting article - thank you - I couldn't find the code download link .. is it me or the website ?
    KR Geoff Johns

    Hi Geoff
    It appears not to be there so have sent to admin so hopefully they can re-add otherwise is attached for your reference

    Hope you enjoy - next part of article includes optimisation and is much much faster!!!

    Thanks for mentioning
    Cheers
    Bevan

    use tempdb
    go

    if object_id('dbo.sp_sudoku_solve_simple') is not null
        drop procedure dbo.sp_sudoku_solve_simple
    go

    create procedure dbo.sp_sudoku_solve_simple @PuzzleIn char(81) as

    /*

    Author:        Bevan Ward
    Date:        21-Jan-2018
    Purpose:    The following stored procedure solves Sudoku puzzles via a single select statement. It is NOT intended to be used for puzzles harder than absolute beginner level.
                A method showing a highly optimised approach will be provided next article!

    Copyright:    Bevan Ward

    Syntax:        exec dbo.sp_sudoku_solve_simple @PuzzleIn = '<81 character puzzle - 0 represents blank cell>'
    Example:    exec sp_sudoku_solve_simple '023780460000620000060304080001000534280000097439000100010205040000036000056018370'

    -- Set of 10 simple puzzles
    exec sp_sudoku_solve_simple '023780460000620000060304080001000534280000097439000100010205040000036000056018370'
    exec sp_sudoku_solve_simple '600050002010702040000346000084000590509000207032000480000165000020407060300090004'
    exec sp_sudoku_solve_simple '800259004040010070000407000302080506580302091607040302000504000060090020700826009'
    exec sp_sudoku_solve_simple '703200104054019380000500000070000805060000030308000090000001000035920460407008903'
    exec sp_sudoku_solve_simple '700200008020405070004080300060508037009000800180607020001070600050903010600004003'
    exec sp_sudoku_solve_simple '000400000004063200809000503090030005040658030600010070901000804005840100000007000'
    exec sp_sudoku_solve_simple '007400803000206001000085700026000039004000100370000680908620000000108000630009200'
    exec sp_sudoku_solve_simple '019600430000098000002005100098074001020000080700850620007500800000730000056001970'
    exec sp_sudoku_solve_simple '280060079100007006070930080907000605008000700040000090090025060800600002650010047'
    exec sp_sudoku_solve_simple '107608209840050036000000000300106004060000090200305007000000000430060052508209301'

    */

    set nocount off

    declare @SQL varchar(max) =''
    declare @Select varchar(max) =''
    declare @Exclusion varchar(max) =''
    declare @PuzzleSolution char(81)

    /* 81 long number table of row, column and block mapping */
    create table #tGrid (CoordinateID int, RowNum int, ColumnNum int, BlockNum int)
    create clustered index IDX01_tGrid on #tGrid (CoordinateID)

    /* output solutions - write to table so can display as 9x9 grids in final output */
    create table #solutions (SolutionID int, [1] char(1), [2] char(1), [3] char(1), [4] char(1), [5] char(1), [6] char(1), [7] char(1), [8] char(1), [9] char(1), [10] char(1), [11] char(1), [12] char(1), [13] char(1), [14] char(1), [15] char(1), [16] char(1), [17] char(1), [18] char(1), [19] char(1), [20] char(1), [21] char(1), [22] char(1), [23] char(1), [24] char(1), [25] char(1), [26] char(1), [27] char(1), [28] char(1), [29] char(1), [30] char(1), [31] char(1), [32] char(1), [33] char(1), [34] char(1), [35] char(1), [36] char(1), [37] char(1), [38] char(1), [39] char(1), [40] char(1), [41] char(1), [42] char(1), [43] char(1), [44] char(1), [45] char(1), [46] char(1), [47] char(1), [48] char(1), [49] char(1), [50] char(1), [51] char(1), [52] char(1), [53] char(1), [54] char(1), [55] char(1), [56] char(1), [57] char(1), [58] char(1), [59] char(1), [60] char(1), [61] char(1), [62] char(1), [63] char(1), [64] char(1), [65] char(1), [66] char(1), [67] char(1), [68] char(1), [69] char(1), [70] char(1), [71] char(1), [72] char(1), [73] char(1), [74] char(1), [75] char(1), [76] char(1), [77] char(1), [78] char(1), [79] char(1), [80] char(1), [81] char(1))

    /* Fixed puzzle values */
    create table #tFixed (CoordinateID int, Value int)

    /* options */
    create table #tOption (CoordinateID int, Value int)
    create clustered index IDX01_tOption on #tOption (CoordinateID)

    /* Construct references for row, column and block CoordinateID logic */
    insert into #tGrid (CoordinateID, RowNum, ColumnNum, BlockNum) values (1,1,1,1),(2,1,2,1),(3,1,3,1),(4,1,4,2),(5,1,5,2),(6,1,6,2),(7,1,7,3),(8,1,8,3),(9,1,9,3),(10,2,1,1),(11,2,2,1),(12,2,3,1),(13,2,4,2),(14,2,5,2),(15,2,6,2),(16,2,7,3),(17,2,8,3),(18,2,9,3),(19,3,1,1),(20,3,2,1),(21,3,3,1),(22,3,4,2),(23,3,5,2),(24,3,6,2),(25,3,7,3),(26,3,8,3),(27,3,9,3),(28,4,1,4),(29,4,2,4),(30,4,3,4),(31,4,4,5),(32,4,5,5),(33,4,6,5),(34,4,7,6),(35,4,8,6),(36,4,9,6),(37,5,1,4),(38,5,2,4),(39,5,3,4),(40,5,4,5),(41,5,5,5),(42,5,6,5),(43,5,7,6),(44,5,8,6),(45,5,9,6),(46,6,1,4),(47,6,2,4),(48,6,3,4),(49,6,4,5),(50,6,5,5),(51,6,6,5),(52,6,7,6),(53,6,8,6),(54,6,9,6),(55,7,1,7),(56,7,2,7),(57,7,3,7),(58,7,4,8),(59,7,5,8),(60,7,6,8),(61,7,7,9),(62,7,8,9),(63,7,9,9),(64,8,1,7),(65,8,2,7),(66,8,3,7),(67,8,4,8),(68,8,5,8),(69,8,6,8),(70,8,7,9),(71,8,8,9),(72,8,9,9),(73,9,1,7),(74,9,2,7),(75,9,3,7),(76,9,4,8),(77,9,5,8),(78,9,6,8),(79,9,7,9),(80,9,8,9),(81,9,9,9)

    /*
    ------------------------------------------------------------------------------------------------------------------------------------
    STORE PUZZLE
    ------------------------------------------------------------------------------------------------------------------------------------
    */

    /* add fixed puzzle cells -- 0 for empty cells - row of first 9 values and so forth */
    insert into #tFixed (CoordinateID, Value)
        select CoordinateID, substring(@PuzzleIn,CoordinateID,1) Value
        from #tGrid
        where substring(@PuzzleIn,CoordinateID,1) != 0

    insert into #tOption (CoordinateID, Value)
            select CoordinateID, Num from #tGrid a cross join
                (select top 9 ROW_NUMBER() over (order by CoordinateID) Num from #tGrid) b
            /* exclude fixed coordinates*/
            where not exists
            (select 1 from #tFixed c where a.CoordinateID = c.CoordinateID)
            /* exclude row */
            and not exists
                (select 1 from #tFixed c inner join #tGrid d on c.CoordinateID = d.CoordinateID where a.RowNum = d.RowNum and b.Num = c.Value)
            /* exclude column */
            and not exists
                (select 1 from #tFixed c inner join #tGrid d on c.CoordinateID = d.CoordinateID where a.ColumnNum = d.ColumnNum and b.Num = c.Value)
            /* exclude value same BlockNum */
            and not exists
                (select 1 from #tFixed c inner join #tGrid d on c.CoordinateID = d.CoordinateID where a.BlockNum = d.BlockNum and b.Num = c.Value)
            /* add back fixed values */
            union
                select CoordinateID, Value from #tFixed

    --------------------
    /*    SOLVE    */
    --------------------
    set @Select = ''
    set @Exclusion = ''
    set @SQL = ''

    set @Select = ''
    set @Exclusion = ''
    set @SQL = ''

    /*produces 81 values in row preference order a row is one permutation of possible values*/
    SELECT @Select = stuff(
        (select 'cross join'+'(select Value ['+CoordinateID+'] from #tOption where CoordinateID = '+CoordinateID+') ['+CoordinateID+']' from
        (select distinct cast(CoordinateID as varchar(3)) CoordinateID from #tOption) b
    order by cast(CoordinateID as int) FOR XML PATH('')), 1, 10, '')

    /* row, column or block exclusions - all one way permutations with the CoordinateID > other */
    select @Exclusion = @Exclusion + ' and ['+cast(l.CoordinateID as varchar(5))+'] <> ['+cast(r.CoordinateID as varchar(5))+']'
    from #tGrid l cross join #tGrid r
    where (l.RowNum = r.RowNum or l.ColumnNum = r.ColumnNum or l.BlockNum = r.BlockNum) and r.CoordinateID > l.CoordinateID

    /* run whole thing - insert into #solution*/

    /* solve */
    set @SQL = 'select ROW_NUMBER() over (order by [1] asc) SolutionID, *
    from (select * from '+@Select+' where 1 = 1 '+@Exclusion+') x '

    insert into #solutions
        exec (@SQL)

    /* store solution in @PuzzleSolution */
    select top 1 @PuzzleSolution = [1]+[2]+[3]+[4]+[5]+[6]+[7]+[8]+[9]+[10]+[11]+[12]+[13]+[14]+[15]+[16]+[17]+[18]+[19]+[20]+[21]+[22]+[23]+[24]+[25]+[26]+[27]+[28]+[29]+[30]+[31]+[32]+[33]+[34]+[35]+[36]+[37]+[38]+[39]+[40]+[41]+[42]+[43]+[44]+[45]+[46]+[47]+[48]+[49]+[50]+[51]+[52]+[53]+[54]+[55]+[56]+[57]+[58]+[59]+[60]+[61]+[62]+[63]+[64]+[65]+[66]+[67]+[68]+[69]+[70]+[71]+[72]+[73]+[74]+[75]+[76]+[77]+[78]+[79]+[80]+[81] from #solutions
        

    /* show puzzle */
    select RowNum, [1],[2],[3],[4],[5],[6],[7],[8],[9]
    from
        (select RowNum, ColumnNum, case when substring(@PuzzleIn,CoordinateID,1) != 0 then substring(@PuzzleIn,CoordinateID,1) end Value from #tGrid) as base
    pivot
    (min(Value) for ColumnNum in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) as pt

    /* Show options */
    select RowNum, [1],[2],[3],[4],[5],[6],[7],[8],[9]
    from
        (select distinct RowNum, ColumnNum,
            (SELECT stuff(
                (select ','+cast(Value as char(1)) from
                #tOption b where a.CoordinateID = b.CoordinateID
            FOR XML PATH('')), 1, 1, '')) Value
             from #tGrid a) as base
    pivot (min(Value) for ColumnNum in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) as pt

    /* show solution */
    select RowNum, [1],[2],[3],[4],[5],[6],[7],[8],[9]
    from
        (select RowNum, ColumnNum, case when substring(@PuzzleSolution,CoordinateID,1) != 0 then substring(@PuzzleSolution,CoordinateID,1) end Value from #tGrid) as base
    pivot (min(Value) for ColumnNum in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) as pt
    go

  • Richard M.

    SSCertifiable

    Points: 7288

    Very interesting Bevan! Thanks for article. Can't wait for next part!

    _______________________________________________________________________
    For better assistance in answering your questions, click here[/url]

  • Dude76

    Mr or Mrs. 500

    Points: 585

    This code is interesting but seems to be completly bugged :/
    I ran the first sample : exec sp_sudoku_solve_simple '023780460000620000060304080001000534280000097439000100010205040000036000056018370'
    the exposed solution is completly false, and almost alls initals values have been lost.
    #    1    2    3    4    5    6    7    8    9
    1    5    8    9    4    6    2    1    7    5 (0x3, 2x5, all initials lost)
    2    3    1    2    6    7    3    5    4    2 (2x2, 2x3, 0x8, 0x9, initial 2 lost)
    3    8    9    6    7    3    1    8    9    2 (0x4, 0x5, 2x8, 2x9, all initials lost)
    4    5    3    4    2    8    5    7    1    4 (2x4, 2x5, 0x6, 0x9, initials 1,5,3 lost)
    5    3    6    9    7    4    3    9    5    8 (0x1, 0x2, 2x3, 2x9, all initials lost)
    6    6    7    1    2    8    3    1    8    2 (2x1, 2x2, 0x4, 0x5, 2x8, 0x9, initials 439 lost)
    7    7    9    5    9    4    6    7    4    2 (0x1, 0x3, 2x4, 2x7, 0x8, 2x9, all initials lost)
    8    9    3    6    4    8    1    5    9    5 (0x2, 2x5, 0x7, 2x9, all initials lost)
    9    6    4    1    8    3    6    7    2    1 (2x1, 0x5, 2x6, 2x9, all initials lost)

    and so on for the columns.
    I'll take a deeper look inside tonight.

    Did i have miss something from your code or the article ?


    My MCP Transcript (ID : 692471 Access : 109741229)

  • Richard M.

    SSCertifiable

    Points: 7288

    Same thing here. I used the code attached to the article, and the result set has almost all initial values replaced with other values and the results is not valid either.

    _______________________________________________________________________
    For better assistance in answering your questions, click here[/url]

  • bevanward

    SSC Eights!

    Points: 855

    Dude76 - Tuesday, February 20, 2018 6:06 AM

    This code is interesting but seems to be completly bugged :/
    I ran the first sample : exec sp_sudoku_solve_simple '023780460000620000060304080001000534280000097439000100010205040000036000056018370'
    the exposed solution is completly false, and almost alls initals values have been lost.
    #    1    2    3    4    5    6    7    8    9
    1    5    8    9    4    6    2    1    7    5 (0x3, 2x5, all initials lost)
    2    3    1    2    6    7    3    5    4    2 (2x2, 2x3, 0x8, 0x9, initial 2 lost)
    3    8    9    6    7    3    1    8    9    2 (0x4, 0x5, 2x8, 2x9, all initials lost)
    4    5    3    4    2    8    5    7    1    4 (2x4, 2x5, 0x6, 0x9, initials 1,5,3 lost)
    5    3    6    9    7    4    3    9    5    8 (0x1, 0x2, 2x3, 2x9, all initials lost)
    6    6    7    1    2    8    3    1    8    2 (2x1, 2x2, 0x4, 0x5, 2x8, 0x9, initials 439 lost)
    7    7    9    5    9    4    6    7    4    2 (0x1, 0x3, 2x4, 2x7, 0x8, 2x9, all initials lost)
    8    9    3    6    4    8    1    5    9    5 (0x2, 2x5, 0x7, 2x9, all initials lost)
    9    6    4    1    8    3    6    7    2    1 (2x1, 0x5, 2x6, 2x9, all initials lost)

    and so on for the columns.
    I'll take a deeper look inside tonight.

    Did i have miss something from your code or the article ?

    Dude76 - Tuesday, February 20, 2018 6:06 AM

    This code is interesting but seems to be completly bugged :/
    I ran the first sample : exec sp_sudoku_solve_simple '023780460000620000060304080001000534280000097439000100010205040000036000056018370'
    the exposed solution is completly false, and almost alls initals values have been lost.
    #    1    2    3    4    5    6    7    8    9
    1    5    8    9    4    6    2    1    7    5 (0x3, 2x5, all initials lost)
    2    3    1    2    6    7    3    5    4    2 (2x2, 2x3, 0x8, 0x9, initial 2 lost)
    3    8    9    6    7    3    1    8    9    2 (0x4, 0x5, 2x8, 2x9, all initials lost)
    4    5    3    4    2    8    5    7    1    4 (2x4, 2x5, 0x6, 0x9, initials 1,5,3 lost)
    5    3    6    9    7    4    3    9    5    8 (0x1, 0x2, 2x3, 2x9, all initials lost)
    6    6    7    1    2    8    3    1    8    2 (2x1, 2x2, 0x4, 0x5, 2x8, 0x9, initials 439 lost)
    7    7    9    5    9    4    6    7    4    2 (0x1, 0x3, 2x4, 2x7, 0x8, 2x9, all initials lost)
    8    9    3    6    4    8    1    5    9    5 (0x2, 2x5, 0x7, 2x9, all initials lost)
    9    6    4    1    8    3    6    7    2    1 (2x1, 0x5, 2x6, 2x9, all initials lost)

    and so on for the columns.
    I'll take a deeper look inside tonight.

    Did i have miss something from your code or the article ?

    Hi Dude76
    YES - there is an order by missing from the code that generates the select part of the statement. It should read

    /*produces 81 values in row preference order a row is one permutation of possible values*/
    SELECT @Select = stuff(
        (select 'cross join'+'(select Value ['+CoordinateID+'] from #tOption where CoordinateID = '+CoordinateID+') ['+CoordinateID+']' from
        (select distinct cast(CoordinateID as varchar(3)) CoordinateID from #tOption) b
    order by cast(CoordinateID as int) FOR XML PATH('')), 1, 10, '')

    The current code displays as 1, 10, 11, etc so results are complete garbage!

    Thanks for finding this - was a last minute change - clearly untested!!!
    Thanks
    Bevan

  • bevanward

    SSC Eights!

    Points: 855

    Richard M. - Tuesday, February 20, 2018 6:47 AM

    Same thing here. I used the code attached to the article, and the result set has almost all initial values replaced with other values and the results is not valid either.

    YES - there is an order by missing from the code that generates the select part of the statement. It should read

    /*produces 81 values in row preference order a row is one permutation of possible values*/
    SELECT @Select = stuff(
        (select 'cross join'+'(select Value ['+CoordinateID+'] from #tOption where CoordinateID = '+CoordinateID+') ['+CoordinateID+']' from 
        (select distinct cast(CoordinateID as varchar(3)) CoordinateID from #tOption) b 
    order by cast(CoordinateID as int) FOR XML PATH('')), 1, 10, '') 

    The current code displays as 1, 10, 11, etc so results are complete garbage!

    Thanks for finding this - was a last minute change - clearly untested!!!
    Thanks
    Bevan

  • bevanward

    SSC Eights!

    Points: 855

    Dude76 - Tuesday, February 20, 2018 6:06 AM

    This code is interesting but seems to be completly bugged :/
    I ran the first sample : exec sp_sudoku_solve_simple '023780460000620000060304080001000534280000097439000100010205040000036000056018370'
    the exposed solution is completly false, and almost alls initals values have been lost.
    #    1    2    3    4    5    6    7    8    9
    1    5    8    9    4    6    2    1    7    5 (0x3, 2x5, all initials lost)
    2    3    1    2    6    7    3    5    4    2 (2x2, 2x3, 0x8, 0x9, initial 2 lost)
    3    8    9    6    7    3    1    8    9    2 (0x4, 0x5, 2x8, 2x9, all initials lost)
    4    5    3    4    2    8    5    7    1    4 (2x4, 2x5, 0x6, 0x9, initials 1,5,3 lost)
    5    3    6    9    7    4    3    9    5    8 (0x1, 0x2, 2x3, 2x9, all initials lost)
    6    6    7    1    2    8    3    1    8    2 (2x1, 2x2, 0x4, 0x5, 2x8, 0x9, initials 439 lost)
    7    7    9    5    9    4    6    7    4    2 (0x1, 0x3, 2x4, 2x7, 0x8, 2x9, all initials lost)
    8    9    3    6    4    8    1    5    9    5 (0x2, 2x5, 0x7, 2x9, all initials lost)
    9    6    4    1    8    3    6    7    2    1 (2x1, 0x5, 2x6, 2x9, all initials lost)

    and so on for the columns.
    I'll take a deeper look inside tonight.

    Did i have miss something from your code or the article ?

    I have fixed it and the it has been added to the site. Thanks for this!!
    Was a missing order by so the fields were coming through in the order 1, 10, 11, 12, etc and stored into a table ordered in sequence!!
    Thanks
    Bevan

  • SQL Guy 1

    SSCoach

    Points: 15730

    There was a great article how to solve Sudoku by Itzik Ben Gun about 12 years ago in SQL Server Magazine.

  • Richard M.

    SSCertifiable

    Points: 7288

    Thanks Bevan! Seems that order clause fixed the issue. Look like the output is now correct.

    _______________________________________________________________________
    For better assistance in answering your questions, click here[/url]

  • bevanward

    SSC Eights!

    Points: 855

    Richard M. - Tuesday, February 20, 2018 8:56 AM

    Thanks Bevan! Seems that order clause fixed the issue. Look like the output is now correct.

    Thanks Richard - another lesson in not testing properly!

  • bevanward

    SSC Eights!

    Points: 855

    SQL Guy 1 - Tuesday, February 20, 2018 8:39 AM

    There was a great article how to solve Sudoku by Itzik Ben Gun about 12 years ago in SQL Server Magazine.

    I'll have to have a look around at how others have solved this - for this exercise it was attempting without looking at solutions however I am keen to see how others have approached it now.

    Thanks for your comment
    Bevan

  • shaulbel

    Old Hand

    Points: 375

    Seems it works now.

    I would like to understand the query

    select RowNum, [1],[2],[3],[4],[5],[6],[7],[8],[9]
    from
      (select RowNum, ColumnNum, case when substring(@PuzzleIn,CoordinateID,1) != 0 then substring(@PuzzleIn,CoordinateID,1) end Value from #tGrid) as base
    pivot
    (min(Value) for ColumnNum in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) as pt

    what is the meaning of !=0
    Thanks

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

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