## Nov 10, 2009

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

In the first part of this series, we created the base objects needed to work on our solution. Now, there are two parts to building the solution:

• The core algorithms that will solve the puzzle for us
• The surrounding objects that will facilitate the solve and execute the core algorithms
The core algorithms are the crux of this whole exercise. Each of these algorithm will ideally take the unsolved sudoku board and try to fill as many cells as possible using the logic implemented in the specific alogorithm.

We will be creating the procedure stubs for the core algorithms (right now I assumed we will have 4 of them) which will be implemented later.  All my future posts in these series will be about implementing each of the algorithm stubs given below.

``````/* YET TO IMPLEMENT */
CREATE PROC RunSolveAlgorithm1
AS
BEGIN
PRINT 'SOLVE ALGORITHM 1 NOT IMPLEMENTED'
RETURN 0
END
GO

/* YET TO IMPLEMENT */
CREATE PROC RunSolveAlgorithm2
AS
BEGIN
PRINT 'SOLVE ALGORITHM 2 NOT IMPLEMENTED'
RETURN 0
END
GO

/* YET TO IMPLEMENT */
CREATE PROC RunSolveAlgorithm3
AS
BEGIN
PRINT 'SOLVE ALGORITHM 3 NOT IMPLEMENTED'
RETURN 0
END
GO

/* YET TO IMPLEMENT */
CREATE PROC RunSolveAlgorithm4
AS
BEGIN
PRINT 'SOLVE ALGORITHM 4 NOT IMPLEMENTED'
RETURN 0
END
GO
``````

Here is the main procedure that will be called to solve the sudoku puzzle. It prints the sudoku board immediately after loading the puzzle (pre-solve) and again after running all the algorithms (post-solve).

``````/* This proc is the main proc that will accept the problem as an input and do the following:
Verify that the input is valid
Load the problem into the sudoku and solution board
Call the algorithms to solve the problem

Sample Inputs:
EXEC SolveSudoku
'030,001,000,,006,000,050,,500,000,983,,080,006,302,,000,050,000,,903,800,060,,714,000,009,,020,000,800,,000,400,030'
EXEC SolveSudoku
'790,000,300,,000,006,900,,800,030,076,,000,005,002,,005,418,700,,400,700,000,,610,090,008,,002,300,000,,009,000,054'
*/
CREATE PROC SolveSudoku
(@in_szProblem varchar(120))
AS
SET NOCOUNT ON
BEGIN
declare @szProblem   varchar(81)
set     @szProblem = replace(@in_szProblem,',','')

/* CHECK IF THE DATA IS VALID */
IF(PATINDEX('%[^0-9]%', @szProblem) > 0)
BEGIN
UPDATE SUDOKU_BOARD SET VAL = NULL;
RETURN 0
END

/* PROCEDURE TO LOAD THE INPUT DATA INTO SUDOKU AND THE SOLUTION BOARD */

/* RUN SOLVE ALGORITHM 1 */
EXEC RunSolveAlgorithm1
IF(dbo.VerifySolve() = 1) /*SOLVED*/
BEGIN
EXEC PrintBoard
PRINT 'SOLVED'
RETURN 0
END

/* RUN SOLVE ALGORITHM 2 */
EXEC RunSolveAlgorithm2
IF(dbo.VerifySolve() = 1) /*SOLVED*/
BEGIN
EXEC PrintBoard
PRINT 'SOLVED'
RETURN 0
END

/* RUN SOLVE ALGORITHM 3 */
EXEC RunSolveAlgorithm3
IF(dbo.VerifySolve() = 1) /*SOLVED*/
BEGIN
EXEC PrintBoard
PRINT 'SOLVED'
RETURN 0
END

/* RUN SOLVE ALGORITHM 4 */
EXEC RunSolveAlgorithm4
IF(dbo.VerifySolve() = 1) /*SOLVED*/
BEGIN
EXEC PrintBoard
PRINT 'SOLVED'
RETURN 0
END

EXEC PrintBoard /*UNSOLVED*/
PRINT 'UNSOLVED'
RETURN 0
END
GO

``````

The main procedure accepts the input problem as a string. It verifies to make sure the input string contains only numeric data and loads the data into the solution and sudoku board using the following procedure:

``````/* This procedure will place the problem in the sudoku board and
the starting solution used for processing in the solution board.
Input data is a contiguous string filling cells from left to right, top to bottom.
Blank cells will have 0
*/
(@in_szData varchar(81))
AS
SET NOCOUNT ON
BEGIN
UPDATE SUDOKU_BOARD
SET VAL = CASE WHEN substring(@in_szData,(YPOS-1)*9 + XPOS,1) = '0'
THEN NULL
ELSE substring(@in_szData,(YPOS-1)*9 + XPOS,1) END

UPDATE SOLUTION_BOARD
SET VAL = CASE WHEN substring(@in_szData,(YPOS-1)*9 + XPOS,1) = '0'
THEN '123456789'
ELSE substring(@in_szData,(YPOS-1)*9 + XPOS,1) END

EXEC PrintBoard
END
GO
``````

You will see that the main procedure calls a function VerifySolve() after running each algorithm. This will check for the following in the sudoku board:
• the sum of value of cells across each row (summing up values grouping by YPOS) = 45
• the sum of value of cells across each column (summing up values grouping by XPOS) = 45
• the sum of value of cells across each 3X3 block(summing up values grouping by (YPOS-1)/3)*3 + (XPOS-1)/3) = 45
• There are nine unique values filling the board (An over kill to make sure any scenario that escapes the above 3 checks is caught here). For example, filling the board with all cells as 5 will pass the first 3 checks
Here is the implementation of the verification function:

``````/* This function can be called anytime to verify if the sudoku board has a complete solution */
CREATE FUNCTION dbo.VerifySolve()
RETURNS BIT
AS
BEGIN RETURN(
SELECT CASE WHEN COUNT(DISTINCT SUM_VAL) = 1
AND MAX(SUM_VAL)=45
AND (SELECT COUNT(DISTINCT VAL) FROM SUDOKU_BOARD) = 9
THEN 1 ELSE 0 END
FROM
(
SELECT SUM(VAL) AS SUM_VAL FROM SUDOKU_BOARD GROUP BY ((YPOS-1)/3)*3 + (XPOS-1)/3
UNION ALL
SELECT SUM(VAL) FROM SUDOKU_BOARD GROUP BY YPOS
UNION ALL
SELECT SUM(VAL) FROM SUDOKU_BOARD GROUP BY XPOS
) AS GROUP_TOTAL)
END
GO
``````

Now, we have the basic solution in place. As you can see, we are no closer to solving the puzzle than we were when we started this series. We are just making sure that when we implement an algorithm, we will concentrate on just the core algorithm and nothing else. Since none of the algorithms are implemented, when we call the procedure SolveSudoku, it will just print the sudoku board without solving it. As we start implementing each algorithm, SolveSudoku will start filling more and more cells in the board. Right now, the pre-solve (before running the algorithms) and post-solve (after running the algorithms) sudoku board is the same. Here is an example:

``````EXEC SolveSudoku
'790,000,300,,000,006,900,,800,030,076,,000,005,002,,005,418,700,,400,700,000,,610,090,008,,002,300,000,,009,000,054'
``````

pre-solve sudoku board:

post-solve sudoku board:

post solve - solution board (EXEC PrintSolution)

All that is left to do now is implementing the core algorithms. I will be giving the the pre-solve and post solve after implementing each core algorithms. The algorithms will start knocking off the invalid numbers from each cell in the solution board. We have to keep building better algorithms till each cell in the solution board is left with only one number. We have then solved the problem. Long way to go, huh?

We will start with building the first algorithm in the next post.