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.