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

Implementation of RunSolveAlgorithm4:

This is the last post in this series. The previous algorithm is the last one that tries to solve the puzzle logically. This one will take the latest unsolved sudoku board that we get after running through the first three algorithms and use brute force to solve the puzzle. I am not going to reinvent the wheel here.

This is a SQL Server implementation of "solving sudoku using recursive subquery factoring" written by Anton Scheffer for Oracle 11gR2.

Here is the logic that was used. Using recursive CTEs, start filling the blank cells (one cell at a time) with all possible valid values for the cell, starting from left to right ,top to bottom. Each empty cell will be a root node with subsequent solutions branching under it. Each valid value filled in that cell will be a new solution node in the branch, which will become the root node for the next blank cell. Now, fill the second cell the same way for each of the node and continue.

The branching of a node will terminate when one of the following conditions are met:
1. If any node cannot no longer have a valid value for the next empty cell, we stop branching that node - It can no longer lead us to the valid solution.
2. When all cells in the sudoku board are filled, stop processing that node. The node holds the solution.

Here is the implementation:

ALTER PROC RunSolveAlgorithm4
AS
SET NOCOUNT ON
BEGIN
    WITH SUDOKU_BOARD_AS_STRING AS /*Convert our latest Sudoku Board as a continous string*/
    (
    SELECT CAST((
             SELECT ISNULL(VAL,0) FROM SUDOKU_BOARD ORDER BY YPOS,XPOS FOR XML PATH('')
           ) AS VARCHAR(81)) AS SUDOKU_PROBLEM
    ),
    ALL_SOLNS AS
    ( SELECT SUDOKU_PROBLEM AS SOLN, CHARINDEX('0',SUDOKU_PROBLEM,1) CUR_POSN FROM SUDOKU_BOARD_AS_STRING
      UNION ALL /*Recursive member - Replace the next blank cell with a possible value*/
      SELECT CAST(LEFT(SOLN,CUR_POSN-1) + CAST(A.NUM AS CHAR(1)) + RIGHT(SOLN,81-CUR_POSN) AS VARCHAR(81)), 
             CHARINDEX( '0',SOLN,CUR_POSN+1)  
      FROM ALL_SOLNS,NUMBERS A 
      WHERE CUR_POSN > 0  /*Branching termination condition 2. No more cells to fill. SOLUTION!!! */
        AND A.NUM NOT IN (/*Pick the solution only when the current value is not in any other cell of 
                            the same row, column and 3X3 block. Branching termination condition 1*/
                          SELECT substring(SOLN,(B.NUM-1)*9 + C.NUM,1)  FROM NUMBERS B, NUMBERS C
                          WHERE B.NUM = (CUR_POSN-1)/9+1 
                             OR C.NUM = (CUR_POSN-1)%9 + 1 
                             OR ((B.NUM-1)/3)*3 + (C.NUM-1)/3 = (((CUR_POSN-1)/27)*3 + ((CUR_POSN-1)%9)/3))
    ),
    SUDOKU_SOLUTION AS
    ( SELECT A.NUM AS XPOS, B.NUM AS YPOS, SUBSTRING(SOLN,(B.NUM-1)*9 + A.NUM,1) AS VAL 
      FROM NUMBERS A,NUMBERS B,(SELECT TOP 1 SOLN FROM ALL_SOLNS WHERE CUR_POSN = 0) C
    )
    UPDATE SUD
    SET SUD.VAL = SOL.VAL
    FROM SUDOKU_BOARD SUD, SUDOKU_SOLUTION SOL
    WHERE SUD.XPOS = SOL.XPOS
    AND SUD.YPOS = SOL.YPOS    

    /* Update the solution board too so that its in sync with sudoku board*/
    UPDATE SOL
    SET SOL.VAL = SUD.VAL
    FROM SUDOKU_BOARD SUD, SOLUTION_BOARD SOL
    WHERE SUD.XPOS = SOL.XPOS
      AND SUD.YPOS = SOL.YPOS    
END

This algorithm can be run directly after loading the data in the sudoku board, without running the other three algorithms. However, due to the recursive nature of this algorithm, the number of branches can be exponentially reduced by filling a few extra cells in the sudoku board. So, I am having this as the last algorithm to be used.

That brings this series to an end (atleast for now).

One final note: If you are planning to build more algorithms on this, add them before this one, for obvious reasons - so that you don't work on a solved puzzle :) You can get the source of all the code in this series from here.