A Sudoku Solver for Ordinary folk

Question

A Sudoku Solver for Ordinary folk

RevOX11

Old Hand

Points: 308
More actions
February 20, 2019 at 10:44 pm

#379385

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

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

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

reece.watkins 16343 Valued Member Points: 68 More actions · Answer 1

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: 68 More actions · Answer 2

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

roger-562742 SSC Enthusiast Points: 186 More actions · Answer 3

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: 18263 More actions · Answer 4

Jonathan AC Roberts

SSCoach

Points: 18263

February 21, 2019 at 9:23 am

#2022562

Very impressive!

RevOX11 Old Hand Points: 308 More actions · Answer 5

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 SSChampion Points: 10051 More actions · Answer 6

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 Old Hand Points: 308 More actions · Answer 7

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: 18263 More actions · Answer 8

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 Old Hand Points: 308 More actions · Answer 9

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.

ben.gijsen SSC Rookie Points: 27 More actions · Answer 10

Great example of how to write code. Originally triggered by the idea, you really got my attention when you declared to "always aim for simplicity (...) much easier to modify", as this also one of my favorites: when writing code (and teaching others how to do it) I always focus on (human) readable code where, precisely because most code gets changed during its lifetime. In my opinion, you should have something which is functionally correct and understandable first, before you start optimizing.

Thanks for this nice example (and of course I also like the approach of the problem). It clearly shows that more (complexity) isn't always the best.

RevOX11 Old Hand Points: 308 More actions · Answer 11

Hi Ben, thanks for your comment. I often wonder if insecurity prompts folk to over-complicate things, whether that is code or anything else. But it is quite likely that that thought is an over-simplification of a complex situation!

Dan Bragg Old Hand Points: 372 More actions · Answer 12

Thank you, RevOX11.

I've been thinking of wringing a Sudoku Solver for years now, just haven't made time to do it, yet. My personal interest isn't so much "can a computer do it" (duh, it can) but rather "can a computer do it in such a way that it can teach a human how to do it themselves" (which is a factor of Auditability - how can I follow what the computer did to verify its result?)

Of course, for Sudoku, the proof is in the completed puzzle with no errors, but my interest is in having the computer "teach" the human, explaining Why a particular cell has only one remaining answer.

I look forward to using your best final solution as a starting point to my efforts. Maybe your simple and elegant baseline is what I need to build my "more complicated on the inside, but simpler on the outside" product!

RevOX11 Old Hand Points: 308 More actions · Answer 13

Hi Dan, I hope you have a lot of fun playing around with this. I certainly did! And you may find that you can improve on my logic, for which I make no claims of perfection - I suspect that I started guessing too soon, having implemented the easier bits of logic.