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:

CREATE TYPE BoardType AS TABLE (R INT, C INT, V INT)

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.

CREATE FUNCTION CreateBoard() RETURNS @board TABLE(R INT, C INT, V INT) AS

BEGIN

— Insert data

DECLARE @sudoku TABLE (id INT IDENTITY, V INT)

 

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

INSERT INTO @sudoku (V) VALUES

  (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);

 

DECLARE @valueMap TABLE (VS INT, VT INT)

 

INSERT INTO @valueMap (VS, VT) VALUES

(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),

(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(9,9)

 

INSERT INTO @board

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

INNER JOIN @valueMap ON V = VS   

 

RETURN

END

 

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.

 

CREATE FUNCTION GetRow(@board BoardType READONLY, @row INT, @col INT) RETURNS TABLE AS

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

 

CREATE FUNCTION GetColumn(@board BoardType READONLY, @row INT, @col INT) RETURNS TABLE AS

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

 

CREATE FUNCTION GetBlock(@board BoardType READONLY, @row INT, @col INT) RETURNS TABLE AS

RETURN SELECT A.R, A.C, A.V, A.D, A.BR, A.BC

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

BEGIN

INSERT INTO @result

SELECT R, C, V FROM @board

 

DELETE FROM @result

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))

 

RETURN

END

 

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.

 

CREATE FUNCTION GetErrorCount(@board BoardType READONLY) RETURNS INT AS

BEGIN

— 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

DECLARE @distincts TABLE(IND INT, CNT INT)

 

INSERT INTO @distincts

SELECT R*9+C AS I, COUNT(*) AS CNT FROM @board GROUP BY (R*9+C)

 

DELETE FROM @distincts

WHERE CNT <> 1

 

DECLARE @distinctBoard AS TABLE(R INT, C INT, V INT)

 

INSERT INTO @distinctBoard

SELECT R, C, V

FROM @board

WHERE R*9+C IN (SELECT IND FROM @distincts)

 

— Figure out if the board is valid

DECLARE @errorCount INT

 

; WITH VerificationSet(A, B) AS

(

          SELECT COUNT(DISTINCT V), COUNT(V) FROM @distinctBoard GROUP BY R

          UNION ALL

          SELECT COUNT(DISTINCT V), COUNT(V) FROM @distinctBoard GROUP BY C

          UNION ALL

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

)

SELECT @errorCount = SUM(CASE WHEN A = B THEN 0 ELSE 1 END)

FROM VerificationSet

 

RETURN @errorCount

END

 

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

INSERT INTO @board

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

 

— Solve puzzle

SELECT * FROM dbo.Solve(@board)

 

Ok, that was all. Thanks for reading.

Advertisements
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: