Oracle PL/SQL Sudoku Solver

5. Full Member Sets

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

This algorithm is hardly ever used, so not sure why have I included it, but it does work if ever given the opportunity. It was not used to solve "The Times Ultra Fiendish" Sudoku puzzle.

Where we have a sub-set of candidates in a cell consisting of a group of unique numbers forming a full set of n members, and this set appears in exactly n cells in either a box, row, or column, then all the other candidates not in the set in these cells can be eliminated.

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 D:
                This sub-query identifies 
                the cells with full member
                sets (f size n) appearing n 
                times in a box/row/column 
                ------------------------- */

                a.row_id,
                a.col_id
         FROM   (SELECT /* -------------------------
                        STEP C:
                        This repeats step A to 
                        identify the cells
                        ------------------------- */

                        a.box_id,
                        a.row_id,
                        a.col_id,
                        pn.set_id,
                        COUNT(*) cnt
                 FROM   combinations pn,
                        answers      a
                 WHERE  pn.set_size = p_size
                 AND    a.answer = pn.puzzle_number
                 AND    a.puzzle_id = p_puzzle_id
                 AND    a.pencil_mark_ind > 0
                 GROUP  BY a.box_id,
                           a.row_id,
                           a.col_id,
                           pn.set_id
                 HAVING COUNT(*) = n
                 ) a,
                (SELECT /* -------------------------
                        STEP B:
                        This in-line view identifies
                        boxes/rows/columns which
                        have n cells with full 
                        member sets of size n
                        ------------------------- */

                        DECODE(1,
                               1, a.box_id,
                               2, a.row_id,
                               3, a.col_id) id,
                        a.set_id
                 FROM   (SELECT /* ----------------------
                                STEP A:
                                This in-line view  
                                identifies cells which have 
                                candidates for all members 
                                of a set ofsize n. The set 
                                can be a sub-set of all 
                                candidates in the cell, but 
                                must have all members. 
                                ---------------------- */

                                a.box_id,
                                a.row_id,
                                a.col_id,
                                pn.set_id,
                                COUNT(*) cnt
                         FROM   combinations pn,
                                answers      a
                         WHERE  pn.set_size = p_size
                         AND    a.answer = pn.puzzle_number
                         AND    a.puzzle_id = p_puzzle_id
                         AND    a.pencil_mark_ind > 0
                         GROUP  BY a.box_id,
                                   a.row_id,
                                   a.col_id,
                                   pn.set_id
                         HAVING COUNT(*) = n
                         ) a
                 GROUP  BY DECODE(1,
                                  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 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