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

3. Pencil Mark Cross Hatching

For each candidate pair or candidate triple (of the same value forming a row or column in a box, and not appearing in any other cell in the box), eliminate the candidates of the same value in the same row or column but in a different box.

The numbers in red are examples of candidate pairs in a box. They must be the only two in a box and form a line either in a column or a row. The numbers in blue are the candidates that can be eliminated.

The algorithm also applies to candidate triples in a box forming a line in either or row or column.

Each time numbers are eliminated, then first two singles algorithms need to be applied to identify certainties. With the above example, it is now possible to iterate through just the singles algorithms only and solve the rest of the puzzle.

The update is performed once for pairs (n=2) and once for triples (n=3). This statement will mark the candidate pairs and triples with the temporary pencil mark value of 2.

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

Immediately after each update above, affected candidates can be eliminated (by setting the pencil mark to -1, i.e. rubbed out). The statement is looped through twice, once for rows, and once for columns...

FOR i IN 1 .. 2 LOOP
    UPDATE answers a
    SET    pencil_mark_ind = -1
    WHERE  a.pencil_mark_ind > 0
    AND    a.puzzle_id = p_puzzle_id
    AND    (DECODE(i,
                   1, a.row_id,
                   2, a.col_id
                   ),
            a.answer
           ) IN
           (SELECT DECODE(i,
                           1, a2.row_id,
                           2, a2.col_id
                         ),
                    a2.answer
             FROM   answers a2
             WHERE  a2.pencil_mark_ind = 2
             AND    a2.puzzle_id = p_puzzle_id
             AND    a2.box_id != a.box_id
             GROUP  BY a2.box_id,
                       decode(i,
                              1, a2.row_id,
                              2, a2.col_id
                             ),
                       a2.answer
             HAVING COUNT(*) = n);

END LOOP;

After the candidates have been removed, then the Singles algorithms can be applied and iterated continuously until no more certainties can be identified.

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 Solver Oracle PL/SQL Sudoku Solver Oracle PL/SQL Oracle PL/SQL