Solving Sudoku using SQL Server 2005 - Step by Step - Part #1

This one is going to be a series. I thought I was going to come up with a single query to solve Sudoku (without choosing the brute force method). When I started creating the tables I needed, I figured out there there are way too many aspects to solving Sudoku logically. I thought it would be a good idea to give a continous update as I go about building the solution.

This post is all about creating the necessary tables and basic procedures which I think we need to build the solution. 

First, I am creating a database called Sudoku which will hold all our objects and the numbers table which I hope we will use frequently.

CREATE DATABASE SUDOKU
GO
USE SUDOKU
GO

/* NUMBERS TABLE USED TO LOAD DEFAULT TABLE DATA*/
CREATE TABLE NUMBERS
(
  NUM INT NOT NULL
)
GO

/* FILL THE NUMBER TABLE */
DECLARE @COUNT INT
SET @COUNT = 0
WHILE (@COUNT <9)
BEGIN
    SET @COUNT = @COUNT + 1
    INSERT INTO NUMBERS SELECT @COUNT
END
GO

We need 2 main tables to start with. One is the SUDOKU_BOARD which will hold the original sudoku problem and will be updated with the confirmed correct value of each cell that we identify in our solve.
The second table is SOLUTION_BOARD, which is like a work table we will play around with to solve the problem. Solution board will hold all possible candidate values for each cell. Both the tables will be prefilled with 81 rows, one row for each cell in the sudoku board. Each row will hold the xy position of the cell and the value of the cell.

/* THE PROBLEM TO BE SOLVED WILL BE PLACED IN THIS BOARD */
CREATE TABLE SUDOKU_BOARD 
(
    XPOS SMALLINT NOT NULL CHECK (XPOS BETWEEN 1 AND 9),
    YPOS SMALLINT NOT NULL CHECK (YPOS BETWEEN 1 AND 9),
    VAL SMALLINT NULL CHECK(VAL BETWEEN 1 AND 9)
)
GO

/* BUILD THE SUDOKU BOARD WITH ALL POSITIONS. THIS IS A ONE TIME OPERATION*/
INSERT INTO SUDOKU_BOARD(XPOS,YPOS)
SELECT X.NUM,Y.NUM FROM NUMBERS X, NUMBERS Y
GO

/* THE SOLUTION WILL BE DERIVED IN THIS BOARD FOR THE GIVEN PROBLEM*/
CREATE TABLE SOLUTION_BOARD 
(
    XPOS SMALLINT NOT NULL CHECK (XPOS BETWEEN 1 AND 9),
    YPOS SMALLINT NOT NULL CHECK (YPOS BETWEEN 1 AND 9),
    VAL VARCHAR(9) DEFAULT '123456789'
)
GO

/* BUILD THE SOLUTION BOARD WITH ALL POSITIONS AND DEFAULT VALUES*/
INSERT INTO SOLUTION_BOARD(XPOS,YPOS)
SELECT X.NUM,Y.NUM FROM NUMBERS X, NUMBERS Y
GO

Though, the two tables are effective for our solve, it is not easily to comprehend the data. So, I am creating 2 procedures that will display the board in the way we are used to seeing it - one for viewing the sudoku board and the other for viewing the solution board. We can call these procedures whenever we might need to view either of the tables, during our solves.

/* CALL THIS PROCEDURE TO VIEW THE SUDOKU BOARD AT ANY TIME*/
CREATE PROC PrintBoard
AS
SET NOCOUNT ON
BEGIN
        SELECT TOP 100 PERCENT 'Y' + CAST(YPOS AS CHAR) AS 'Y/X', 
               ISNULL(CAST([1] AS VARCHAR(1)),'') AS [X1],
               ISNULL(CAST([2] AS VARCHAR(1)),'') AS [X2],
               ISNULL(CAST([3] AS VARCHAR(1)),'') AS [X3],
               ISNULL(CAST([4] AS VARCHAR(1)),'') AS [X4],
               ISNULL(CAST([5] AS VARCHAR(1)),'') AS [X5],
               ISNULL(CAST([6] AS VARCHAR(1)),'') AS [X6],
               ISNULL(CAST([7] AS VARCHAR(1)),'') AS [X7],
               ISNULL(CAST([8] AS VARCHAR(1)),'') AS [X8],
               ISNULL(CAST([9] AS VARCHAR(1)),'') AS [X9]
        FROM   SUDOKU_BOARD
        PIVOT (SUM(VAL) FOR XPOS IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) AS SB
        ORDER BY YPOS
END
GO

/* CALL THIS PROCEDURE TO VIEW THE SOLUTION BOARD AT ANY TIME*/
CREATE PROC PrintSolution
AS
SET NOCOUNT ON
BEGIN 
        SELECT TOP 100 PERCENT 'Y' + CAST(YPOS AS CHAR) AS 'Y/X', 
               [1] AS [X1],
               [2] AS [X2],
               [3] AS [X3],
               [4] AS [X4],
               [5] AS [X5],
               [6] AS [X6],
               [7] AS [X7],
               [8] AS [X8],
               [9] AS [X9]
        FROM   SOLUTION_BOARD
        PIVOT (MIN(VAL) FOR XPOS IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) AS SB
        ORDER BY YPOS
END
GO

I guess, this should setup the environment that we need to start building our solution. Please feel free to use the scripts above if you want to come up with your own solution.

If you plan to write a solution, I suggest you read through this link. They have got a good read on solving sudoku by logic and have a javascript implementation of the same. The solution I plan to write, if not a direct implementation of their logic, will atleast be based on theirs. And I wish to give them the due credit.

And if you do come up with a solution, please post it in the comments section. I would love to see it.

The next part of this series is available here.