## Nov 14, 2009

### 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.