Database Innovations

Sudoku

Bloggers:

You might be interested in some of the blog entries on this Oracle PL/SQL Sudoku solver:

Steven Feuerstein

Patrick Barel

Forum:

Sudoku Forum

Codetips:

Need some help with building some Oracle PL/SQL solutions? Then these articles may be of use...

1. Dynamic SQL: A performance tuning guide.

2. Bulk Data Loading: The available approaches.

3. Report Writing: Using Oracle XML, XSL, and HTML.

4. Data Driven Processing: XML Metadata

Oracle PL/SQL Sudoku Solver - Algorithms

Links to Sudoku; or algorithms 1, 2, 3, or 4, userguide or download

1. Singles - cell

If there is only a single remaining pencil mark in a cell, then it must be a certainty. Any other candidates with the same value in the same box, row or column can be eliminated.

In the above example, the number 7 in red is a single candidates in a cell. The blue numbers can then be rubbed out.

This is the SQL statement used to identify the candidates that meet the criteria.

UPDATE answers
SET     pencil_mark_ind = 0
WHERE   pencil_mark_ind > 0
AND     puzzle_id = p_puzzle_id
AND    (row_id, col_id) IN
    (   SELECT a.row_id,
               a.col_id
        FROM   answers a
        WHERE a.puzzle_id = p_puzzle_id
        AND    a.pencil_mark_ind > 0
        GROUP BY a.row_id,
               a.col_id
        HAVING COUNT(*) = 1);

Each time new certainties are found, then any other candidates remaining in the cell can be rubbed out, and any candidates with the same value in the same box, row or column, but different cell can also be rubbed out.

This eliminates the candidates in the same cell...

UPDATE answers a
SET    pencil_mark_ind = -1
WHERE  a.pencil_mark_ind > 0
AND    a.puzzle_id = p_puzzle_id
AND    (a.row_id, a.col_id) IN
       (SELECT a2.row_id,
                a2.col_id
         FROM   answers a2
         WHERE  a2.pencil_mark_ind = 0
         AND    a2.puzzle_id = p_puzzle_id);

This eliminates the candidates in the same box, row, or column (iterated three times for box, row, and column)...

FOR i IN 1 .. 3 LOOP
    UPDATE answers a
    SET    a.pencil_mark_ind = -1
    WHERE  a.pencil_mark_ind > 0
    AND    a.puzzle_id = p_puzzle_id
    AND    (a.answer, DECODE(i,
                             1, a.box_id,
                             2, a.row_id,
                             3, a.col_id
                             )
            ) IN
            (SELECT  a2.answer,
                    DECODE(i,
                           1, a2.box_id,
                           2, a2.row_id,
                           3, a2.col_id)
             FROM   answers a2
             WHERE  a2.puzzle_id = p_puzzle_id
             AND    a2.pencil_mark_ind = 0
             AND    (a2.row_id != a.row_id
                 OR a2.col_id != a.col_id)
            );

END LOOP;

To view the other algorithms select the required link...

1. Singles - Cell

2. Singles -Box

3. Cross Hatching

4. Partial Members Set

Oracle PL/SQL Sudoku Solver Oracle PL/SQL Sudoku Solver Oracle PL/SQL Sudoku Solve Oracle PL/SQL Sudoku Solver Oracle PL/SQL Oracle PL/SQL