## Nov 12, 2009

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