Tuesday, January 25, 2011

Sudoku - SQL solution

Sudoku is a logic puzzle many people have heard of and probably solved a few of too. The most common version of Sudoku consists of a 3x3 squares grid where each square have 9 cells for a total of 81 cells. Each cell has a domain of the integers 1 through to 9. The constraints are well-known, but I'll repeat them for the sake of completeness:
  • Each of the 9 cells of a square must be different from the other cells in that square
  • Each of the 9 cells of a row must be different from the other cells in that row
  • Each of the 9 cells of a column must be different from the other cells in that column
The problem
A given puzzle consists of a partial solution with exactly one complete solution. Let's say we have the following partial solution:
745
25846
71632
152
9432
395
39258
96473
683

Modeling the problem and finding a solution
What we want to do now is to have the DBMS find the complete solution given the partial solution and the constraints. Again I'm using the free version of Oracle, the XE edition. First we model the variable domains by setting up a view:

CREATE OR REPLACE VIEW V_SUDOKU_CELLS AS
SELECT
    CELLS.CELL
FROM
    (SELECT 1 CELL FROM DUAL UNION ALL
    SELECT 2 CELL FROM DUAL UNION ALL
    SELECT 3 CELL FROM DUAL UNION ALL
    SELECT 4 CELL FROM DUAL UNION ALL
    SELECT 5 CELL FROM DUAL UNION ALL
    SELECT 6 CELL FROM DUAL UNION ALL
    SELECT 7 CELL FROM DUAL UNION ALL
    SELECT 8 CELL FROM DUAL UNION ALL
    SELECT 9 CELL FROM DUAL) CELLS;

Next we build the model of the problem as a SQL query (in Oracle-dialect). This includes the partial solution stated above as well as the given constraints. Together these form a declaration of what we want. The SQL query:

WITH SUDOKU_SOLUTION AS
    (SELECT
        *
    FROM
        (SELECT
            C1.CELL C1_1,
            C2.CELL C2_1,
            C3.CELL C3_1,
            C4.CELL C4_1,
            C5.CELL C5_1,
            C6.CELL C6_1,
            C7.CELL C7_1,
            C8.CELL C8_1,
            C9.CELL C9_1,
            C10.CELL C1_2,
            C11.CELL C2_2,
            C12.CELL C3_2,
            C13.CELL C4_2,
            C14.CELL C5_2,
            C15.CELL C6_2,
            C16.CELL C7_2,
            C17.CELL C8_2,
            C18.CELL C9_2,
            C19.CELL C1_3,
            C20.CELL C2_3,
            C21.CELL C3_3,
            C22.CELL C4_3,
            C23.CELL C5_3,
            C24.CELL C6_3,
            C25.CELL C7_3,
            C26.CELL C8_3,
            C27.CELL C9_3,
            C28.CELL C1_4,
            C29.CELL C2_4,
            C30.CELL C3_4,
            C31.CELL C4_4,
            C32.CELL C5_4,
            C33.CELL C6_4,
            C34.CELL C7_4,
            C35.CELL C8_4,
            C36.CELL C9_4,
            C37.CELL C1_5,
            C38.CELL C2_5,
            C39.CELL C3_5,
            C40.CELL C4_5,
            C41.CELL C5_5,
            C42.CELL C6_5,
            C43.CELL C7_5,
            C44.CELL C8_5,
            C45.CELL C9_5,
            C46.CELL C1_6,
            C47.CELL C2_6,
            C48.CELL C3_6,
            C49.CELL C4_6,
            C50.CELL C5_6,
            C51.CELL C6_6,
            C52.CELL C7_6,
            C53.CELL C8_6,
            C54.CELL C9_6,
            C55.CELL C1_7,
            C56.CELL C2_7,
            C57.CELL C3_7,
            C58.CELL C4_7,
            C59.CELL C5_7,
            C60.CELL C6_7,
            C61.CELL C7_7,
            C62.CELL C8_7,
            C63.CELL C9_7,
            C64.CELL C1_8,
            C65.CELL C2_8,
            C66.CELL C3_8,
            C67.CELL C4_8,
            C68.CELL C5_8,
            C69.CELL C6_8,
            C70.CELL C7_8,
            C71.CELL C8_8,
            C72.CELL C9_8,
            C73.CELL C1_9,
            C74.CELL C2_9,
            C75.CELL C3_9,
            C76.CELL C4_9,
            C77.CELL C5_9,
            C78.CELL C6_9,
            C79.CELL C7_9,
            C80.CELL C8_9,
            C81.CELL C9_9
        FROM
            V_SUDOKU_CELLS C1,
            V_SUDOKU_CELLS C2,
            V_SUDOKU_CELLS C3,
            V_SUDOKU_CELLS C4,
            V_SUDOKU_CELLS C5,
            V_SUDOKU_CELLS C6,
            V_SUDOKU_CELLS C7,
            V_SUDOKU_CELLS C8,
            V_SUDOKU_CELLS C9,
            V_SUDOKU_CELLS C10,
            V_SUDOKU_CELLS C11,
            V_SUDOKU_CELLS C12,
            V_SUDOKU_CELLS C13,
            V_SUDOKU_CELLS C14,
            V_SUDOKU_CELLS C15,
            V_SUDOKU_CELLS C16,
            V_SUDOKU_CELLS C17,
            V_SUDOKU_CELLS C18,
            V_SUDOKU_CELLS C19,
            V_SUDOKU_CELLS C20,
            V_SUDOKU_CELLS C21,
            V_SUDOKU_CELLS C22,
            V_SUDOKU_CELLS C23,
            V_SUDOKU_CELLS C24,
            V_SUDOKU_CELLS C25,
            V_SUDOKU_CELLS C26,
            V_SUDOKU_CELLS C27,
            V_SUDOKU_CELLS C28,
            V_SUDOKU_CELLS C29,
            V_SUDOKU_CELLS C30,
            V_SUDOKU_CELLS C31,
            V_SUDOKU_CELLS C32,
            V_SUDOKU_CELLS C33,
            V_SUDOKU_CELLS C34,
            V_SUDOKU_CELLS C35,
            V_SUDOKU_CELLS C36,
            V_SUDOKU_CELLS C37,
            V_SUDOKU_CELLS C38,
            V_SUDOKU_CELLS C39,
            V_SUDOKU_CELLS C40,
            V_SUDOKU_CELLS C41,
            V_SUDOKU_CELLS C42,
            V_SUDOKU_CELLS C43,
            V_SUDOKU_CELLS C44,
            V_SUDOKU_CELLS C45,
            V_SUDOKU_CELLS C46,
            V_SUDOKU_CELLS C47,
            V_SUDOKU_CELLS C48,
            V_SUDOKU_CELLS C49,
            V_SUDOKU_CELLS C50,
            V_SUDOKU_CELLS C51,
            V_SUDOKU_CELLS C52,
            V_SUDOKU_CELLS C53,
            V_SUDOKU_CELLS C54,
            V_SUDOKU_CELLS C55,
            V_SUDOKU_CELLS C56,
            V_SUDOKU_CELLS C57,
            V_SUDOKU_CELLS C58,
            V_SUDOKU_CELLS C59,
            V_SUDOKU_CELLS C60,
            V_SUDOKU_CELLS C61,
            V_SUDOKU_CELLS C62,
            V_SUDOKU_CELLS C63,
            V_SUDOKU_CELLS C64,
            V_SUDOKU_CELLS C65,
            V_SUDOKU_CELLS C66,
            V_SUDOKU_CELLS C67,
            V_SUDOKU_CELLS C68,
            V_SUDOKU_CELLS C69,
            V_SUDOKU_CELLS C70,
            V_SUDOKU_CELLS C71,
            V_SUDOKU_CELLS C72,
            V_SUDOKU_CELLS C73,
            V_SUDOKU_CELLS C74,
            V_SUDOKU_CELLS C75,
            V_SUDOKU_CELLS C76,
            V_SUDOKU_CELLS C77,
            V_SUDOKU_CELLS C78,
            V_SUDOKU_CELLS C79,
            V_SUDOKU_CELLS C80,
            V_SUDOKU_CELLS C81
        WHERE
            C5.CELL = 7 AND
            C8.CELL = 4 AND
            C9.CELL = 5 AND
            C11.CELL = 2 AND
            C12.CELL = 5 AND
            C14.CELL = 8 AND
            C15.CELL = 4 AND
            C16.CELL = 6 AND
            C20.CELL = 7 AND
            C21.CELL = 1 AND
            C23.CELL = 6 AND
            C24.CELL = 3 AND
            C25.CELL = 2 AND
            C29.CELL = 1 AND
            C32.CELL = 5 AND
            C33.CELL = 2 AND
            C38.CELL = 9 AND
            C39.CELL = 4 AND
            C43.CELL = 3 AND
            C44.CELL = 2 AND
            C49.CELL = 3 AND
            C50.CELL = 9 AND
            C53.CELL = 5 AND
            C57.CELL = 3 AND
            C58.CELL = 9 AND
            C59.CELL = 2 AND
            C61.CELL = 5 AND
            C62.CELL = 8 AND
            C66.CELL = 9 AND
            C67.CELL = 6 AND
            C68.CELL = 4 AND
            C70.CELL = 7 AND
            C71.CELL = 3 AND
            C73.CELL = 6 AND
            C74.CELL = 8 AND
            C77.CELL = 3) U
    WHERE
        -- Rows
        (U.C1_1 NOT IN (U.C1_2,U.C1_3,U.C1_4,U.C1_5,U.C1_6,U.C1_7,U.C1_8,U.C1_9) AND
        U.C1_2 NOT IN (U.C1_3,U.C1_4,U.C1_5,U.C1_6,U.C1_7,U.C1_8,U.C1_9) AND
        U.C1_3 NOT IN (U.C1_4,U.C1_5,U.C1_6,U.C1_7,U.C1_8,U.C1_9) AND
        U.C1_4 NOT IN (U.C1_5,U.C1_6,U.C1_7,U.C1_8,U.C1_9) AND
        U.C1_5 NOT IN (U.C1_6,U.C1_7,U.C1_8,U.C1_9) AND
        U.C1_6 NOT IN (U.C1_7,U.C1_8,U.C1_9) AND
        U.C1_7 NOT IN (U.C1_8,U.C1_9) AND
        U.C1_8 NOT IN (U.C1_9)) AND
        (U.C2_1 NOT IN (U.C2_2,U.C2_3,U.C2_4,U.C2_5,U.C2_6,U.C2_7,U.C2_8,U.C2_9) AND
        U.C2_2 NOT IN (U.C2_3,U.C2_4,U.C2_5,U.C2_6,U.C2_7,U.C2_8,U.C2_9) AND
        U.C2_3 NOT IN (U.C2_4,U.C2_5,U.C2_6,U.C2_7,U.C2_8,U.C2_9) AND
        U.C2_4 NOT IN (U.C2_5,U.C2_6,U.C2_7,U.C2_8,U.C2_9) AND
        U.C2_5 NOT IN (U.C2_6,U.C2_7,U.C2_8,U.C2_9) AND
        U.C2_6 NOT IN (U.C2_7,U.C2_8,U.C2_9) AND
        U.C2_7 NOT IN (U.C2_8,U.C2_9) AND
        U.C2_8 NOT IN (U.C2_9)) AND
        (U.C3_1 NOT IN (U.C3_2,U.C3_3,U.C3_4,U.C3_5,U.C3_6,U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_2 NOT IN (U.C3_3,U.C3_4,U.C3_5,U.C3_6,U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_3 NOT IN (U.C3_4,U.C3_5,U.C3_6,U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_4 NOT IN (U.C3_5,U.C3_6,U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_5 NOT IN (U.C3_6,U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_6 NOT IN (U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_7 NOT IN (U.C3_8,U.C3_9) AND
        U.C3_8 NOT IN (U.C3_9)) AND
        (U.C4_1 NOT IN (U.C4_2,U.C4_3,U.C4_4,U.C4_5,U.C4_6,U.C4_7,U.C4_8,U.C4_9) AND
        U.C4_2 NOT IN (U.C4_3,U.C4_4,U.C4_5,U.C4_6,U.C4_7,U.C4_8,U.C4_9) AND
        U.C4_3 NOT IN (U.C4_4,U.C4_5,U.C4_6,U.C4_7,U.C4_8,U.C4_9) AND
        U.C4_4 NOT IN (U.C4_5,U.C4_6,U.C4_7,U.C4_8,U.C4_9) AND
        U.C4_5 NOT IN (U.C4_6,U.C4_7,U.C4_8,U.C4_9) AND
        U.C4_6 NOT IN (U.C4_7,U.C4_8,U.C4_9) AND
        U.C4_7 NOT IN (U.C4_8,U.C4_9) AND
        U.C4_8 NOT IN (U.C4_9)) AND
        (U.C5_1 NOT IN (U.C5_2,U.C5_3,U.C5_4,U.C5_5,U.C5_6,U.C5_7,U.C5_8,U.C5_9) AND
        U.C5_2 NOT IN (U.C5_3,U.C5_4,U.C5_5,U.C5_6,U.C5_7,U.C5_8,U.C5_9) AND
        U.C5_3 NOT IN (U.C5_4,U.C5_5,U.C5_6,U.C5_7,U.C5_8,U.C5_9) AND
        U.C5_4 NOT IN (U.C5_5,U.C5_6,U.C5_7,U.C5_8,U.C5_9) AND
        U.C5_5 NOT IN (U.C5_6,U.C5_7,U.C5_8,U.C5_9) AND
        U.C5_6 NOT IN (U.C5_7,U.C5_8,U.C5_9) AND
        U.C5_7 NOT IN (U.C5_8,U.C5_9) AND
        U.C5_8 NOT IN (U.C5_9)) AND
        (U.C6_1 NOT IN (U.C6_2,U.C6_3,U.C6_4,U.C6_5,U.C6_6,U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_2 NOT IN (U.C6_3,U.C6_4,U.C6_5,U.C6_6,U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_3 NOT IN (U.C6_4,U.C6_5,U.C6_6,U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_4 NOT IN (U.C6_5,U.C6_6,U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_5 NOT IN (U.C6_6,U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_6 NOT IN (U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_7 NOT IN (U.C6_8,U.C6_9) AND
        U.C6_8 NOT IN (U.C6_9)) AND
        (U.C7_1 NOT IN (U.C7_2,U.C7_3,U.C7_4,U.C7_5,U.C7_6,U.C7_7,U.C7_8,U.C7_9) AND
        U.C7_2 NOT IN (U.C7_3,U.C7_4,U.C7_5,U.C7_6,U.C7_7,U.C7_8,U.C7_9) AND
        U.C7_3 NOT IN (U.C7_4,U.C7_5,U.C7_6,U.C7_7,U.C7_8,U.C7_9) AND
        U.C7_4 NOT IN (U.C7_5,U.C7_6,U.C7_7,U.C7_8,U.C7_9) AND
        U.C7_5 NOT IN (U.C7_6,U.C7_7,U.C7_8,U.C7_9) AND
        U.C7_6 NOT IN (U.C7_7,U.C7_8,U.C7_9) AND
        U.C7_7 NOT IN (U.C7_8,U.C7_9) AND
        U.C7_8 NOT IN (U.C7_9)) AND
        (U.C8_1 NOT IN (U.C8_2,U.C8_3,U.C8_4,U.C8_5,U.C8_6,U.C8_7,U.C8_8,U.C8_9) AND
        U.C8_2 NOT IN (U.C8_3,U.C8_4,U.C8_5,U.C8_6,U.C8_7,U.C8_8,U.C8_9) AND
        U.C8_3 NOT IN (U.C8_4,U.C8_5,U.C8_6,U.C8_7,U.C8_8,U.C8_9) AND
        U.C8_4 NOT IN (U.C8_5,U.C8_6,U.C8_7,U.C8_8,U.C8_9) AND
        U.C8_5 NOT IN (U.C8_6,U.C8_7,U.C8_8,U.C8_9) AND
        U.C8_6 NOT IN (U.C8_7,U.C8_8,U.C8_9) AND
        U.C8_7 NOT IN (U.C8_8,U.C8_9) AND
        U.C8_8 NOT IN (U.C8_9)) AND
        (U.C9_1 NOT IN (U.C9_2,U.C9_3,U.C9_4,U.C9_5,U.C9_6,U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_2 NOT IN (U.C9_3,U.C9_4,U.C9_5,U.C9_6,U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_3 NOT IN (U.C9_4,U.C9_5,U.C9_6,U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_4 NOT IN (U.C9_5,U.C9_6,U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_5 NOT IN (U.C9_6,U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_6 NOT IN (U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_7 NOT IN (U.C9_8,U.C9_9) AND
        U.C9_8 NOT IN (U.C9_9)) AND
        -- Columns
        (U.C1_1 NOT IN (U.C2_1,U.C3_1,U.C4_1,U.C5_1,U.C6_1,U.C7_1,U.C8_1,U.C9_1) AND
        U.C2_1 NOT IN (U.C3_1,U.C4_1,U.C5_1,U.C6_1,U.C7_1,U.C8_1,U.C9_1) AND
        U.C3_1 NOT IN (U.C4_1,U.C5_1,U.C6_1,U.C7_1,U.C8_1,U.C9_1) AND
        U.C4_1 NOT IN (U.C5_1,U.C6_1,U.C7_1,U.C8_1,U.C9_1) AND
        U.C5_1 NOT IN (U.C6_1,U.C7_1,U.C8_1,U.C9_1) AND
        U.C6_1 NOT IN (U.C7_1,U.C8_1,U.C9_1) AND
        U.C7_1 NOT IN (U.C8_1,U.C9_1) AND
        U.C8_1 NOT IN (U.C9_1)) AND
        (U.C1_2 NOT IN (U.C2_2,U.C3_2,U.C4_2,U.C5_2,U.C6_2,U.C7_2,U.C8_2,U.C9_2) AND
        U.C2_2 NOT IN (U.C3_2,U.C4_2,U.C5_2,U.C6_2,U.C7_2,U.C8_2,U.C9_2) AND
        U.C3_2 NOT IN (U.C4_2,U.C5_2,U.C6_2,U.C7_2,U.C8_2,U.C9_2) AND
        U.C4_2 NOT IN (U.C5_2,U.C6_2,U.C7_2,U.C8_2,U.C9_2) AND
        U.C5_2 NOT IN (U.C6_2,U.C7_2,U.C8_2,U.C9_2) AND
        U.C6_2 NOT IN (U.C7_2,U.C8_2,U.C9_2) AND
        U.C7_2 NOT IN (U.C8_2,U.C9_2) AND
        U.C8_2 NOT IN (U.C9_2)) AND
        (U.C1_3 NOT IN (U.C2_3,U.C3_3,U.C4_3,U.C5_3,U.C6_3,U.C7_3,U.C8_3,U.C9_3) AND
        U.C2_3 NOT IN (U.C3_3,U.C4_3,U.C5_3,U.C6_3,U.C7_3,U.C8_3,U.C9_3) AND
        U.C3_3 NOT IN (U.C4_3,U.C5_3,U.C6_3,U.C7_3,U.C8_3,U.C9_3) AND
        U.C4_3 NOT IN (U.C5_3,U.C6_3,U.C7_3,U.C8_3,U.C9_3) AND
        U.C5_3 NOT IN (U.C6_3,U.C7_3,U.C8_3,U.C9_3) AND
        U.C6_3 NOT IN (U.C7_3,U.C8_3,U.C9_3) AND
        U.C7_3 NOT IN (U.C8_3,U.C9_3) AND
        U.C8_3 NOT IN (U.C9_3)) AND
        (U.C1_4 NOT IN (U.C2_4,U.C3_4,U.C4_4,U.C5_4,U.C6_4,U.C7_4,U.C8_4,U.C9_4) AND
        U.C2_4 NOT IN (U.C3_4,U.C4_4,U.C5_4,U.C6_4,U.C7_4,U.C8_4,U.C9_4) AND
        U.C3_4 NOT IN (U.C4_4,U.C5_4,U.C6_4,U.C7_4,U.C8_4,U.C9_4) AND
        U.C4_4 NOT IN (U.C5_4,U.C6_4,U.C7_4,U.C8_4,U.C9_4) AND
        U.C5_4 NOT IN (U.C6_4,U.C7_4,U.C8_4,U.C9_4) AND
        U.C6_4 NOT IN (U.C7_4,U.C8_4,U.C9_4) AND
        U.C7_4 NOT IN (U.C8_4,U.C9_4) AND
        U.C8_4 NOT IN (U.C9_4)) AND
        (U.C1_5 NOT IN (U.C2_5,U.C3_5,U.C4_5,U.C5_5,U.C6_5,U.C7_5,U.C8_5,U.C9_5) AND
        U.C2_5 NOT IN (U.C3_5,U.C4_5,U.C5_5,U.C6_5,U.C7_5,U.C8_5,U.C9_5) AND
        U.C3_5 NOT IN (U.C4_5,U.C5_5,U.C6_5,U.C7_5,U.C8_5,U.C9_5) AND
        U.C4_5 NOT IN (U.C5_5,U.C6_5,U.C7_5,U.C8_5,U.C9_5) AND
        U.C5_5 NOT IN (U.C6_5,U.C7_5,U.C8_5,U.C9_5) AND
        U.C6_5 NOT IN (U.C7_5,U.C8_5,U.C9_5) AND
        U.C7_5 NOT IN (U.C8_5,U.C9_5) AND
        U.C8_5 NOT IN (U.C9_5)) AND
        (U.C1_6 NOT IN (U.C2_6,U.C3_6,U.C4_6,U.C5_6,U.C6_6,U.C7_6,U.C8_6,U.C9_6) AND
        U.C2_6 NOT IN (U.C3_6,U.C4_6,U.C5_6,U.C6_6,U.C7_6,U.C8_6,U.C9_6) AND
        U.C3_6 NOT IN (U.C4_6,U.C5_6,U.C6_6,U.C7_6,U.C8_6,U.C9_6) AND
        U.C4_6 NOT IN (U.C5_6,U.C6_6,U.C7_6,U.C8_6,U.C9_6) AND
        U.C5_6 NOT IN (U.C6_6,U.C7_6,U.C8_6,U.C9_6) AND
        U.C6_6 NOT IN (U.C7_6,U.C8_6,U.C9_6) AND
        U.C7_6 NOT IN (U.C8_6,U.C9_6) AND
        U.C8_6 NOT IN (U.C9_6)) AND
        (U.C1_7 NOT IN (U.C2_7,U.C3_7,U.C4_7,U.C5_7,U.C6_7,U.C7_7,U.C8_7,U.C9_7) AND
        U.C2_7 NOT IN (U.C3_7,U.C4_7,U.C5_7,U.C6_7,U.C7_7,U.C8_7,U.C9_7) AND
        U.C3_7 NOT IN (U.C4_7,U.C5_7,U.C6_7,U.C7_7,U.C8_7,U.C9_7) AND
        U.C4_7 NOT IN (U.C5_7,U.C6_7,U.C7_7,U.C8_7,U.C9_7) AND
        U.C5_7 NOT IN (U.C6_7,U.C7_7,U.C8_7,U.C9_7) AND
        U.C6_7 NOT IN (U.C7_7,U.C8_7,U.C9_7) AND
        U.C7_7 NOT IN (U.C8_7,U.C9_7) AND
        U.C8_7 NOT IN (U.C9_7)) AND
        (U.C1_8 NOT IN (U.C2_8,U.C3_8,U.C4_8,U.C5_8,U.C6_8,U.C7_8,U.C8_8,U.C9_8) AND
        U.C2_8 NOT IN (U.C3_8,U.C4_8,U.C5_8,U.C6_8,U.C7_8,U.C8_8,U.C9_8) AND
        U.C3_8 NOT IN (U.C4_8,U.C5_8,U.C6_8,U.C7_8,U.C8_8,U.C9_8) AND
        U.C4_8 NOT IN (U.C5_8,U.C6_8,U.C7_8,U.C8_8,U.C9_8) AND
        U.C5_8 NOT IN (U.C6_8,U.C7_8,U.C8_8,U.C9_8) AND
        U.C6_8 NOT IN (U.C7_8,U.C8_8,U.C9_8) AND
        U.C7_8 NOT IN (U.C8_8,U.C9_8) AND
        U.C8_8 NOT IN (U.C9_8)) AND
        (U.C1_9 NOT IN (U.C2_9,U.C3_9,U.C4_9,U.C5_9,U.C6_9,U.C7_9,U.C8_9,U.C9_9) AND
        U.C2_9 NOT IN (U.C3_9,U.C4_9,U.C5_9,U.C6_9,U.C7_9,U.C8_9,U.C9_9) AND
        U.C3_9 NOT IN (U.C4_9,U.C5_9,U.C6_9,U.C7_9,U.C8_9,U.C9_9) AND
        U.C4_9 NOT IN (U.C5_9,U.C6_9,U.C7_9,U.C8_9,U.C9_9) AND
        U.C5_9 NOT IN (U.C6_9,U.C7_9,U.C8_9,U.C9_9) AND
        U.C6_9 NOT IN (U.C7_9,U.C8_9,U.C9_9) AND
        U.C7_9 NOT IN (U.C8_9,U.C9_9) AND
        U.C8_9 NOT IN (U.C9_9)) AND
        -- Squares (upper row of squares)
        (U.C1_1 NOT IN (U.C1_2,U.C1_3,U.C2_1,U.C2_2,U.C2_3,U.C3_1,U.C3_2,U.C3_3) AND
        U.C1_2 NOT IN (U.C1_3,U.C2_1,U.C2_2,U.C2_3,U.C3_1,U.C3_2,U.C3_3) AND
        U.C1_3 NOT IN (U.C2_1,U.C2_2,U.C2_3,U.C3_1,U.C3_2,U.C3_3) AND
        U.C2_1 NOT IN (U.C2_2,U.C2_3,U.C3_1,U.C3_2,U.C3_3) AND
        U.C2_2 NOT IN (U.C2_3,U.C3_1,U.C3_2,U.C3_3) AND
        U.C2_3 NOT IN (U.C3_1,U.C3_2,U.C3_3) AND
        U.C3_1 NOT IN (U.C3_2,U.C3_3) AND
        U.C3_2 NOT IN (U.C3_3)) AND
        (U.C1_4 NOT IN (U.C1_5,U.C1_6,U.C2_4,U.C2_5,U.C2_6,U.C3_4,U.C3_5,U.C3_6) AND
        U.C1_5 NOT IN (U.C1_6,U.C2_4,U.C2_5,U.C2_6,U.C3_4,U.C3_5,U.C3_6) AND
        U.C1_6 NOT IN (U.C2_4,U.C2_5,U.C2_6,U.C3_4,U.C3_5,U.C3_6) AND
        U.C2_4 NOT IN (U.C2_5,U.C2_6,U.C3_4,U.C3_5,U.C3_6) AND
        U.C2_5 NOT IN (U.C2_6,U.C3_4,U.C3_5,U.C3_6) AND
        U.C2_6 NOT IN (U.C3_4,U.C3_5,U.C3_6) AND
        U.C3_4 NOT IN (U.C3_5,U.C3_6) AND
        U.C3_5 NOT IN (U.C3_6)) AND
        (U.C1_7 NOT IN (U.C1_8,U.C1_9,U.C2_7,U.C2_8,U.C2_9,U.C3_7,U.C3_8,U.C3_9) AND
        U.C1_8 NOT IN (U.C1_9,U.C2_7,U.C2_8,U.C2_9,U.C3_7,U.C3_8,U.C3_9) AND
        U.C1_9 NOT IN (U.C2_7,U.C2_8,U.C2_9,U.C3_7,U.C3_8,U.C3_9) AND
        U.C2_7 NOT IN (U.C2_8,U.C2_9,U.C3_7,U.C3_8,U.C3_9) AND
        U.C2_8 NOT IN (U.C2_9,U.C3_7,U.C3_8,U.C3_9) AND
        U.C2_9 NOT IN (U.C3_7,U.C3_8,U.C3_9) AND
        U.C3_7 NOT IN (U.C3_8,U.C3_9) AND
        U.C3_8 NOT IN (U.C3_9)) AND
        -- Squares (middle row of squares)
        (U.C4_1 NOT IN (U.C4_2,U.C4_3,U.C5_1,U.C5_2,U.C5_3,U.C6_1,U.C6_2,U.C6_3) AND
        U.C4_2 NOT IN (U.C4_3,U.C5_1,U.C5_2,U.C5_3,U.C6_1,U.C6_2,U.C6_3) AND
        U.C4_3 NOT IN (U.C5_1,U.C5_2,U.C5_3,U.C6_1,U.C6_2,U.C6_3) AND
        U.C5_1 NOT IN (U.C5_2,U.C5_3,U.C6_1,U.C6_2,U.C6_3) AND
        U.C5_2 NOT IN (U.C5_3,U.C6_1,U.C6_2,U.C6_3) AND
        U.C5_3 NOT IN (U.C6_1,U.C6_2,U.C6_3) AND
        U.C6_1 NOT IN (U.C6_2,U.C6_3) AND
        U.C6_2 NOT IN (U.C6_3)) AND
        (U.C4_4 NOT IN (U.C4_5,U.C4_6,U.C5_4,U.C5_5,U.C5_6,U.C6_4,U.C6_5,U.C6_6) AND
        U.C4_5 NOT IN (U.C4_6,U.C5_4,U.C5_5,U.C5_6,U.C6_4,U.C6_5,U.C6_6) AND
        U.C4_6 NOT IN (U.C5_4,U.C5_5,U.C5_6,U.C6_4,U.C6_5,U.C6_6) AND
        U.C5_4 NOT IN (U.C5_5,U.C5_6,U.C6_4,U.C6_5,U.C6_6) AND
        U.C5_5 NOT IN (U.C5_6,U.C6_4,U.C6_5,U.C6_6) AND
        U.C5_6 NOT IN (U.C6_4,U.C6_5,U.C6_6) AND
        U.C6_4 NOT IN (U.C6_5,U.C6_6) AND
        U.C6_5 NOT IN (U.C6_6)) AND
        (U.C4_7 NOT IN (U.C4_8,U.C4_9,U.C5_7,U.C5_8,U.C5_9,U.C6_7,U.C6_8,U.C6_9) AND
        U.C4_8 NOT IN (U.C4_9,U.C5_7,U.C5_8,U.C5_9,U.C6_7,U.C6_8,U.C6_9) AND
        U.C4_9 NOT IN (U.C5_7,U.C5_8,U.C5_9,U.C6_7,U.C6_8,U.C6_9) AND
        U.C5_7 NOT IN (U.C5_8,U.C5_9,U.C6_7,U.C6_8,U.C6_9) AND
        U.C5_8 NOT IN (U.C5_9,U.C6_7,U.C6_8,U.C6_9) AND
        U.C5_9 NOT IN (U.C6_7,U.C6_8,U.C6_9) AND
        U.C6_7 NOT IN (U.C6_8,U.C6_9) AND
        U.C6_8 NOT IN (U.C6_9)) AND
        -- Squares (bottom row of squares)
        (U.C7_1 NOT IN (U.C7_2,U.C7_3,U.C8_1,U.C8_2,U.C8_3,U.C9_1,U.C9_2,U.C9_3) AND
        U.C7_2 NOT IN (U.C7_3,U.C8_1,U.C8_2,U.C8_3,U.C9_1,U.C9_2,U.C9_3) AND
        U.C7_3 NOT IN (U.C8_1,U.C8_2,U.C8_3,U.C9_1,U.C9_2,U.C9_3) AND
        U.C8_1 NOT IN (U.C8_2,U.C8_3,U.C9_1,U.C9_2,U.C9_3) AND
        U.C8_2 NOT IN (U.C8_3,U.C9_1,U.C9_2,U.C9_3) AND
        U.C8_3 NOT IN (U.C9_1,U.C9_2,U.C9_3) AND
        U.C9_1 NOT IN (U.C9_2,U.C9_3) AND
        U.C9_2 NOT IN (U.C9_3)) AND
        (U.C7_4 NOT IN (U.C7_5,U.C7_6,U.C8_4,U.C8_5,U.C8_6,U.C9_4,U.C9_5,U.C9_6) AND
        U.C7_5 NOT IN (U.C7_6,U.C8_4,U.C8_5,U.C8_6,U.C9_4,U.C9_5,U.C9_6) AND
        U.C7_6 NOT IN (U.C8_4,U.C8_5,U.C8_6,U.C9_4,U.C9_5,U.C9_6) AND
        U.C8_4 NOT IN (U.C8_5,U.C8_6,U.C9_4,U.C9_5,U.C9_6) AND
        U.C8_5 NOT IN (U.C8_6,U.C9_4,U.C9_5,U.C9_6) AND
        U.C8_6 NOT IN (U.C9_4,U.C9_5,U.C9_6) AND
        U.C9_4 NOT IN (U.C9_5,U.C9_6) AND
        U.C9_5 NOT IN (U.C9_6)) AND
        (U.C7_7 NOT IN (U.C7_8,U.C7_9,U.C8_7,U.C8_8,U.C8_9,U.C9_7,U.C9_8,U.C9_9) AND
        U.C7_8 NOT IN (U.C7_9,U.C8_7,U.C8_8,U.C8_9,U.C9_7,U.C9_8,U.C9_9) AND
        U.C7_9 NOT IN (U.C8_7,U.C8_8,U.C8_9,U.C9_7,U.C9_8,U.C9_9) AND
        U.C8_7 NOT IN (U.C8_8,U.C8_9,U.C9_7,U.C9_8,U.C9_9) AND
        U.C8_8 NOT IN (U.C8_9,U.C9_7,U.C9_8,U.C9_9) AND
        U.C8_9 NOT IN (U.C9_7,U.C9_8,U.C9_9) AND
        U.C9_7 NOT IN (U.C9_8,U.C9_9) AND
        U.C9_8 NOT IN (U.C9_9)))
SELECT
    C1_1 A,
    C2_1 B ,
    C3_1 C,
    C4_1 D,
    C5_1 E,
    C6_1 F,
    C7_1 G,
    C8_1 H,
    C9_1 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_2 A,
    C2_2 B,
    C3_2 C,
    C4_2 D,
    C5_2 E,
    C6_2 F,
    C7_2 G,
    C8_2 H,
    C9_2 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_3 A,
    C2_3 B,
    C3_3 C,
    C4_3 D,
    C5_3 E,
    C6_3 F,
    C7_3 G,
    C8_3 H,
    C9_3 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_4 A,
    C2_4 B,
    C3_4 C,
    C4_4 D,
    C5_4 E,
    C6_4 F,
    C7_4 G,
    C8_4 H,
    C9_4 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_5 A,
    C2_5 B,
    C3_5 C,
    C4_5 D,
    C5_5 E,
    C6_5 F,
    C7_5 G,
    C8_5 H,
    C9_5 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_6 A,
    C2_6 B,
    C3_6 C,
    C4_6 D,
    C5_6 E,
    C6_6 F,
    C7_6 G,
    C8_6 H,
    C9_6 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_7 A,
    C2_7 B,
    C3_7 C,
    C4_7 D,
    C5_7 E,
    C6_7 F,
    C7_7 G,
    C8_7 H,
    C9_7 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_8 A,
    C2_8 B,
    C3_8 C,
    C4_8 D,
    C5_8 E,
    C6_8 F,
    C7_8 G,
    C8_8 H,
    C9_8 I
FROM
    SUDOKU_SOLUTION
UNION ALL
SELECT
    C1_9 A,
    C2_9 B,
    C3_9 C,
    C4_9 D,
    C5_9 E,
    C6_9 F,
    C7_9 G,
    C8_9 H,
    C9_9 I
FROM
    SUDOKU_SOLUTION;

Results
The DBMS found the complete solution:
It is worth noting that it is not very efficent to use the DBMS to search for a solution of this kind. On my Lenovo T400 (Dual Core 2.53Ghz with 2 gig's of RAM) running Oracle XE on Windows XP it took 3:30 minutes! However, it is fun to show that you can have the DBMS find a solution with one SQL statement.

No comments:

Post a Comment