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

Implementation of RunSolveAlgorithm1:

In the previous post of this series, we created the procedure stub for each algorithm. This post will implement RunSolveAlgorithm1.

The first algorithm will do the primary clean up on the solution board. It will implement the basic rules of Sudoku. The rule is that a number cannot appear in a cell if it already appears in any other cell in the same row or column or the block in the sudoku board. It will remove those numbers from the possible cadidate values of each cell in the solution board.

This cannot usually solve the puzzle completely unless the problem is extremely easy. But, this will make sure our other algorithms need not worry about figuring out the obvious.

So, here goes the implementation. Once you understand the row level update, the column and block level update are pretty much the same. I have added comments in place, so it should be fairly easy to understand.

ALTER PROC RunSolveAlgorithm1
AS
SET NOCOUNT ON
BEGIN
   DECLARE @RowCount SMALLINT,
           @Counter  SMALLINT
 
   SET     @RowCount = 1
   SET     @Counter = 1

   /* We will keep running this algorithm till there are no more
      cells left to update in the sudoku board  */
   
   WHILE(@RowCount > 0 AND dbo.VerifySolve() = 0)
   BEGIN
   /* We need to use the counter logic to make sure we don't do 
   mutiple updates on the same value such that it over writes 
   each other */
      SET @Counter = 0;
      WHILE (@Counter <=9) 
      BEGIN  
         /*Remove the number from each cell in solution board if it exists in any of the cells 
           in the same column from the sudoku board */
          WITH SUD_XPOS AS
          (
            SELECT XPOS,VAL,
            ROW_NUMBER() OVER (PARTITION BY XPOS ORDER BY VAL ) AS COUNTER 
            FROM SUDOKU_BOARD 
            WHERE VAL IS NOT NULL
          )
          UPDATE SOL SET VAL = REPLACE(SOL.VAL,SUD.VAL,'')
          FROM   SOLUTION_BOARD SOL, SUD_XPOS SUD
          WHERE  SOL.XPOS = SUD.XPOS
          AND LEN(SOL.VAL) > 1
          AND COUNTER = @Counter;
          
          /*Remove the number from each cell in solution board if it exists in any of the cells 
            in the same row from the sudoku board */
          WITH SUD_YPOS AS
          (
            SELECT YPOS,VAL,
            ROW_NUMBER() OVER (PARTITION BY YPOS ORDER BY VAL ) AS COUNTER  
            FROM SUDOKU_BOARD 
            WHERE VAL IS NOT NULL
          )
          UPDATE SOL SET VAL = REPLACE(SOL.VAL,SUD.VAL,'')
          FROM   SOLUTION_BOARD SOL, SUD_YPOS SUD
          WHERE  SOL.YPOS = SUD.YPOS
          AND LEN(SOL.VAL) > 1
          AND COUNTER = @Counter;

          /*Remove the number from each cell in solution board if it exists in any of the cells 
            in the same 3X3 block from the sudoku board */
          WITH SUD_BLOCK AS
          (
            SELECT ((YPOS-1)/3)*3 + (XPOS-1)/3 AS BPOS,VAL,
                   ROW_NUMBER() OVER (PARTITION BY ((YPOS-1)/3)*3 + (XPOS-1)/3 ORDER BY VAL ) AS COUNTER  
            FROM SUDOKU_BOARD 
            WHERE VAL IS NOT NULL
          )
          UPDATE SOL SET VAL = REPLACE(SOL.VAL,SUD.VAL,'')
          FROM   SOLUTION_BOARD SOL, SUD_BLOCK SUD
          WHERE  ((SOL.YPOS-1)/3)*3 + (SOL.XPOS-1)/3 = SUD.BPOS
          AND LEN(SOL.VAL) > 1
          AND COUNTER = @Counter;
          
          SET @Counter = @Counter  + 1
      END /* WHILE (@Counter <=9) */

      /*If the above updates led to a determining the value of any cell in the solution 
        board (Only one digit exists in the cell), then we update the sudoku_board */
      UPDATE SUD
      SET VAL = SOL.VAL
      FROM SUDOKU_BOARD SUD, SOLUTION_BOARD SOL
      WHERE SUD.XPOS = SOL.XPOS
      AND SUD.YPOS = SOL.YPOS
      AND LEN(SOL.VAL) = 1
      AND SUD.VAL IS NULL

      SET @RowCount = @@ROWCOUNT
   END /* WHILE(@RowCount > 0 AND dbo.VerifySolve() = 0) */
   
END

When I call the proc SolveSudoku, you can see that though the problem is not solved, it does fill a few more cells in the sudoku board and the solution board has a lot less choices in the unsolved cells.

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'

post-solve sudoku board - before implementing Algorithm 1

post-solve sudoku board  - after implementing Agorithm 1

post-solve solution board - before implementing Algorithm 1

post-solve solution board - after implementing Agorithm 1

That ends this post. Lets see if the next algorithm solves this puzzle.