## Nov 14, 2009

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

Implementation of RunSolveAlgorithm3:

The last algorithm that we implemented was able to solve an easy puzzle. Now, lets take a hard one and see if the solution we have built till now in this series can solve it.

`````` 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'
``````

post-solve sudoku board - before implementing algorithm 3

post-solve solution board - before implementing algorithm 3

We see that the current solve methods cannot handle this puzzle. Lets build the next algorithm.

Implementation of RunSolveAlgorithm3:
The next algorithm is again an implementation from sudoku solver which they call the solve method B.
It is a little complex and I enjoyed implementing this one. You see that any row in the board will belong to three 3X3 block and the row will have 3 cells in each block. Now, check if there are any values in the row occur only in one of the 3 blocks. If it does, it means that for that particular block, the value exists in that row. So, that value can be removed from the other 6 cells in the block. We do the same for the columns.

We can do the check the other way round too, where any block will belong to 3 rows and will have 3 cells in each row. Now, check if there are any values in the block occur only in one of the 3 rows. If it does, it means that for that particular row, the value exists in that block. So, that value can be removed from the other 6 cells in the row. We can do it similarly for columns.

With the algorithm explained, here is the implementation:

``````ALTER PROC RunSolveAlgorithm3
AS
SET NOCOUNT ON
BEGIN
DECLARE @RowCount SMALLINT,
@Counter SMALLINT

SET     @RowCount = 1
SET     @Counter = 1

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

/*For each row, check if any number occur only in a specific block, then the number will be
in that row, remove it from all other rows in that block */
WITH YSOL AS
(
SELECT YPOS,(XPOS-1)/3 + 1 AS XBLK, 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,(XPOS-1)/3 + 1 ,SUBSTRING(VAL,NUM,1)
),
YSOL_DEL AS
(
SELECT D.NUM AS XPOS,C.NUM AS YPOS,A.VAL FROM YSOL A LEFT OUTER JOIN YSOL B ON A.YPOS = B.YPOS
AND A.XBLK <> B.XBLK AND A.VAL= B.VAL
INNER JOIN NUMBERS C ON (A.YPOS -1)/3 =(C.NUM-1)/3
INNER JOIN NUMBERS D ON A.XBLK =(D.NUM-1)/3+1
WHERE B.YPOS IS NULL
AND A.YPOS <> C.NUM
AND A.VAL = @Counter
)
UPDATE SOL SET VAL = REPLACE(SOL.VAL,YDEL.VAL,'')
FROM   SOLUTION_BOARD SOL, YSOL_DEL YDEL
WHERE  SOL.XPOS = YDEL.XPOS
AND SOL.YPOS = YDEL.YPOS
AND LEN(SOL.VAL) > 1;

/*For each column, check if any number occur only in a specific block, then the number will be
in that column, remove it from all other columns in that block */
WITH XSOL AS
(
SELECT XPOS,(YPOS-1)/3 + 1 AS YBLK, 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,(YPOS-1)/3 + 1 ,SUBSTRING(VAL,NUM,1)
),
XSOL_DEL AS
(
SELECT D.NUM AS YPOS,C.NUM AS XPOS,A.VAL FROM XSOL A LEFT OUTER JOIN XSOL B ON A.XPOS = B.XPOS
AND A.YBLK <> B.YBLK AND A.VAL= B.VAL
INNER JOIN NUMBERS C ON (A.XPOS -1)/3 =(C.NUM-1)/3
INNER JOIN NUMBERS D ON A.YBLK =(D.NUM-1)/3+1
WHERE B.XPOS IS NULL
AND A.XPOS <> C.NUM
AND A.VAL = @Counter
)
UPDATE SOL SET VAL = REPLACE(SOL.VAL,XDEL.VAL,'')
FROM   SOLUTION_BOARD SOL, XSOL_DEL XDEL
WHERE  SOL.YPOS = XDEL.YPOS
AND SOL.XPOS = XDEL.XPOS
AND LEN(SOL.VAL) > 1;

/*For each block, check if any number occur only in a specific row, then the number will be
in that block, remove it from all other blocks in that row*/
WITH YBLK AS
(
SELECT ((YPOS-1)/3)*3 + (XPOS-1)/3 + 1 AS BPOS, 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-1)/3)*3 + (XPOS-1)/3,YPOS,SUBSTRING(VAL,NUM,1)
),
YBLK_DEL AS
(
SELECT  A.YPOS,C.NUM AS XPOS ,A.VAL
FROM YBLK A LEFT OUTER JOIN YBLK B
ON      A.BPOS = B.BPOS
AND A.YPOS <> B.YPOS
AND A.VAL= B.VAL
INNER JOIN NUMBERS C ON 1 = 1
WHERE B.YPOS IS NULL
AND A.BPOS = 8
AND (C.NUM-1)/3 + 1 <> A.BPOS  - ((A.YPOS-1)/3)*3
AND A.VAL = @Counter
)
UPDATE SOL SET VAL = REPLACE(SOL.VAL,YDEL.VAL,'')
FROM  SOLUTION_BOARD SOL, YBLK_DEL YDEL
WHERE SOL.XPOS = YDEL.XPOS
AND SOL.YPOS = YDEL.YPOS
AND LEN(SOL.VAL) > 1;

/*For each block, check if any number occur only in a specific column, then the number will be
in that block, remove it from all other blocks in that column*/
WITH XBLK AS
(
SELECT ((XPOS-1)/3)*3 + (YPOS-1)/3 + 1 AS BPOS, 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-1)/3)*3 + (YPOS-1)/3,XPOS,SUBSTRING(VAL,NUM,1)
),
XBLK_DEL AS
(
SELECT A.XPOS, C.NUM AS YPOS ,A.VAL
FROM XBLK A LEFT OUTER JOIN XBLK B
ON     A.BPOS = B.BPOS
AND A.XPOS <> B.XPOS
AND A.VAL= B.VAL
INNER JOIN NUMBERS C ON 1 = 1
WHERE B.XPOS IS NULL AND
A.BPOS = 8
AND (C.NUM-1)/3 + 1 <> A.BPOS  - ((A.XPOS-1)/3)*3
AND A.VAL = @Counter
)
UPDATE SOL SET VAL = REPLACE(SOL.VAL,XDEL.VAL,'')
FROM  SOLUTION_BOARD SOL, XBLK_DEL XDEL
WHERE SOL.YPOS = XDEL.YPOS
AND SOL.XPOS = XDEL.XPOS
AND LEN(SOL.VAL) > 1;

SET @Counter = @Counter + 1
END

/* 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

/* We rerun SolveAlgorithms 1 and 2 to see if there are any more solves possible */

EXEC RunSolveAlgorithm1;
EXEC RunSolveAlgorithm2;
END
END
GO
``````

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

With this implementation, we should be able to solve most medium and some hard puzzles. There are a lot more well known algorithms available to solve the puzzle logically, which should be equally interesting to implement. If you come up with an implementation other than the ones given here, please feel free to post the link or the actual implementation in the comments section. But, I am done with my implementations for now. The next post, our last algorithm, will be a brute force algorithm, which will be a fall back in case our first 3 algorithms are not able to solve the puzzle.