How to solve it with SQL: January 2011

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:

				7			4	5
	2	5		8	4	6
	7	1		6	3	2
	1			5	2
	9	4				3	2
			3	9			5
		3	9	2		5	8
		9	6	4		7	3
6	8			3

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.

Thursday, January 6, 2011

Optimization problems

I will soon post an example of how to add optimization to the SQL method for CSP's. The Zebra problem is only constraint satisfaction and does not incorporate optimization.

Who owns the Zebra? SQL Solution

Have you ever come across the "Who owns the Zebra?" problem? If you're reading this blog, it means you probably have. It's one of the most well-known constraint satisfaction problems and quite easy to solve using only pen and paper and logical inference. On the other hand, if you were to use a computer, you might use a constraint solver like Prolog with CSP extensions (e.g. Sicstus Prolog). However, it's also possible to generate a solution using only SQL. In this case I've been using Oracle SQL and the free version of Oracle DBMS (Oracle XE). I'll jump right in...

The problem
There are five houses, each of a different color and inhabited by men of different nationalities, with different pets, favorite drinks, and cars. Moreover, there are several constraints:

The Enghlishman lives in the red house.
The Spaniard owns the dog.
The man in the green house drinks cocoa.
The Ukrainian drinks eggnog.
The green house is immediately to the right (your right) of the ivory house.
The owner of the Oldsmobile also owns snails.
The owner of the Ford lives in the yellow house.
The man in the middle house drinks milk.
The Norwegian lives in the first house on the left.
The man who owns the Chevrolet lives in the house next to the house where the man owns a fox.
The Ford owners's house is next to the house where the horse is kept.
The Mercedes-Benz owner drinks orange juice.
The Japanese drives a Volkswagen.
The Norwegian lives next to the blue house

The question is: Who owns the Zebra?
Modelling the problem
From the above we can extract the following information; there are five houses each having five variables each pertaining to the house or the owner of the house The variables are color, nationality, pet, drink and car. Each variable has a domain of five possible values:

Color ∈ {Red,Blue,Yellow,Green,Ivory}
Nationality ∈ {Norwegian,English,Spanish,Japanese,Ukrainian}
Pet ∈ {Dog,Horse,Zebra,Snail,Fox}
Drink ∈ {Cocoa,Eggnog,Orange juice,Milk,Water}
Car ∈ {Oldsmobile,Ford,Mercedes-Benz,Chevrolet,Volkswagen}

Next we have an index for house from the set N ∈ {1,2,3,4,5}. We said that we have five houses with five variables each, which gives us 25 variables. These variables are named with abbreviations (where n ∈ N, i.e. house 1, 2, 3, etc):

Color: CLR_n
Nationality: N_n
Pet: P_n
Drink: D_n
Car: C_n

Constraint modelling
Now that we have identified the variables and enumerated their domains, we need to formalize the constraints.

All variables must have unique domain assignments. I.e. there can only be one blue house, only one yellow house, only one green house, only one ivory-colored house and only one red house, and so on...

In logical notation this can be written as

NONEEQUAL ⇒
∀n∈N,∀m∈N:(n≠m)∧(CLR_n≠CLR_m)∧(N_n≠N_m)∧(D_n≠D_m)∧(P_n≠P_m)∧(C_n≠C_m)
The Enghlishman lives in the red house

∀n∈N:N_n=English⇒CLR_n=Red
The Spaniard owns the dog

∀n∈N:N_n=Spanish⇒P_n=Dog
The man in the green house drinks cocoa

∀n∈N:CLR_n=Green⇒D_n=Cocoa
The Ukrainian drinks eggnog

∀n∈N:N_n=Ukrainian⇒D_n=eggnog
The green house is immediately to the right (your right) of the ivory house

∀n∈N,(n<5):clr_n=Ivory⇒CLR_n+1=Green
The owner of the Oldsmobile also owns snails

∀n∈N:C_n=Oldsmobile⇒P_n=Snail
The owner of the Ford lives in the yellow house

∀n∈N:C_n=Ford⇒CLR_n=Yellow
The man in the middle house drinks milk

D₃=Milk
The Norwegian lives in the first house on the left

N₃=Norwegian
The man who owns the Chevrolet lives in the house next to the house where the man owns a fox

∀n∈N,(n<5):(c_n=Chevrolet⇒P_n+1=Fox)∨(P_n=Fox⇒C_n+1=Chevrolet)
The Ford owners's house is next to the house where the horse is kept

∀n∈N,(n<5):(c_n=Ford⇒P_n+1=Horse)∨(P_n=Horse⇒C_n+1=Ford)
The Mercedes-Benz owner drinks orange juice

∀n∈N:C_n=Mercedes Benz⇒D_n=Orange juice
The Japanese drives a Volkswagen

∀n∈N:N_n=Japanese⇒C_n=Volkswagen
The Norwegian lives next to the blue house

∀n∈N,(n<5):(n_n=Norwegian⇒CLR_n+1=Blue)∨(CLR_n=Blue⇒N_n+1=Norwegian)

Implementing the model in SQL
Now for the fun part. We're going to model both the problem and the constraints in plain SQL so that the DBMS can search for a solution. We will do this without storing any data to a physical database table. Let's go.

Implement the variable domains

-- Setup variable domains (Color, Nationality, Pet, Drink, Car)
CREATE OR REPLACE VIEW V_WOTZ_COLORS AS
SELECT
COLORS.V COLOR
FROM
(SELECT 'Red' V FROM DUAL UNION ALL
SELECT 'Blue' V FROM DUAL UNION ALL
SELECT 'Green' V FROM DUAL UNION ALL
SELECT 'Ivory' V FROM DUAL UNION ALL
SELECT 'Yellow' V FROM DUAL) COLORS;

CREATE OR REPLACE VIEW V_WOTZ_NATIONALITIES AS
SELECT
NATIONALITIES.V NATIONALITY
FROM
(SELECT 'English' V FROM DUAL UNION ALL
SELECT 'Spanish' V FROM DUAL UNION ALL
SELECT 'Norwegian' V FROM DUAL UNION ALL
SELECT 'Ukrainian' V FROM DUAL UNION ALL
SELECT 'Japanese' V FROM DUAL) NATIONALITIES;

CREATE OR REPLACE VIEW V_WOTZ_PETS AS
SELECT
PETS.V PET
FROM
(SELECT 'Dog' V FROM DUAL UNION ALL
SELECT 'Snail' V FROM DUAL UNION ALL
SELECT 'Fox' V FROM DUAL UNION ALL
SELECT 'Horse' V FROM DUAL UNION ALL
SELECT 'Zebra' V FROM DUAL) PETS;

CREATE OR REPLACE VIEW V_WOTZ_DRINKS AS
SELECT
DRINKS.V DRINK
FROM
(SELECT 'Cocoa' V FROM DUAL UNION ALL
SELECT 'Eggnog' V FROM DUAL UNION ALL
SELECT 'Orange juice' V FROM DUAL UNION ALL
SELECT 'Milk' V FROM DUAL UNION ALL
SELECT 'Water' V FROM DUAL) DRINKS;

CREATE OR REPLACE VIEW V_WOTZ_CARS AS
SELECT
CARS.V CAR
FROM
(SELECT 'Oldsmobile' V FROM DUAL UNION ALL
SELECT 'Ford' V FROM DUAL UNION ALL
SELECT 'Chevrolet' V FROM DUAL UNION ALL
SELECT 'Mercedes Benz' V FROM DUAL UNION ALL
SELECT 'Volkswagen' V FROM DUAL) CARS;
Generate solutions and apply constraints. This is where we solve it!

WITH SOLUTION AS
-- Find a solution which satisfies the constraints
(SELECT
ROWNUM SOLUTION_ID,

CLR1.COLOR CLR1,
N1.NATIONALITY N1,
P1.PET P1,
D1.DRINK D1,
C1.CAR C1,

CLR2.COLOR CLR2,
N2.NATIONALITY N2,
P2.PET P2,
D2.DRINK D2,
C2.CAR C2,

CLR3.COLOR CLR3,
N3.NATIONALITY N3,
P3.PET P3,
D3.DRINK D3,
C3.CAR C3,

CLR4.COLOR CLR4,
N4.NATIONALITY N4,
P4.PET P4,
D4.DRINK D4,
C4.CAR C4,

CLR5.COLOR CLR5,
N5.NATIONALITY N5,
P5.PET P5,
D5.DRINK D5,
C5.CAR C5
FROM
(SELECT COLOR FROM V_WOTZ_COLORS) CLR1,
(SELECT COLOR FROM V_WOTZ_COLORS) CLR2,
(SELECT COLOR FROM V_WOTZ_COLORS) CLR3,
(SELECT COLOR FROM V_WOTZ_COLORS) CLR4,
(SELECT COLOR FROM V_WOTZ_COLORS) CLR5,

(SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N1,
(SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N2,
(SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N3,
(SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N4,
(SELECT NATIONALITY FROM V_WOTZ_NATIONALITIES) N5,

(SELECT PET FROM V_WOTZ_PETS) P1,
(SELECT PET FROM V_WOTZ_PETS) P2,
(SELECT PET FROM V_WOTZ_PETS) P3,
(SELECT PET FROM V_WOTZ_PETS) P4,
(SELECT PET FROM V_WOTZ_PETS) P5,

(SELECT DRINK FROM V_WOTZ_DRINKS) D1,
(SELECT DRINK FROM V_WOTZ_DRINKS) D2,
(SELECT DRINK FROM V_WOTZ_DRINKS) D3,
(SELECT DRINK FROM V_WOTZ_DRINKS) D4,
(SELECT DRINK FROM V_WOTZ_DRINKS) D5,

(SELECT CAR FROM V_WOTZ_CARS) C1,
(SELECT CAR FROM V_WOTZ_CARS) C2,
(SELECT CAR FROM V_WOTZ_CARS) C3,
(SELECT CAR FROM V_WOTZ_CARS) C4,
(SELECT CAR FROM V_WOTZ_CARS) C5
WHERE
((CLR1.COLOR NOT IN (CLR2.COLOR,CLR3.COLOR,CLR4.COLOR,CLR5.COLOR) AND
CLR2.COLOR NOT IN (CLR3.COLOR,CLR4.COLOR,CLR5.COLOR) AND
CLR3.COLOR NOT IN (CLR4.COLOR,CLR5.COLOR) AND
CLR4.COLOR NOT IN (CLR5.COLOR)) AND
(N1.NATIONALITY NOT IN (N2.NATIONALITY,N3.NATIONALITY,N4.NATIONALITY,N5.NATIONALITY) AND
N2.NATIONALITY NOT IN (N3.NATIONALITY,N4.NATIONALITY,N5.NATIONALITY) AND
N3.NATIONALITY NOT IN (N4.NATIONALITY,N5.NATIONALITY) AND
N4.NATIONALITY NOT IN (N5.NATIONALITY)) AND
(P1.PET NOT IN (P2.PET,P3.PET,P4.PET,P5.PET) AND
P2.PET NOT IN (P3.PET,P4.PET,P5.PET) AND
P3.PET NOT IN (P4.PET,P5.PET) AND
P4.PET NOT IN (P5.PET)) AND
(D1.DRINK NOT IN (D2.DRINK,D3.DRINK,D4.DRINK,D5.DRINK) AND
D2.DRINK NOT IN (D3.DRINK,D4.DRINK,D5.DRINK) AND
D3.DRINK NOT IN (D4.DRINK,D5.DRINK) AND
D4.DRINK NOT IN (D5.DRINK)) AND
(C1.CAR NOT IN (C2.CAR,C3.CAR,C4.CAR,C5.CAR) AND
C2.CAR NOT IN (C3.CAR,C4.CAR,C5.CAR) AND
C3.CAR NOT IN (C4.CAR,C5.CAR) AND
C4.CAR NOT IN (C5.CAR)))
AND
(
(N1.NATIONALITY = 'English' AND CLR1.COLOR = 'Red') OR
(N2.NATIONALITY = 'English' AND CLR2.COLOR = 'Red') OR
(N3.NATIONALITY = 'English' AND CLR3.COLOR = 'Red') OR
(N4.NATIONALITY = 'English' AND CLR4.COLOR = 'Red') OR
(N5.NATIONALITY = 'English' AND CLR5.COLOR = 'Red')
)
AND
(
(N1.NATIONALITY = 'Spanish' AND P1.PET = 'Dog') OR
(N2.NATIONALITY = 'Spanish' AND P2.PET = 'Dog') OR
(N3.NATIONALITY = 'Spanish' AND P3.PET = 'Dog') OR
(N4.NATIONALITY = 'Spanish' AND P4.PET = 'Dog') OR
(N5.NATIONALITY = 'Spanish' AND P5.PET = 'Dog')
)
AND
(
(CLR1.COLOR = 'Green' AND D1.DRINK = 'Cocoa') OR
(CLR2.COLOR = 'Green' AND D2.DRINK = 'Cocoa') OR
(CLR3.COLOR = 'Green' AND D3.DRINK = 'Cocoa') OR
(CLR4.COLOR = 'Green' AND D4.DRINK = 'Cocoa') OR
(CLR5.COLOR = 'Green' AND D5.DRINK = 'Cocoa')
)
AND
(
(N1.NATIONALITY = 'Ukrainian' AND D1.DRINK = 'Eggnog') OR
(N2.NATIONALITY = 'Ukrainian' AND D2.DRINK = 'Eggnog') OR
(N3.NATIONALITY = 'Ukrainian' AND D3.DRINK = 'Eggnog') OR
(N4.NATIONALITY = 'Ukrainian' AND D4.DRINK = 'Eggnog') OR
(N5.NATIONALITY = 'Ukrainian' AND D5.DRINK = 'Eggnog')
)
AND
(
(CLR1.COLOR = 'Ivory' AND CLR2.COLOR = 'Green') OR
(CLR2.COLOR = 'Ivory' AND CLR3.COLOR = 'Green') OR
(CLR3.COLOR = 'Ivory' AND CLR4.COLOR = 'Green') OR
(CLR4.COLOR = 'Ivory' AND CLR5.COLOR = 'Green')
)
AND
(
(C1.CAR = 'Oldsmobile' AND P1.PET = 'Snail') OR
(C2.CAR = 'Oldsmobile' AND P2.PET = 'Snail') OR
(C3.CAR = 'Oldsmobile' AND P3.PET = 'Snail') OR
(C4.CAR = 'Oldsmobile' AND P4.PET = 'Snail') OR
(C5.CAR = 'Oldsmobile' AND P5.PET = 'Snail')
)
AND
(
(C1.CAR = 'Ford' AND CLR1.COLOR = 'Yellow') OR
(C2.CAR = 'Ford' AND CLR2.COLOR = 'Yellow') OR
(C3.CAR = 'Ford' AND CLR3.COLOR = 'Yellow') OR
(C4.CAR = 'Ford' AND CLR4.COLOR = 'Yellow') OR
(C5.CAR = 'Ford' AND CLR5.COLOR = 'Yellow')
)
AND
(
D3.DRINK = 'Milk'
)
AND
(
N1.NATIONALITY = 'Norwegian'
)
AND
(
(
(C1.CAR = 'Chevrolet' AND P2.PET = 'Fox') OR
(C2.CAR = 'Chevrolet' AND P3.PET = 'Fox') OR
(C3.CAR = 'Chevrolet' AND P4.PET = 'Fox') OR
(C4.CAR = 'Chevrolet' AND P5.PET = 'Fox')
)
OR
(
(P1.PET = 'Fox' AND C2.CAR = 'Chevrolet') OR
(P2.PET = 'Fox' AND C3.CAR = 'Chevrolet') OR
(P3.PET = 'Fox' AND C4.CAR = 'Chevrolet') OR
(P4.PET = 'Fox' AND C5.CAR = 'Chevrolet')
)
)
AND
(
(
(C1.CAR = 'Ford' AND P2.PET = 'Horse') OR
(C2.CAR = 'Ford' AND P3.PET = 'Horse') OR
(C3.CAR = 'Ford' AND P4.PET = 'Horse') OR
(C4.CAR = 'Ford' AND P5.PET = 'Horse')
)
OR
(
(P1.PET = 'Horse' AND C2.CAR = 'Ford') OR
(P2.PET = 'Horse' AND C3.CAR = 'Ford') OR
(P3.PET = 'Horse' AND C4.CAR = 'Ford') OR
(P4.PET = 'Horse' AND C5.CAR = 'Ford')
)
)
AND
(
(C1.CAR = 'Mercedes Benz' AND D1.DRINK = 'Orange juice') OR
(C2.CAR = 'Mercedes Benz' AND D2.DRINK = 'Orange juice') OR
(C3.CAR = 'Mercedes Benz' AND D3.DRINK = 'Orange juice') OR
(C4.CAR = 'Mercedes Benz' AND D4.DRINK = 'Orange juice') OR
(C5.CAR = 'Mercedes Benz' AND D5.DRINK = 'Orange juice')
)
AND
(
(N1.NATIONALITY = 'Japanese' AND C1.CAR = 'Volkswagen') OR
(N2.NATIONALITY = 'Japanese' AND C2.CAR = 'Volkswagen') OR
(N3.NATIONALITY = 'Japanese' AND C3.CAR = 'Volkswagen') OR
(N4.NATIONALITY = 'Japanese' AND C4.CAR = 'Volkswagen') OR
(N5.NATIONALITY = 'Japanese' AND C5.CAR = 'Volkswagen')
)
AND
(
(
(N1.NATIONALITY = 'Norwegian' AND CLR2.COLOR = 'Blue') OR
(N2.NATIONALITY = 'Norwegian' AND CLR3.COLOR = 'Blue') OR
(N3.NATIONALITY = 'Norwegian' AND CLR4.COLOR = 'Blue') OR
(N4.NATIONALITY = 'Norwegian' AND CLR5.COLOR = 'Blue')
)
OR
(
(CLR1.COLOR = 'Blue' AND N2.NATIONALITY = 'Norwegian') OR
(CLR2.COLOR = 'Blue' AND N3.NATIONALITY = 'Norwegian') OR
(CLR3.COLOR = 'Blue' AND N4.NATIONALITY = 'Norwegian') OR
(CLR4.COLOR = 'Blue' AND N5.NATIONALITY = 'Norwegian')
)
))
SELECT
'Color' VARIABLE,
CLR1 HOUSE1,
CLR2 HOUSE2,
CLR3 HOUSE3,
CLR4 HOUSE4,
CLR5 HOUSE5
FROM
SOLUTION
UNION ALL
SELECT
'Nationality' VARIABLE,
N1 HOUSE1,
N2 HOUSE2,
N3 HOUSE3,
N4 HOUSE4,
N5 HOUSE5
FROM
SOLUTION
UNION ALL
SELECT
'Drink' VARIABLE,
D1 HOUSE1,
D2 HOUSE2,
D3 HOUSE3,
D4 HOUSE4,
D5 HOUSE5
FROM
SOLUTION
UNION ALL
SELECT
'Pet' VARIABLE,
P1 HOUSE1,
P2 HOUSE2,
P3 HOUSE3,
P4 HOUSE4,
P5 HOUSE5
FROM
SOLUTION
UNION ALL
SELECT
'Car' VARIABLE,
C1 HOUSE1,
C2 HOUSE2,
C3 HOUSE3,
C4 HOUSE4,
C5 HOUSE5
FROM
SOLUTION;

Result
The DBMS found the only solution to the problem given the constraints.

The answer to the question: The Japanese owns the Zebra! What's cool is that the DBMS found the answer.

Discussion
The SQL methodology is as follows.

Do a cartesian join on all the 25 variables. We'll call this the UNIVERSAL set.

This yields (5⁵)⁵combinations, an unmanageable amount of data. Which is why we need to apply step 2.
Apply the constraints. This is done in the where-clause of the SQL statement.

After we've applied the NONEEQUAL constraint, the number of combinations have been reduced to (5!)⁵

Note that the SQL statement above never stores all these combinations to a physical table or in memory. The trick is that the DBMS will build the result set by applying the given constraints (from the where-clause) in the order it finds most efficient. Not until all the constraints have been satisfied, will the DBMS present the result set.

Try it! It works.