Oracle PL/SQL Sudoku Solver

4. Partial Member Sets

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

This algorithm works with sets of unique candidate numbers. A set has n members of unique numbers. The algorithm looks for n cells in a box, row or column containing only members of the set, whether a partial set or full set. When it finds n cells, with up to n set members in a cell, and no non-members in the cell, it can then eliminate any other occurrence of the numbers in other cells.

The value of n can range from 2 upwards, but a maximum set size of 5 seems to be the most practical limit.

For example, a row could have three cells containing the candidates: 5,7 ; 3,5 ; and 3,7 (see number in red below). These all belong to set 357. Candidates in other cells with the same value in the same row (see numbers in blue below) can be eliminated.


Like with the previous algorithm, once candidates have been removed, then the Singles algorithms need to be applied to identify any certainties.

Once no more three member sets can be found, then four member sets can be identified, and so on until five member sets. This puzzle has an example of a four member set (1469) in a column (see below).

This puzzle example will now completely solve itself just by iterating through the singles algorithms - starting with the 9 highlighted in green.

This is the SQL to identify the partially complete sets.

UPDATE answers
SET    pencil_mark_ind = 2 
WHERE  pencil_mark_ind > 0
AND    puzzle_id = p_puzzle_id
AND    (row_id, col_id) IN
   (SELECT  /* -------------------------
            STEP E:
            This sub-query identifies 
            the cells which are entirely
            made up of candidates 
            belonging to the same set 
            spread across n cells in a 
            box/row/column.
            ------------------------- */

            a.row_id,
            a.col_id
     FROM   (SELECT /* -------------------------
                    STEP C:
                    This in-line view identifies 
                    all the possible sets 
                    (combinations) of size n 
                    within a cell and that set 
                    appearing up to and
                    including the most number 
                    of candidates identified
                    in step A. 
                    ------------------------- */ 

                    a.box_id,
                    a.row_id,
                    a.col_id,
                    pn.set_id,
                    COUNT(*) cnt
             FROM   combinations pn,
                    (SELECT /* ------------------------
                            STEP B:
                            This in-line view retrieves 
                            all the candidates from the 
                            cells having exactly n or 
                            less candidates 
                            ------------------------- */
 
                            b.box_id,
                            b.row_id,
                            b.col_id,
                            a.cnt,
                            b.answer
                     FROM   (SELECT /* ------------------
                                    STEP A:
                                    This in-line view 
                                    identifies those 
                                    cells which have 
                                    exactly n (set size) 
                                    or less candidates 
                                    in the cell. 
                                    ----------------- */ 

                                    a.box_id,
                                    a.row_id,
                                    a.col_id,
                                    COUNT(*) cnt
                             FROM   answers a
                             WHERE  a.puzzle_id = p_puzzle_id
                             AND    a.pencil_mark_ind > 0
                             GROUP  BY a.box_id,
                                       a.row_id,
                                       a.col_id
                             HAVING COUNT(*) <= n
                            ) a,
                            answers b
                     WHERE  a.box_id = b.box_id
                     AND    a.row_id = b.row_id
                     AND    a.col_id = b.col_id
                     AND    b.puzzle_id = p_puzzle_id
                     AND    b.pencil_mark_ind > 0
                     ) a
             WHERE  pn.set_size = n
             AND    a.answer = pn.puzzle_number
             GROUP  BY a.box_id,
                       a.row_id,
                       a.col_id,
                       pn.set_id
             HAVING COUNT(*) = MAX(a.cnt)
             ) a,
            (SELECT /* ---------------------------
                    STEP D:
                    This in-line view repeats steps
                    A, B and C to identify the 
                    cells again, and then
                    selects the box/row/column 
                    which has the sets 
                    appearing in n cells in 
                    that box/row/column
                    ----------------------------- */

                    DECODE(p_type,
                           1, a.box_id,
                           2, a.row_id,
                           3, a.col_id) id,
                    a.set_id
             FROM   (SELECT a.box_id,
                            a.row_id,
                            a.col_id,
                            pn.set_id,
                            COUNT(*) cnt
                     FROM   combinations pn,
                            (SELECT b.box_id,
                                    b.row_id,
                                    b.col_id,
                                    a.cnt,
                                    b.answer
                             FROM  (SELECT  a.box_id,
                                            a.row_id,
                                            a.col_id,
                                            COUNT(*) cnt
                                     FROM   answers a
                                     WHERE  a.puzzle_id =
                                            p_puzzle_id
                                     AND    a.pencil_mark_ind > 0
                                     GROUP  BY a.box_id,
                                               a.row_id,
                                               a.col_id
                                     HAVING COUNT(*) <= n
                                    ) a,
                                    answers b
                             WHERE  a.box_id = b.box_id
                             AND    a.row_id = b.row_id
                             AND    a.col_id = b.col_id
                             AND    b.puzzle_id = p_puzzle_id
                             AND    b.pencil_mark_ind > 0) a
                     WHERE  pn.set_size = n
                     AND    a.answer = pn.puzzle_number
                     GROUP  BY a.box_id,
                               a.row_id,
                               a.col_id,
                               pn.set_id
                     HAVING COUNT(*) = MAX(a.cnt)
                     ) a
             GROUP  BY DECODE(p_type,
                              1, a.box_id,
                              2, a.row_id,
                              3, a.col_id),
                       a.set_id
             HAVING COUNT(*) = n
             ) s
     WHERE  s.id = DECODE(p_type,
                          1, a.box_id,
                          2, a.row_id,
                          3, a.col_id)
     AND    s.set_id = a.set_id
     );


To rub out the affected candidates use this statement for box, row, and column...

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

After the candidates have been removed, then the Singles algorithms (1 and 2) can be applied and iterated continuously until no more certainties can be found.

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

1. Singles - Cell

2. Singles -Box

3. Cross Hatching

4. Partial Members Set

5. Full Member Set

 


webmaster@db-innovations.co.uk : Copyright 2005 - 2010 Database Innovations Ltd : Last modified: 27/08/10