|
Sudoku
|
Oracle PL/SQL
Sudoku Solver - Algorithms
Links to
Sudoku; or algorithms
1, 2,
3, or 4,
userguide
or download
4. Partial Member
Sets
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
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 |
|
