A SQL Sudoko Solver

Introduction

During a long wet May bank holiday weekend I decided to try my hand at a Sudoko puzzle in the Sunday paper.

After all, how hard could it be?

Four frustrating hours later I thought "hang on, this is a set based problem, surely I can use

SQL Server to solve this thing".

Basic Sudoko

Sudoko is usually a 9x9 grid, although any grid that can be regularly divided up is theoretically possible.

For the sake of this article we will assume that we are trying to solve a 9x9 grid.

A Sudoko grid may look something like the following:

As with all the best puzzles the rules are very simple

• Each row must contain the numbers 1 through to 9 only once
• Each column must contain the numbers 1 through to 9 only once
• Each 3x3 cell must contain the numbers 1 through to 9 only once

Looking at our grid this means that in row 9 column 9 we know that its value cannot be

1 because a 1 already exists in that 3x3 cell

Building the initial Sudoko square.

Our first task is to come up a table structure that will hold our Sudoko information.

We can populate this table using simple INSERT statements.

TRUNCATE TABLE dbo.Sudoko
-- Row 1
INSERT INTO dbo.Sudoko (RowId, ColumnId, CellValue) VALUES (1,4,5)
INSERT INTO dbo.Sudoko (RowId, ColumnId, CellValue) VALUES (1,6,8)
...etc

Where we do not yet know the values in the cells we want an entry with a NULL value. Do do this I have a couple of views

and a quick bit of script as follows

IF EXISTS (SELECT * FROM sys.views WHERE Name='Digits')
DROP VIEW dbo.Digits
GO
CREATE VIEW dbo.Digits
AS
SELECT     0 AS value
UNION ALL
SELECT     1 AS value
UNION ALL
SELECT     2 AS value
UNION ALL
SELECT     3 AS value
UNION ALL
SELECT     4 AS value
UNION ALL
SELECT     5 AS value
UNION ALL
SELECT     6 AS value
UNION ALL
SELECT     7 AS value
UNION ALL
SELECT     8 AS value
UNION ALL
SELECT     9 AS value
GO
--------------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='AllValues')
DROP VIEW dbo.AllValues
GO
CREATE VIEW dbo.AllValues
AS
SELECT R.Value AS RowId, C.Value AS ColumnId, V.Value AS CellValue
FROM dbo.Digits AS R,dbo.Digits AS C, dbo.Digits AS V
WHERE R.Value>0 AND C.Value>0 AND V.Value>0
GO
--------------------------------------------------------------------------
-- Insert NULL values into the Sudoko square where row/column coordinates do not yet exist.
INSERT INTO dbo.Sudoko (RowId,ColumnID)
SELECT DT.RowId,DT.ColumnId
FROM dbo.Sudoko AS SD RIGHT JOIN(
SELECT DISTINCT RowId,ColumnId
FROM dbo.AllValues
WHERE RowId>0
AND ColumnId > 0
AND CellValue>0
) AS DT
ON SD.RowId = DT.RowId
AND SD.ColumnId = DT.ColumnID
WHERE SD.RowId IS NULL
GO

Blocked Values Part One

Once we have built our Sudoko square the first step in the solution is to establish which values are blocked from

each individual cell. Remember the rules we outlined earlier.

• Each row must contain the numbers 1 through to 9 only once
• Each column must contain the numbers 1 through to 9 only once
• Each 3x3 cell must contain the numbers 1 through to 9 only once

We have to build a query that will determine these values for us.

To begin with we want to identify all the values that occur in any one row.

SELECT DISTINCT RowId,CellValue
FROM dbo.Sudoko 
WHERE CellValue IS NOT NULL

Now we want to join this back to the empty cells of our Sudoko square as follows

SELECT SD.RowId, SD.ColumnId,SR.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
-- Get the values for the row.
SELECT DISTINCT RowId,CellValue
FROM dbo.Sudoko 
WHERE CellValue IS NOT NULL
) AS SR
ON SD.RowId = SR.RowId
WHERE SD.CellValue IS NULL

We want a similar query for the columns and finally a query that identifies the values in a particular 3x3 cell.

SELECT SD.RowId, SD.ColumnId,CC.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
-- Get the values present in a 3x3 cell.
SELECT DISTINCT 
(RowId-1)/3+1 AS RowCellId,
(ColumnId-1)/3+1 AS ColumnCellId,
CellValue
FROM dbo.Sudoko 
WHERE CellValue IS NOT NULL
) AS CC
ON (SD.ColumnId-1)/3+1  = CC.ColumnCellId
AND (SD.RowId-1)/3+1  = CC.RowCellId
WHERE SD.CellValue IS NULL

We have our 3 queries and we want all of these added together which we can do in a single view as follows:

IF EXISTS (SELECT * FROM sys.views WHERE Name='BlockedValues')
DROP VIEW dbo.BlockedValues
GO
--##SUMMARY Values that cannot be inserted into cells
CREATE VIEW dbo.BlockedValues
AS
SELECT SD.RowId, SD.ColumnId,SR.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
SELECT DISTINCT RowId,CellValue
FROM dbo.Sudoko 
WHERE CellValue IS NOT NULL
) AS SR
ON SD.RowId = SR.RowId
WHERE SD.CellValue IS NULL
UNION
SELECT SD.RowId, SD.ColumnId,SC.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
SELECT DISTINCT ColumnId,CellValue
FROM dbo.Sudoko 
WHERE CellValue IS NOT NULL
) AS SC
ON SD.ColumnId = SC.ColumnId
WHERE SD.CellValue IS NULL
UNION
SELECT SD.RowId, SD.ColumnId,CC.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
SELECT DISTINCT 
(RowId-1)/3+1 AS RowCellId,
(ColumnId-1)/3+1 AS ColumnCellId,
CellValue
FROM dbo.Sudoko 
WHERE CellValue IS NOT NULL
) AS CC
ON (SD.ColumnId-1)/3+1  = CC.ColumnCellId
AND (SD.RowId-1)/3+1  = CC.RowCellId
WHERE SD.CellValue IS NULL
GO

We now have all those cell values that are directly blocked by existing data.

This isn't the whole story but it is a good start

Possible Values Part One

The list of possible values that can be inserted into any one cell must be the values still left to solve less those

identified in our "BlockValues" view.

To get to this we can define two new views as follows:

---------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='AllPossibleValues')
DROP VIEW dbo.AllPossibleValues
GO
CREATE VIEW dbo.AllPossibleValues
AS
SELECT AllVal.RowId,
AllVal.ColumnId ,
AllVal.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN dbo.AllValues AS AllVal
ON SD.RowId = AllVal.RowId
AND SD.ColumnID = AllVal.ColumnID
WHERE SD.CellValue IS NULL
GO
---------------------------------------------------------------------

This first view simply produces a total list of all values for those cells that are currently blank.

---------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='PossibleValues')
DROP VIEW dbo.PossibleValues
GO
CREATE VIEW dbo.PossibleValues
AS
SELECT AllVal.RowId,
AllVal.ColumnId ,
AllVal.CellValue
FROM dbo.AllPossibleValues AS AllVal
LEFT JOIN dbo.BlockedValues AS Block
ON AllVal.RowId = Block.RowId
AND AllVal.ColumnId = Block.ColumnId
AND AllVal.CellValue = Block.CellValue
WHERE Block.RowId IS NULL
GO

This 2nd view excludes those values that are deemed to be blocked.

Our first solving query

What we want to do is to populate any cells in our Sudoko puzzle where there is only one possible value,

that is 8 out of 9 values are blocked.

Of course if we solve a cell (or hopefully cells) this means that our list of possible values will be

reduced for other cells and therefore we want to keep hitting our query until it can solve no more values. This means

we need some code that says

WHILE @@ROWCOUNT >0
BEGIN
... exec dbo.OurSolvingSP
END

Firstly we must identify those cells for which there is only one solution.

SELECT     RowId, ColumnId, MIN(CellValue) AS CellValue
FROM         dbo.PossibleValues
GROUP BY RowId, ColumnId
HAVING COUNT(*)=1

Our stored procedure becomes the following:

------------------------------------------------------------
IF EXISTS(SELECT 1 FROM sys.procedures where name = 'SolveSingleCells')
DROP PROC dbo.SolveSingleCells 
GO
CREATE PROCEDURE dbo.SolveSingleCells
AS
SET NOCOUNT ON
DECLARE @RecordCount1 INT ,
@RecordCount2 INT ,
@TotalCount INT
SET @TotalCount=1
WHILE @TotalCount>0
BEGIN
-- Update the Sudoko square where only a single solution exists
-- for any one cell
UPDATE SD
SET SD.CellValue = DT.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
SELECT     RowId, ColumnId, MIN(CellValue) AS CellValue
FROM         dbo.PossibleValues
GROUP BY RowId, ColumnId
HAVING COUNT(*)=1
) AS DT
ON SD.RowId = DT.RowId
AND SD.ColumnId = DT.ColumnId
SET @TotalCount= @@ROWCOUNT
END
GO

In a simple puzzle this will solve quite a few values however our puzzle is a little more complicated than that

so we must think again.

A 2nd attempt

Look at the first 3x3 cell of our grid again. We know that there are no cells with a single possible solution

so we must turn the problem on its head and look for occurrences where a value can only fit in a single cell.

Consider the number 7. The shaded square show where figure 7 cannot go and as you can see there is only one

possible cell where 7 is not blocked.

Using the same method we can see that in the bottom right hand 3x3 cell there is also only one cell where 7 is not blocked.

Clearly we need a query that can identify these occurrences and that we can incorporate into our solving stored procedure!

Our first step is to build a view that can determine the number of different cell values that can go in any particular

cell.

IF EXISTS (SELECT * FROM sys.views WHERE Name='PossibleValuesByCell')
DROP VIEW dbo.PossibleValuesByCell
GO
CREATE VIEW dbo.PossibleValuesByCell
AS 
SELECT 
(PV.RowId-1)/3+1 AS RowCellId,
(PV.ColumnId-1)/3+1 AS ColumnCellId,
PV.CellValue,
COUNT(*) AS Occurrences
FROM dbo.possiblevalues AS PV
GROUP BY (PV.RowId-1)/3+1 ,
(PV.ColumnId-1)/3+1 ,
PV.CellValue
GO

Our update statement therefore becomes the following

UPDATE SD
SET SD.CellValue = PV.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN dbo.possiblevalues AS PV
ON SD.RowId = PV.RowId
AND SD.ColumnId = PV.ColumnID
INNER JOIN PossibleValuesByCell AS PC
ON PC.RowCellId = (PV.RowId-1)/3+1 
AND PC.ColumnCellId = (PV.ColumnId-1)/3+1
AND PC.CellValue = PV.CellValue

WHERE PC.Occurrences=1

Wrapping this up into a single stored procedure becomes the following

------------------------------------------------------------
IF EXISTS(SELECT 1 FROM sys.procedures where name = 'SolveSingleCells')
DROP PROC dbo.SolveSingleCells 
GO
CREATE PROCEDURE dbo.SolveSingleCells
AS
SET NOCOUNT ON
DECLARE @RecordCount1 INT ,
@RecordCount2 INT ,
@TotalCount INT
SET @TotalCount=1
WHILE @TotalCount>0
BEGIN
-- Update the Sudoko square where only a single solution exists
-- for any one cell
UPDATE SD
SET SD.CellValue = DT.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
SELECT     RowId, ColumnId, MIN(CellValue) AS CellValue
FROM         dbo.PossibleValues 
GROUP BY RowId, ColumnId
HAVING COUNT(*)=1
) AS DT
ON SD.RowId = DT.RowId
AND SD.ColumnId = DT.ColumnId
SET @RecordCount1 = @@ROWCOUNT

UPDATE SD
SET SD.CellValue = PV.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN dbo.PossibleValues AS PV
ON SD.RowId = PV.RowId
AND SD.ColumnId = PV.ColumnID
INNER JOIN PossibleValuesByCell AS PC
ON PC.RowCellId = (PV.RowId-1)/3+1 
AND PC.ColumnCellId = (PV.ColumnId-1)/3+1
AND PC.CellValue = PV.CellValue

WHERE PC.Occurrences=1

SET @RecordCount2 = @@ROWCOUNT
SET @TotalCount = @RecordCount1+@RecordCount2
-- Display the number of solved values.
RAISERROR('Single cells solved = %d',10,1,@TotalCount)
END
RETURN @TotalCount
GO

By itterating through this procedure until it can solve no other cells we can see that it will fill in

quite a few of the gaps in our puzzle.

Solving double values

The cells that are left have multiple possible solutions so we need something that will evaluate these cells.

If we look at the row 3 and 4 for column 6 we can see that they are both limited to the same pair of values, 2 &9.

This means that nothing else in that column can take either of these values. If any other cells did take one of these

values it would mean that both of our cells would have exactly the same value, which is against the rules.

What we need is a query that blocks these values from our list of possible values for other cells.

Our next step is to create a view that identifies those cells that have only two possible solutions.

---------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='TwinValues')
DROP VIEW dbo.TwinValues
GO
CREATE VIEW dbo.TwinValues
AS
SELECT     RowId, ColumnId,MIN(CellValue) AS Value1, MAX(CellValue) AS Value2
FROM         dbo.PossibleValues
GROUP BY RowId, ColumnId
HAVING COUNT(*)=2
GO
---------------------------------------------------------------------

Then we want to identify where a pair of values is shared in the same column.

---------------------------------------------------------------------
SELECT  T1.ColumnId, MIN(T1.RowId) AS RowId1, MAX(T1.RowId) AS RowId2, T1.Value1, T1.Value2
FROM dbo.twinvalues AS T1 INNER JOIN dbo.twinvalues AS T2
ON T1.ColumnId = T2.ColumnId -- Must be in the same column
AND T1.Value1 = T2.Value1 -- Must have an identical 1st value
AND T1.Value2 = T2.Value2 -- Must have an identical 2nd value
WHERE T1.RowId<>T2.RowId -- Must be in a different row.
GROUP BY T1.ColumnId,T1.Value1, T1.Value2
---------------------------------------------------------------------

Finally we must combined this back with our possible values so that we can identify any cells in our column, other

than the ones we have identified that have one or more of these values.

---------------------------------------------------------------------
SELECT PV.RowId , 
PV.ColumnId,
PV.CellValue
FROM dbo.PossibleValues AS PV 
INNER JOIN (
SELECT  T1.ColumnId, MIN(T1.RowId) AS RowId1, MAX(T1.RowId) AS RowId2, T1.Value1, T1.Value2
FROM dbo.twinvalues AS T1 INNER JOIN dbo.twinvalues AS T2
ON T1.ColumnId = T2.ColumnId
AND T1.Value1 = T2.Value1
AND T1.Value2 = T2.Value2
WHERE T1.RowId<>T2.RowId
GROUP BY T1.ColumnId,T1.Value1, T1.Value2
) AS DT
ON PV.ColumnId = DT.ColumnId -- Must be in the same column
AND PV.CellValue IN (DT.Value1, DT.Value2)-- Must have at least one of the values
AND PV.RowId NOT IN (DT.RowId1,DT.RowId2)-- Must not be in the same cells as our paired value cells.
---------------------------------------------------------------------

Blocked Values Part Two

The previous query will form the basis for our 2nd blocked values view. This new view will contain the following:

• Our query identifying values from pairs which occur in column cells other than our paired cells
• A similar query identifying values from pairs which occur in row cells other than our paired cells
• The values from our original BlockedValues view

Putting it all together we can come up with a 2nd stage blocked view

---------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='BlockedValuesStage2')
DROP VIEW dbo.BlockedValuesStage2
GO
--##SUMMARY Values that cannot be inserted into cells
CREATE VIEW dbo.BlockedValuesStage2
AS
-- Identify cell values blocked because they exist in a column pair
SELECT PV.RowId , 
PV.ColumnId,
PV.CellValue
FROM dbo.PossibleValues AS PV 
INNER JOIN (
SELECT  T1.ColumnId, MIN(T1.RowId) AS RowId1, MAX(T1.RowId) AS RowId2, T1.Value1, T1.Value2
FROM dbo.twinvalues AS T1 INNER JOIN dbo.twinvalues AS T2
ON T1.ColumnId = T2.ColumnId
AND T1.Value1 = T2.Value1
AND T1.Value2 = T2.Value2
WHERE T1.RowId<>T2.RowId
GROUP BY T1.ColumnId,T1.Value1, T1.Value2
) AS DT
ON PV.ColumnId = DT.ColumnId
AND PV.CellValue IN (DT.Value1, DT.Value2)
AND PV.RowId NOT IN (DT.RowId1,DT.RowId2)
UNION
-- Identify cell values blocked because they exist in a row pair
SELECT PV.RowId , 
PV.ColumnId,
PV.CellValue
FROM dbo.PossibleValues AS PV 
INNER JOIN (
SELECT  T1.RowId, MIN(T1.ColumnId) AS ColumnId1, MAX(T1.ColumnId) AS ColumnId2, T1.Value1, T1.Value2
FROM dbo.twinvalues AS T1 INNER JOIN dbo.twinvalues AS T2
ON T1.RowId = T2.RowId
AND T1.Value1 = T2.Value1
AND T1.Value2 = T2.Value2
WHERE T1.ColumnId<>T2.ColumnId
GROUP BY T1.RowId,T1.Value1, T1.Value2
) AS DT
ON PV.RowId = DT.RowId
AND PV.CellValue IN (DT.Value1, DT.Value2)
AND PV.ColumnId NOT IN (DT.ColumnId1,DT.ColumnId2)
UNION
-- Identify cells from the original blocked query.
SELECT RowId , ColumnId, CellValue
FROM dbo.BlockedValues
GO

A case to ponder

There is one other case that we could consider. Where a paired value exists in the same 3x3 cell but does not share

a row or column. This would indeed pose a challenge as a query because, where as a column pair or row pair share a common

axis, this instance does not share any easily encoded values.

Let us suppose that row 1, column 1 shares the same pairing as row 3 column 3. Writing a query that would investigate

values not in these two cells would be quite tricky. The ways that the preceding queries work would cause row 1 column 3

and row 3 column 1 to be blocked.

There are two reasons why we don't need to worry about this query

• It would only affect the diagonal 3x3 cells 1,1 & 2,2 & 3,3. That is, you cannot transpose row 3 column 4 with

  column 4 row 3 as these are in 3x3 cells 1,2 and 2,1 respectively

• The other blocked values actually work around the whole query making our cell test irrelevant.

At worst we end up

with an extra couple of itterations in our loop but the solution remains the same.

Possible Values Part Two

Of course, now we have an additional blocked values query we also need a 2nd stage PossibleValues query.

This will be similar to the first version but will be dbo.PossibleValues minus dbo.BlockedValuesStage2

---------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='PossibleValuesStage2')
DROP VIEW dbo.PossibleValuesStage2
GO
CREATE VIEW dbo.PossibleValuesStage2
AS
SELECT AllVal.RowId,
AllVal.ColumnId ,
AllVal.CellValue
FROM dbo.PossibleValues AS AllVal
LEFT JOIN dbo.BlockedValuesStage2 AS Block
ON AllVal.RowId = Block.RowId
AND AllVal.ColumnId = Block.ColumnId
AND AllVal.CellValue = Block.CellValue
WHERE Block.RowId IS NULL
GO
---------------------------------------------------------------------

Now we can revisit our dbo.SolveSingleCells procedure and dbo.PossibleValuesByCell view and replace

references to dbo.PossibleValues with dbo.PossibleValuesStage2

---------------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='PossibleValuesByCell')
DROP VIEW dbo.PossibleValuesByCell
GO
CREATE VIEW dbo.PossibleValuesByCell
AS 
SELECT 
(PV.RowId-1)/3+1 AS RowCellId,
(PV.ColumnId-1)/3+1 AS ColumnCellId,
PV.CellValue,
COUNT(*) AS Occurrences
FROM dbo.PossibleValuesStage2 AS PV
GROUP BY (PV.RowId-1)/3+1 ,
(PV.ColumnId-1)/3+1 ,
PV.CellValue
GO
------------------------------------------------------------
IF EXISTS(SELECT 1 FROM sys.procedures where name = 'SolveSingleCells')
DROP PROC dbo.SolveSingleCells 
GO
CREATE PROCEDURE dbo.SolveSingleCells
AS
SET NOCOUNT ON
DECLARE @RecordCount1 INT ,
@RecordCount2 INT ,
@TotalCount INT
SET @TotalCount=1
WHILE @TotalCount>0
BEGIN
-- Update the Sudoko square where only a single solution exists
-- for any one cell
UPDATE SD
SET SD.CellValue = DT.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN (
SELECT     RowId, ColumnId, MIN(CellValue) AS CellValue
FROM         dbo.PossibleValuesStage2
GROUP BY RowId, ColumnId
HAVING COUNT(*)=1
) AS DT
ON SD.RowId = DT.RowId
AND SD.ColumnId = DT.ColumnId
SET @RecordCount1 = @@ROWCOUNT

UPDATE SD
SET SD.CellValue = PV.CellValue
FROM dbo.Sudoko AS SD
INNER JOIN dbo.PossibleValuesStage2 AS PV
ON SD.RowId = PV.RowId
AND SD.ColumnId = PV.ColumnID
INNER JOIN PossibleValuesByCell AS PC
ON PC.RowCellId = (PV.RowId-1)/3+1 
AND PC.ColumnCellId = (PV.ColumnId-1)/3+1
AND PC.CellValue = PV.CellValue

WHERE PC.Occurrences=1

SET @RecordCount2 = @@ROWCOUNT
SET @TotalCount = @RecordCount1+@RecordCount2
RAISERROR('Single cells solved = %d',10,1,@TotalCount)
-- If any updates occurred then remove them from the possible values list.
IF @TotalCount>0
exec dbo.RemoveSolvedCells
END
RETURN @TotalCount
GO
------------------------------------------------------------

Wrapping it all up

Perhaps the final stage is to write two short views to ensure that the puzzle is truly solved.

The following view should never return any records if the solution is valid. It attempts to find the

following occurrences

• Rows where a single value occurs more than once.
• Columns where a single value occurs more than once.

------------------------------------------------------------
IF EXISTS (SELECT * FROM sys.views WHERE Name='ValidateSolution')
DROP VIEW dbo.ValidateSolution
GO
CREATE VIEW dbo.ValidateSolution
AS
SELECT RowId AS IndexValue,'Row' AS Item,cellvalue
FROM dbo.sudoko
GROUP BY rowid,cellvalue
HAVING count(*)>1
UNION ALL
SELECT ColumnId AS IndexValue,'Column' AS Item,cellvalue
FROM dbo.sudoko
GROUP BY ColumnId,cellvalue
HAVING count(*)>1
GO
------------------------------------------------------------

Concluding thoughts

I have tested this routine on the Sudoko puzzles in the UK's "The Independent" newspaper over the past week

or so and in each case it has produced the correct solution.

I see no reason why this Sudoko solver shouldn't be extended to solve any size of puzzle thought this would almost

certainly move away from the single solving stored procedure.

Of course it is one thing to solve a Sudoko puzzle but the real challenge would be to come up with the necessary

SQL code to generate the solution!