A Sudoku Solver for Ordinary folk

  • RevOX11

    SSC Veteran

    Points: 270

    Comments posted to this topic are about the item A Sudoku Solver for Ordinary folk

  • reece.watkins 16343

    Valued Member

    Points: 63

    Nice article! One problem, though.  It's generally considered a bad idea to use a named constraint on a temporary table. If there's an error before the temp table is dropped, the constraint can get stuck in TempDB and cause subsequent runs to fail with the error "There is already an object named 'PK0ByCell' in the database." Worse, the object does not show up in sys.objects, and cannot be dropped.  Just remove "CONSTRAINT PK0ByCell" and leave it as "PRIMARY KEY CLUSTERED...", and it will work properly.

    CREATE TABLE [#ByCell]([tiGuessNo]  TINYINT
            ,[tiRow]   TINYINT
            ,[tiCol]   TINYINT
            ,[tiBlk]   TINYINT
            ,[tiVal]   TINYINT
            ,[RowSetString] VARCHAR(9)
            ,[ColSetString] VARCHAR(9)
            ,[BlkSetString] VARCHAR(9)
            ,[Possibles]  VARCHAR(9)
            -- Get rid of these two words ====> ,CONSTRAINT [PK0ByCell]
            ,PRIMARY KEY CLUSTERED([tiGuessNo],[tiRow],[tiCol]))

    Further, I'd suggest using VARCHAR or CHAR instead of NVARCHAR, since all of the characters you'll be dealing with are single-byte.  Also, Try using the inline-IF (IIF()) function instead of a whole CASE block when there's only a single choice.  It makes the code shorter and easier to read. Like so:

    UpdateSetStrings:
    UPDATE [#ByCell]
    SET [RowSetString] = CAST([Val01] AS VARCHAR(1)) + CAST([Val02] AS VARCHAR(1)) + CAST([Val03] AS VARCHAR(1)) + CAST([Val04] AS VARCHAR(1)) + CAST([Val05] AS VARCHAR(1)) + CAST([Val06] AS VARCHAR(1)) + CAST([Val07] AS VARCHAR(1)) + CAST([Val08] AS VARCHAR(1)) + CAST([Val09] AS VARCHAR(1))
    FROM [#ByCell] AS [BC]
    INNER JOIN(SELECT
         [tiRow]
         ,MAX(IIF([tiCol] = 1,[tiVal],0)) AS [Val01]
         ,MAX(IIF([tiCol] = 2,[tiVal],0)) AS [Val02]
         ,MAX(IIF([tiCol] = 3,[tiVal],0)) AS [Val03]
         ,MAX(IIF([tiCol] = 4,[tiVal],0)) AS [Val04]
         ,MAX(IIF([tiCol] = 5,[tiVal],0)) AS [Val05]
         ,MAX(IIF([tiCol] = 6,[tiVal],0)) AS [Val06]
         ,MAX(IIF([tiCol] = 7,[tiVal],0)) AS [Val07]
         ,MAX(IIF([tiCol] = 8,[tiVal],0)) AS [Val08]
         ,MAX(IIF([tiCol] = 9,[tiVal],0)) AS [Val09]
        FROM [#ByCell]
        WHERE [tiGuessNo] = @tiGuess
        GROUP BY
         [tiRow]) AS [T] ON [BC].[tiRow] = [T].[tiRow]
    WHERE
     [tiGuessNo] = @tiGuess

    and similar for the Column/Row UPDATE below it.

    Doing these things shaved about 30 milliseconds off of the average runtime for me.

  • reece.watkins 16343

    Valued Member

    Points: 63

    Here's a little change to format the output a little closer to how the puzzles are usually presented, too:

    --ThatsAllForNowFolks
    ;WITH [xPuzzle] AS
    (SELECT TOP 9
     SUBSTRING(@strPuzzle,([tiRow] - 1) * 9 + 1,9) AS [Puzzle]
    ,MAX([RowSetString]) AS [Solution]
    FROM [#ByCell]
    WHERE [tiGuessNo] = @tiGuess
    GROUP BY [tiRow]
    ORDER BY [tiRow]
    )
    SELECT
    REPLACE( '| '+SUBSTRING([Puzzle],1,1) +
    ' | '+SUBSTRING([Puzzle],2,1) +
    ' | '+SUBSTRING([Puzzle],3,1) +
    ' | '+SUBSTRING([Puzzle],4,1) +
    ' | '+SUBSTRING([Puzzle],5,1) +
    ' | '+SUBSTRING([Puzzle],6,1) +
    ' | '+SUBSTRING([Puzzle],7,1) +
    ' | '+SUBSTRING([Puzzle],8,1) +
    ' | '+SUBSTRING([Puzzle],9,1) + ' |','0','_') as [Puzzle],
    '| '+SUBSTRING([Solution],1,1) +
    ' | '+SUBSTRING([Solution],2,1) +
    ' | '+SUBSTRING([Solution],3,1) +
    ' | '+SUBSTRING([Solution],4,1) +
    ' | '+SUBSTRING([Solution],5,1) +
    ' | '+SUBSTRING([Solution],6,1) +
    ' | '+SUBSTRING([Solution],7,1) +
    ' | '+SUBSTRING([Solution],8,1) +
    ' | '+SUBSTRING([Solution],9,1) + ' |' as [Solution]
    FROM [xPuzzle]

  • roger-562742

    SSC Enthusiast

    Points: 184

    Nice work!
    But what I'd really like to know: How do compilers know when they've provided sufficient numbers in the cells, for it to be possible to complete the Soduku? Over to you Pete, when you've done with the DIY...

  • Jonathan AC Roberts

    SSCoach

    Points: 16882

    Very impressive!

  • RevOX11

    SSC Veteran

    Points: 270

    reece.watkins 16343 - Thursday, February 21, 2019 6:44 AM

    Here's a little change to format the output a little closer to how the puzzles are usually presented, too:

    --ThatsAllForNowFolks
    ;WITH [xPuzzle] AS
    (SELECT TOP 9
     SUBSTRING(@strPuzzle,([tiRow] - 1) * 9 + 1,9) AS [Puzzle]
    ,MAX([RowSetString]) AS [Solution]
    FROM [#ByCell]
    WHERE [tiGuessNo] = @tiGuess
    GROUP BY [tiRow]
    ORDER BY [tiRow]
    )
    SELECT
    REPLACE( '| '+SUBSTRING([Puzzle],1,1) +
    ' | '+SUBSTRING([Puzzle],2,1) +
    ' | '+SUBSTRING([Puzzle],3,1) +
    ' | '+SUBSTRING([Puzzle],4,1) +
    ' | '+SUBSTRING([Puzzle],5,1) +
    ' | '+SUBSTRING([Puzzle],6,1) +
    ' | '+SUBSTRING([Puzzle],7,1) +
    ' | '+SUBSTRING([Puzzle],8,1) +
    ' | '+SUBSTRING([Puzzle],9,1) + ' |','0','_') as [Puzzle],
    '| '+SUBSTRING([Solution],1,1) +
    ' | '+SUBSTRING([Solution],2,1) +
    ' | '+SUBSTRING([Solution],3,1) +
    ' | '+SUBSTRING([Solution],4,1) +
    ' | '+SUBSTRING([Solution],5,1) +
    ' | '+SUBSTRING([Solution],6,1) +
    ' | '+SUBSTRING([Solution],7,1) +
    ' | '+SUBSTRING([Solution],8,1) +
    ' | '+SUBSTRING([Solution],9,1) + ' |' as [Solution]
    FROM [xPuzzle]

    Thanks very much for your input.  I have not been a big user of temp tables, and have only used them for very simple situations.  But this was an unusual project, trying to make the least impact on databases where it would be run, and so have used a temp table where I would normally have used a permanent table.  I have never suffered from having created a phantom unremovable Constraint in TempDB, and now thanks to your warning, that happy situation is likely to continue! 
    When it comes to Char/nChar/VarChar/nVarChar, I have pretty much standardised on nVarChar.  This decision is in no small part due to having had to convert a database using Char/VarChar to using the Unicode equivalents - there was a possibility of the database going to South East Asia.  Much of it was simply Find-And-Replace, but a significant chunk of it wasn't.  I don't remember any of the fine detail, but the memory of the pain is still strong, and the weeks invested in that project will never become available again.  I accept that always using nVarChar is overkill, but my databases have never needed those tiny improvements that would make this a bad choice, and I have seen many databases where far worse standards have been implemented.
    Likewise with IIf and Case.  I cannot count how many times things have initially been binary choices, only to subsequently become much more complex, so I have tended to use Case always.  Although that potential 30ms to be saved is appealing...

  • Michael Meierruth

    SSCrazy Eights

    Points: 9991

    Very neat. Very fast.
    Found an old SQL Server 2008 installation where it runs just fine.
    I do the New York Time Sudoku almost every day. It is slightly different in that you have to deal with four additional blocks.
    Thus I will try and adabt this code to solve this variant...

  • RevOX11

    SSC Veteran

    Points: 270

    Michael Meierruth - Monday, February 25, 2019 12:18 PM

    Very neat. Very fast.
    Found an old SQL Server 2008 installation where it runs just fine.
    I do the New York Time Sudoku almost every day. It is slightly different in that you have to deal with four additional blocks.
    Thus I will try and adabt this code to solve this variant...

    Glad you liked it, and that it has inspired you to play around a bit.  I would be delighted to hear of your progress with NYTimes version.  I am not surprised that it is OK with SQL2008, and would likewise not be surprised to find that it would work on SQL 2005 - not that I intend finding out.

  • Jonathan AC Roberts

    SSCoach

    Points: 16882

    It's a really impressive script. I think it's worth changing the table definition in of #ByCell in script Soduku_PJR to remove the name of the primary key and then republish the article. This has caused an error on my machine and reece watkins. It just needs to be changed to:
       CREATE TABLE #ByCell(tiGuessNo         TinyInt
                            , tiRow           TinyInt
                            , tiCol           TinyInt
                            , tiBlk           TinyInt
                            , tiVal           TinyInt
                            , RowSetString    nVarChar(9)
                            , ColSetString    nVarChar(9)
                            , BlkSetString    nVarChar(9)
                            , Possibles       nVarChar(9)
                            , Primary Key CLUSTERED (tiGuessNo, tiRow, tiCol))

    It would be a shame for people to miss such a good solver just because they got a compile error.

  • RevOX11

    SSC Veteran

    Points: 270

    Jonathan AC Roberts - Friday, March 1, 2019 6:20 AM

    It's a really impressive script. I think it's worth changing the table definition in of #ByCell in script Soduku_PJR to remove the name of the primary key and then republish the article. This has caused an error on my machine and reece watkins. It just needs to be changed to:
       CREATE TABLE #ByCell(tiGuessNo         TinyInt
                            , tiRow           TinyInt
                            , tiCol           TinyInt
                            , tiBlk           TinyInt
                            , tiVal           TinyInt
                            , RowSetString    nVarChar(9)
                            , ColSetString    nVarChar(9)
                            , BlkSetString    nVarChar(9)
                            , Possibles       nVarChar(9)
                            , Primary Key CLUSTERED (tiGuessNo, tiRow, tiCol))

    It would be a shame for people to miss such a good solver just because they got a compile error.

    Thanks for your input, in addition to that from Reece Watkins.  I am learning (slowly) what can and cannot be done with published articles, but have made the change, and resubmitted.

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

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