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;
          PRINT 'BAD DATA'
          RETURN 0
     END     
 
     /* PROCEDURE TO LOAD THE INPUT DATA INTO SUDOKU AND THE SOLUTION BOARD */
     EXEC LoadInputData @szProblem;
 
     /* 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 
*/
CREATE PROC LoadInputData
(@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.