Home > Uncategorized > A Sudoku solver in T-SQL

A Sudoku solver in T-SQL

Writing a Sudoku solver has become one of my favorite exercise puzzles. It is a small task but still complex enough to be challenging when tested in a new domain or context. So far I have written Sudoku solvers in C++, C#, F# and Powershell. This time my eyes fell upon T-SQL, which is the SQL dialect used by SQL Server. Why? (Do I need a reason? Smile) Well, at least, it seemed like a fun way to gain some more experience in that area.  When thinking back, I must admit that it was more on the terrible, frustrating side of the scale than anything else. Still very interesting, though. On the top of my head, some of the things that buggered me:

    I do not say that T-SQL sucks (well, maybe a little bit… Smile) but these are things that we have become accustomed to and expect in other contexts and other, more normal, programming languages. There are probably good reasons for every bump on the road.
    Anyway, as I said, it was still interesting so lets have a look at the solution. (Note: I used SQL Server 2012 but it might be possible to run the code in earlier versions.)
    I started out by writing code for creating the Sudoku board. I felt it was natural to represent the data using a table having to following definition:


Here is the function that generates such a table. Unfortunately, due to the restrictions of function return types I have to repeat the definition of BoardType in the function definition.



— Insert data



— ref: http://www.dctech.com/sudoku/samples/


  (0),(0),(9), (6),(0),(7), (4),(3),(1),

  (8),(0),(0), (0),(5),(3), (0),(0),(9),

  (0),(6),(0), (2),(0),(0), (5),(0),(0),                                                                    


  (0),(0),(8), (9),(0),(0), (0),(0),(6),

  (0),(0),(2), (0),(4),(0), (7),(0),(5),

  (0),(0),(0), (0),(0),(1), (0),(0),(0),                                                                    


  (0),(0),(0), (5),(9),(4), (3),(0),(2),

  (0),(2),(7), (0),(3),(0), (0),(1),(0),

  (4),(0),(0), (1),(0),(2), (6),(5),(0);









SELECT (ID1)/9 AS R, (ID1)%9 AS C, VT AS V FROM @sudoku

INNER JOIN @valueMap ON V = VS   





As you may have noticed, I use a temporary table and create the final one from a join, in order to avoid writing too much.


Extracting rows, columns and blocks are naturally written using select statements.



RETURN SELECT A.R, A.C, A.V, A.D FROM (SELECT R, C, V, dbo.GetCellDimension(@board, R,C) AS D FROM @board) AS A

WHERE A.R = @row AND A.C <> @col AND A.D = 1



RETURN SELECT A.R, A.C, A.V, A.D FROM (SELECT R, C, V, dbo.GetCellDimension(@board,R,C) AS D FROM @board) AS A

WHERE A.C = @col AND A.R <> @row AND A.D = 1




FROM (SELECT R, C, V, dbo.GetCellDimension(@board,R,C) AS D, R/3 AS BR, C/3 AS BC FROM @board) AS A

WHERE A.BR = @row/3 AND A.BC = @col/3 AND NOT (A.C = @col AND A.R = @row) AND A.D = 1


Due to the the fact that execution order is different from the statements order, I use an inner select statement, which complicates matter slightly. This article on stackoverflow suggests this work around.


The next thing was to add constraint propagation. Instead of propagating constraints for one cell at the time, I found a way that was more in the flavor of set theory and thus simpler to express in T-SQL:


CREATE FUNCTION PropagateConstraints(@board BoardType READONLY) RETURNS @result TABLE(R INT, C INT, V INT) AS



SELECT R, C, V FROM @board



WHERE dbo.GetCellDimension(@board, R, C) > 1 AND V IN (

          SELECT V FROM dbo.GetRow(@board, R, C) UNION

          SELECT V FROM dbo.GetColumn(@board, R, C) UNION

          SELECT V FROM dbo.GetBlock(@board, R, C))





The downside of this method is that it may not propagate constraints entirely, leaving cells having one value left that is still illegal. Detecting illegal boards like this is done by the GetErrorCount function which, along with the solver method, was the hardest to write.




— Are all cells there?

DECLARE @cellCount INT

SELECT @cellCount = COUNT(DISTINCT R*9+C) FROM @board

IF @cellCount <> 81

          RETURN 1000


— Create a board where ambiguous cells are removed



INSERT INTO @distincts



DELETE FROM @distincts





INSERT INTO @distinctBoard


FROM @board



— Figure out if the board is valid

DECLARE @errorCount INT


; WITH VerificationSet(A, B) AS



          UNION ALL


          UNION ALL

          SELECT COUNT(DISTINCT V), COUNT(V) FROM @distinctBoard GROUP BY R/3*3+C/3



FROM VerificationSet


RETURN @errorCount



The idea is to compare the distinct values to the total value count for each row, column and block. If the number of distinct values are less, we have an error.


Finally, we got the solver which is just to large to fit in here. Feel free to have a look in the final code at bitucket.


Having all the pieces in place we can now solve a puzzle using:


— Create board

DECLARE @board BoardType


SELECT R, C, V FROM dbo.CreateBoard();


— Solve puzzle

SELECT * FROM dbo.Solve(@board)


Ok, that was all. Thanks for reading.

Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: