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

Implementation of RunSolveAlgorithm2:

We implemented RunSolveAlgorithm1 in previous post of this series . The next algorithm is the implementation of Solve Method A from sudoku solver.

In this algorithm, we check all the cells (having mutiple values) in each row and see if a particular value occurs only once in that row. Then update that as the solution for the cell having that value. We do the similar check for column and the 3X3 block.

This can solve the easy to medium puzzles. Here goes the implementation.

ALTER PROC RunSolveAlgorithm2
AS
SET NOCOUNT ON
BEGIN
    DECLARE @RowCount int,
        @UpdateRowCount int

    SET     @RowCount = 1
    SET    @UpdateRowCount = 0

    WHILE(@RowCount > 0 AND dbo.VerifySolve() = 0)
    BEGIN
        SET @RowCount = 0;

        /* Take all the cells, having mutiple values, in each row and see if a particular value occurs only 
           once in that row. Then update that as the solution for the cell */
        WITH XSOL AS
        (
        SELECT XPOS,SUBSTRING(VAL,NUM,1) AS VAL FROM SOLUTION_BOARD A, NUMBERS B
                       WHERE B.NUM <=LEN(A.VAL)
                       AND LEN(VAL) > 1
        GROUP BY XPOS,SUBSTRING(VAL,NUM,1) HAVING COUNT(*) = 1
        )
        UPDATE SOL 
        SET VAL = XSOL.VAL
        FROM SOLUTION_BOARD SOL, XSOL
        WHERE 
              SOL.XPOS = XSOL.XPOS
          AND LEN(SOL.VAL) > 1
          AND CHARINDEX(XSOL.VAL,SOL.VAL) > 0;

        SET @UpdateRowCount = @@ROWCOUNT;
        SET @RowCount = @RowCount + @UpdateRowCount;
        IF(@UpdateRowCount > 0) /* Need to rerun algorithm 1 for clean up if any cell was updated */
            EXEC RunSolveAlgorithm1; 


        /* Take all the cells, having mutiple values, in each column and see if a particular value occurs only 
           once in that column. Then update that as the solution for the cell */
        WITH YSOL AS
        (
        SELECT YPOS,SUBSTRING(VAL,NUM,1) AS VAL FROM SOLUTION_BOARD A, NUMBERS B
                       WHERE B.NUM <=LEN(A.VAL)
                       AND LEN(VAL) > 1
        GROUP BY YPOS,SUBSTRING(VAL,NUM,1) HAVING COUNT(*) = 1
        )
        UPDATE SOL 
        SET VAL = YSOL.VAL
        FROM SOLUTION_BOARD SOL, YSOL
        WHERE 
              SOL.YPOS = YSOL.YPOS
          AND LEN(SOL.VAL) > 1
          AND CHARINDEX(YSOL.VAL,SOL.VAL) > 0;

        SET @UpdateRowCount = @@ROWCOUNT;
        SET @RowCount = @RowCount + @UpdateRowCount;
        IF(@UpdateRowCount > 0) /* Need to rerun algorithm 1 for clean up if any cell was updated */
            EXEC RunSolveAlgorithm1; 


        /* Take all the cells, having mutiple values, in each 3X3 block and see if a particular value occurs only 
           once in that block. Then update that as the solution for the cell */
        WITH BSOL AS
        (
        SELECT ((YPOS-1)/3)*3 + (XPOS-1)/3 AS BPOS,SUBSTRING(VAL,NUM,1) AS VAL FROM SOLUTION_BOARD A, NUMBERS B
                       WHERE B.NUM <=LEN(A.VAL)
                       AND LEN(VAL) > 1
        GROUP BY ((YPOS-1)/3)*3 + (XPOS-1)/3,SUBSTRING(VAL,NUM,1) HAVING COUNT(*) = 1
        )
        UPDATE SOL 
        SET VAL = BSOL.VAL
        FROM SOLUTION_BOARD SOL, BSOL
        WHERE 
              ((SOL.YPOS-1)/3)*3 + (SOL.XPOS-1)/3 = BSOL.BPOS
          AND LEN(SOL.VAL) > 1
          AND CHARINDEX(BSOL.VAL,SOL.VAL) > 0;

        SET @UpdateRowCount = @@ROWCOUNT;
        SET @RowCount = @RowCount + @UpdateRowCount;
        IF(@UpdateRowCount > 0) /* Need to rerun algorithm 1 for clean up if any cell was updated */
            EXEC RunSolveAlgorithm1; 

    END
END
GO

When I call the proc SolveSudoku now, you can see that the problem is solved and when solved, the solution board and sudoku board are in sync.

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 2

post-solve sudoku board - after implementing Algorithm 2 (Solved)

post-solve solution board - before implementing Algorithm 2

post-solve solution board - after implementing Algorithm 2 (Same as the sudoku board)

For the next algorithm will take up a harder puzzle and see how well we fare.