Pure PL/SQL Sudoku solver
Back when Sudokus were new-ish and everybody was writing Sudoku solvers as a coding challenge, it occurred to me in a moment of inspiration that you could probably deduce most blank cells' values by finding the intersection of the unused values for their row, column and square. So for example, if the cell's row currently contained all the numbers exept 1, 2 and 3, its column all except 2, 3 and 4, and its square all except 3, 7 and 9, then the missing value must be 3. This wouldn't work for every cell of course, but if you kept looping over the puzzle using this method to fill in every blank you could, maybe that would be a set-based way to solve it.
I thought this was pretty neat until I looked up Sudoku-solving and found that my briliant technique was called "Forced Moves" and regarded as the most basic approach used by beginners on simple puzzles.
After some more thought, I came up with a second deduction approach, in which a possible value for a cell is checked to see if there is anywhere else it could go in its row. If not, then it must go in that cell. This seems to be known as "Intersections" and is also regarded as basic.
I built on this by adding a guessing loop, in which if the elimination approach cannot complete the puzzle, it takes each candidate value for each empty cell in turn, plugs that value in and retries the eliminator process. It turns out this is another standard technique, known variously as "What If", "Guess-and-Check", "Bifurcation", "Backtracking" or "Ariadne's thread". (I'm less keen on this kind of brute-force approach to be honest, as I'd prefer my programming challenge to use proper logical deduction, but used as a final when-all-else-fails method it cracks a lot of ultra-fiendish Sudokus that it otherwise couldn't.)
The row/column/square free values intersection code uses the handy multiset intersect operator,
the validation procedure uses is a set, and I've used member of in the "cross hatching" algorithm.
I also used some conditional compilation for diagnostic output.
The next straightforward algorithm I want to add in a future version is "matched groups", described in Wikipedia as follows:
One method works by identifying "matched cell groups". For instance, if precisely two cells within a scope (a particular row, column, or region) contain the same two candidate numerals (p,q), or if precisely three cells within a scope contain the same three candidate numerals (p,q,r), these cells are said to be matched. The placement of those candidate numerals anywhere else within that same scope would make a solution impossible; therefore, those candidate numerals can be deleted from all other cells in the scope.
I also want to add what the Brainbashers page calls Intersection Removal, in which for example you narrow down the location of the 5 within a box to one of two positions, and these fall within the same row or column: now even though you don't know exactly which position it goes in, you still have enough information to exclude the rest of that row or column.
To install using SQL*Plus, download sudoku.pls and run it from the SQL> prompt.
@sudoku.pls
This will cleanly drop all sudoku_* types, avoiding type dependency issues.
-- PL/SQL Sudoku Solver
-- William Robertson 2007, www.williamrobertson.net
-- Improved version incorporating additional cross-hatching algorithm and guessing loop.
-- Allow optional parameter
set feed off term off define on verify off echo off
--col 1 new_value 1
col persistance new_value persistance
--select null as "1" from dual where 1=2;
-- "&1" now has value passed on command line, or null
select case when to_number(regexp_replace(version_full,'\..*')) >= 18 then 'not persistable' end as persistance from v$instance;
-- "&persistance" now has the value 'not persistable' if database version is 18 or later
set term on
begin
for r in (
select * from user_types t
where t.type_name in ('SUDOKU','SUDOKU_ELEMENT_TT','SUDOKU_ELEMENT','SUDOKU_CELL_TT')
order by substr(t.type_name,8) nulls last
)
loop
execute immediate 'drop type ' || r.type_name || ' force';
dbms_output.put_line('Dropped type '||r.type_name);
end loop;
end;
/
set feed 1
-- I originally made SUDOKU_CELL_TT a VARRAY because it made sense to limit it to nine values, however the multiset operators
-- (MEMBER OF, MULTISET EXCEPT etc) only work on nested table collections.
create or replace type sudoku_cell_tt as table of (number(1)) &PERSISTANCE
/
prompt Type SUDOKU_ELEMENT:
create or replace type sudoku_element
as object
( cells sudoku_cell_tt
, member procedure check_valid -- Checks for dups, raises error (can't use name "validate")
( self in out nocopy sudoku_element
, p_label varchar2 default null ) -- Label for use in error message e.g. "Column 5"
, member procedure set_cell
( self in out nocopy sudoku_element
, p_position positive
, p_value positive )
, member function free_values -- Returns the set of missing numbers for a set
return sudoku_cell_tt
, member function free_locations -- Returns the set of blank cell positions for a set
return sudoku_cell_tt
, member procedure print
( self in out nocopy sudoku_element
, p_name varchar2 default null -- Optional label
, p_gridlines boolean default true ) -- Optionally print gridlines
, constructor function sudoku_element
( p_cell1 positive
, p_cell2 positive
, p_cell3 positive
, p_cell4 positive
, p_cell5 positive
, p_cell6 positive
, p_cell7 positive
, p_cell8 positive
, p_cell9 positive
, p_validate boolean default true )
return self as result
-- Convenient alternative constructor accepts a single character string e.g. '52 7 4 1'
, constructor function sudoku_element
( p_cell_string varchar2 )
return self as result
-- Another convenient alternative constructor populates with all nulls:
, constructor function sudoku_element
return self as result
) &PERSISTANCE
/
show errors type sudoku_element
prompt Type Body sudoku_element:
create or replace type body sudoku_element
as
member procedure check_valid
( self in out nocopy sudoku_element
, p_label varchar2 default null ) -- Label for use in error message e.g. "Column 5"
is
v_available sudoku_cell_tt;
begin
if self.cells is a set then
return;
else
v_available := new sudoku_cell_tt(null,null,null,null,null,null,null,null,null);
for i in self.cells.first..self.cells.last
loop
-- Place each element value into a blank set, checking for collisions:
if self.cells(i) is null then
null;
elsif v_available(self.cells(i)) is not null then
self.print(p_label);
raise_application_error
( -20000
, ltrim(p_label || ': ',': ') ||
'Value "' || self.cells(i) || '" is duplicated.'
, true );
else
v_available(self.cells(i)) := self.cells(i); -- Placeholder: this slot now taken
end if;
end loop;
end if;
end check_valid;
member procedure set_cell
( self in out nocopy sudoku_element
, p_position positive
, p_value positive )
is
begin
self.cells(p_position) := p_value;
-- Only need check during development, otherwise unnecessary overhead:
-- check_valid;
end set_cell;
-- Values not in self.cells
member function free_values
return sudoku_cell_tt
is
begin
-- Takes multiset 2 away from multiset 1, in this case [all numbers] minus [those we have used so far],
-- to return [unused numbers], i.e. possible values for an unresolved cell.
return sudoku_cell_tt(1,2,3,4,5,6,7,8,9) multiset except self.cells;
end free_values;
member function free_locations -- Returns the set of blank cell positions for a set
return sudoku_cell_tt
is
v_locations sudoku_cell_tt := sudoku_cell_tt();
begin
for i in self.cells.first..self.cells.last loop
if self.cells(i) is null then
v_locations.extend;
v_locations(v_locations.count) := i;
end if;
end loop;
return v_locations;
end free_locations;
member procedure print
( self in out nocopy sudoku_element
, p_name varchar2 default null -- Optional label
, p_gridlines boolean default true ) -- Optionally print gridlines
is
begin
dbms_output.put(rpad(nvl(p_name,'Element')||':',9));
for i in 1..9 loop
dbms_output.put(lpad(nvl(to_char(self.cells(i)),'-'),3));
if p_gridlines and i in (3,6) then
dbms_output.put(' |');
end if;
end loop;
dbms_output.new_line();
end print;
constructor function sudoku_element
( p_cell1 positive
, p_cell2 positive
, p_cell3 positive
, p_cell4 positive
, p_cell5 positive
, p_cell6 positive
, p_cell7 positive
, p_cell8 positive
, p_cell9 positive
, p_validate boolean default true ) -- Allowed to skip validation
return self as result -- e.g. when constructing from previously checked values
is
begin
self.cells :=
new sudoku_cell_tt(p_cell1,p_cell2,p_cell3,p_cell4,p_cell5,p_cell6,p_cell7,p_cell8,p_cell9);
if p_validate then
check_valid();
end if;
return;
end sudoku_element;
constructor function sudoku_element
( p_cell_string varchar2 )
return self as result
is
v_cell_string char(10) := rpad(nvl(p_cell_string,' '),10);
begin
self :=
new sudoku_element
( nullif(substr(v_cell_string,1,1),' ')
, nullif(substr(v_cell_string,2,1),' ')
, nullif(substr(v_cell_string,3,1),' ')
, nullif(substr(v_cell_string,4,1),' ')
, nullif(substr(v_cell_string,5,1),' ')
, nullif(substr(v_cell_string,6,1),' ')
, nullif(substr(v_cell_string,7,1),' ')
, nullif(substr(v_cell_string,8,1),' ')
, nullif(substr(v_cell_string,9,1),' ') );
return;
end sudoku_element;
constructor function sudoku_element
return self as result
is
begin
self.cells := new sudoku_cell_tt(null,null,null,null,null,null,null,null,null);
return;
end sudoku_element;
end;
/
show errors type body sudoku_element
-- Array type, 9 x sudoku elements:
prompt Type sudoku_element_tt (varray(9) of sudoku_element):
create or replace type sudoku_element_tt as varray(9) of (sudoku_element) &PERSISTANCE
/
/
show errors type sudoku_element_tt
prompt Type sudoku:
create or replace type sudoku as object
( s_rows sudoku_element_tt -- Array of 9 Sudoku Element objects (can't use name "rows")
, status varchar2(8) -- 'New'|'Solved'|'Unsolved'
, member function s_columns -- Getter function for a single specified column object
( p_col# integer )
return sudoku_element
, member function s_squares -- Getter function for a single specified square object
( p_square# integer )
return sudoku_element
, member procedure print
( p_gridlines boolean default true )
, member procedure solve
( p_verbose boolean default false )
, member function solved_cursor -- Results as ref cursor
return sys_refcursor
, constructor function sudoku
( p_rows sudoku_element_tt
, p_verbose boolean default false )
return self as result
, constructor function sudoku
( p_row1 varchar2 default ' '
, p_row2 varchar2 default ' '
, p_row3 varchar2 default ' '
, p_row4 varchar2 default ' '
, p_row5 varchar2 default ' '
, p_row6 varchar2 default ' '
, p_row7 varchar2 default ' '
, p_row8 varchar2 default ' '
, p_row9 varchar2 default ' '
, p_verbose boolean default false )
return self as result
) &PERSISTANCE
/
show errors type sudoku
prompt Type body sudoku:
create or replace type body sudoku
as
member procedure print
( p_gridlines boolean default true )
is
k_horizontal_rule constant varchar2(50) := '- ---------+-----------+----------';
begin
dbms_output.put_line(k_horizontal_rule);
for i in 1..9 loop
self.s_rows(i).print('Row ' || i);
if p_gridlines and i in (3,6) then
dbms_output.put_line(k_horizontal_rule);
end if;
end loop;
if p_gridlines then
dbms_output.put_line(k_horizontal_rule);
end if;
dbms_output.new_line();
end print;
-- Getter function for a single specified column:
member function s_columns
( p_col# integer )
return sudoku_element
is
begin
return new sudoku_element
( self.s_rows(1).cells(p_col#)
, self.s_rows(2).cells(p_col#)
, self.s_rows(3).cells(p_col#)
, self.s_rows(4).cells(p_col#)
, self.s_rows(5).cells(p_col#)
, self.s_rows(6).cells(p_col#)
, self.s_rows(7).cells(p_col#)
, self.s_rows(8).cells(p_col#)
, self.s_rows(9).cells(p_col#)
, false ); -- Don't re-validate
end s_columns;
-- Getter function for a single specified square:
member function s_squares
( p_square# integer )
return sudoku_element
is
k_startrow constant pls_integer := ceil(p_square#/3) * 3 -2;
k_startcol constant pls_integer := mod(p_square# -1,3) * 3 + 1;
begin
return new sudoku_element
( self.s_rows(k_startrow).cells(k_startcol)
, self.s_rows(k_startrow).cells(k_startcol +1)
, self.s_rows(k_startrow).cells(k_startcol +2)
, self.s_rows(k_startrow +1).cells(k_startcol)
, self.s_rows(k_startrow +1).cells(k_startcol +1)
, self.s_rows(k_startrow +1).cells(k_startcol +2)
, self.s_rows(k_startrow +2).cells(k_startcol)
, self.s_rows(k_startrow +2).cells(k_startcol +1)
, self.s_rows(k_startrow +2).cells(k_startcol +2)
, false ); -- Don't re-validate
end s_squares;
-- Approach is to find intersection of free lists for current row, column and square.
-- Row, column and square are sudoku_element objects, which have a free_values method,
-- Thus for each null cell we will look for
-- intersect(row.free_values, column.free_values, square.free_values) -- pseudo-code
-- and hope for a single value, i.e. candidates.count = 1.
member procedure solve
( p_verbose boolean default false )
is
sudoku_broken exception;
pragma exception_init(sudoku_broken, -20200);
procedure put_line ( p_text varchar2 ) is
begin
if p_verbose then dbms_output.put_line(p_text); end if;
end put_line;
procedure put ( p_text varchar2 ) is
begin
if p_verbose then dbms_output.put(p_text); end if;
end put;
procedure new_line is
begin
if p_verbose then dbms_output.new_line; end if;
end new_line;
-- Given two sudoku_element objects, return the set of common values:
-- Third set is optional
function intersection
( p_set1 sudoku_cell_tt
, p_set2 sudoku_cell_tt
, p_set3 sudoku_cell_tt default null )
return sudoku_cell_tt
is
v_result sudoku_cell_tt;
begin
if p_set1.count = 0 or p_set2.count = 0 then
v_result := sudoku_cell_tt();
else
v_result := (p_set1 multiset intersect p_set2);
end if;
if p_set3 is not null then
v_result := (v_result multiset intersect p_set3);
end if;
return v_result;
end intersection;
-- Determine which square a (row,column) coordinate falls in:
function which_square
( p_row# pls_integer
, p_col# pls_integer )
return pls_integer
is
begin
return ceil(p_col#/3) +
case
when p_row# <= 3 then 0
when p_row# <= 6 then 3
when p_row# <= 9 then 6
end;
-- Could also use:
-- ceil(p_col#/3) + ((ceil(p_row#/3) -1) *3)
-- but this is harder to read and I suspect less efficient (untested)
end which_square;
-- "Locations" check:
-- For a specified value and row, return check which cell(s) it can go in.
-- e.g. Looking at a particular cell, perhaps any of {2,3,5} could go in it. However, maybe 2 cannot go in the
-- row above because there is already a 2 in that row, etc. so in fact this cell is the only place for that 2.
-- Return true if the position specified is the only valid position for this value in the row.
function only_valid_location_in_row
( p_candidate pls_integer -- A candidate value to check e.g. 4
, p_position pls_integer -- A position in the row
, p_which_row pls_integer -- the row number, e.g. row 6
, p_row sudoku_element ) -- the row object itself
return boolean
is
v_locations sudoku_cell_tt := p_row.free_locations(); -- Possible locations within this row.
v_which_column pls_integer;
v_which_square pls_integer;
v_results sudoku_cell_tt := sudoku_cell_tt();
begin
if p_candidate is null then
-- Cheap shortcut simplifies validation - null in, null out:
return null;
elsif p_candidate not member of p_row.free_values then
-- Review how we want to handle this. Is it an error or something we can just skip?
raise_application_error
( -20000
, 'Value ' || p_candidate || ' is already in use within row ' || p_which_row );
elsif v_locations.count > 9 then
raise_application_error
( -20000
, 'valid_locations_in_row: value ' || p_candidate || ' has ' || v_locations.count || ' possible locations in row ' || p_which_row || '.' );
end if;
-- The specified row will have two or more unused values to place.
-- This procedure is passed one of those values as p_candidate.
-- Build up a collection of possible locations for it.
-- e.g. row is {4,2,1,null,9,7,6,8,null}, and p_candidate is 3.
-- Initially 3 could go in positions 4 or 9 (the two empty locations).
-- However, it is possible that column 4 already has the value 3, in which case it must go in column 9.
-- The corresponding square is checked in a similar way.
-- Loop through the row's empty locations, checking whether the candidate can go in each one:
<>
for l in v_locations.first..v_locations.last loop
v_which_column := v_locations(l); -- The current location to check
v_which_square := which_square(p_which_row,v_which_column);
-- See whether this value is also free within the column:
if p_candidate member of self.s_columns(v_which_column).free_values
and p_candidate member of self.s_squares(v_which_square).free_values
then
-- This is a possible location for this value:
-- [todo: break out of loop after finding second possible location. For now, confirm correct.]
-- v_locations_count := v_locations_count +1;
v_results.extend;
v_results(v_results.count) := v_which_column;
exit when v_results.count > 1;
end if;
end loop locations;
-- true if there is only one position and it is the specified one:
return v_results.count = 1 and p_position member of v_results;
end only_valid_location_in_row;
-- "Locations" check2:
-- For a specified value, position and column, see whether the specified posiition is the only place it can go.
function only_valid_location_in_column
( p_candidate pls_integer -- A candidate value to check e.g. 4
, p_position pls_integer -- A position in the row
, p_which_column pls_integer -- the column number, e.g. column 6
, p_column sudoku_element ) -- the column object itself
return boolean
is
v_locations sudoku_cell_tt := p_column.free_locations(); -- Possible locations within this column.
v_which_row pls_integer;
v_which_square pls_integer;
v_results sudoku_cell_tt := sudoku_cell_tt();
begin
if p_candidate is null then
-- Cheap shortcut simplifies validation - null in, null out:
return null;
elsif p_candidate not member of p_column.free_values then
-- Review how we want to handle this. Is it an error or something we can just skip?
raise_application_error
( -20000
, 'Value ' || p_candidate || ' is already in use within column ' || p_which_column );
elsif v_locations.count > 9 then
raise_application_error
( -20000
, 'valid_locations_in_row: value ' || p_candidate || ' has ' || v_locations.count || ' possible locations in row ' || p_which_column || '.');
end if;
-- Loop through the column's empty locations, checking whether the candidate can go in each one:
<>
for l in v_locations.first..v_locations.last loop
v_which_row := v_locations(l); -- The current location to check
v_which_square := which_square(v_which_row,p_which_column);
-- See whether this value is also free within the column:
if p_candidate member of self.s_rows(v_which_row).free_values
and p_candidate member of self.s_squares(v_which_square).free_values
then
-- This is a possible location for this value:
v_results.extend;
v_results(v_results.count) := v_which_row;
-- We are checking for the case where the value can only go in one position, so no point continuing if > 1:
exit when v_results.count > 1;
end if;
end loop locations;
-- true if there is only one position and it is the specified one:
return v_results.count = 1 and p_position member of v_results;
end only_valid_location_in_column;
-- "Locations" check2:
-- For a specified value and column, return the only cell(s) it can go in.
function valid_locations_in_column
( p_candidate pls_integer -- A candidate value to check e.g. 4
, p_which_column pls_integer -- the column number, e.g. column 6
, p_column sudoku_element ) -- the column object itself
return sudoku_cell_tt
is
v_locations sudoku_cell_tt := p_column.free_locations(); -- Possible locations within this column.
v_which_row pls_integer;
v_which_square pls_integer;
v_results sudoku_cell_tt := sudoku_cell_tt();
begin
if p_candidate is null then
-- Cheap shortcut simplifies validation - null in, null out:
return null;
elsif p_candidate not member of p_column.free_values then
-- Review how we want to handle this. Is it an error or something we can just skip?
raise_application_error
( -20000
, 'Value ' || p_candidate || ' is already in use within column ' || p_which_column );
elsif v_locations.count > 9 then
raise_application_error
( -20000
, 'valid_locations_in_row: value ' || p_candidate || ' has ' || v_locations.count || ' possible locations in row ' || p_which_column || '.' );
end if;
-- Loop through the column's empty locations, checking whether the candidate can go in each one:
<>
for l in v_locations.first..v_locations.last loop
v_which_row := v_locations(l); -- The current location to check
v_which_square := which_square(v_which_row,p_which_column);
-- See whether this value is also free within the column:
if p_candidate member of self.s_rows(v_which_row).free_values
and p_candidate member of self.s_squares(v_which_square).free_values
then
-- This is a possible location for this value:
v_results.extend;
v_results(v_results.count) := v_which_row;
-- We are checking for the case where the value can only go in one position, so no point continuing if > 1:
exit when v_results.count > 1;
end if;
end loop locations;
return v_results;
end valid_locations_in_column;
-- "Locations" check3:
-- For a specified value,position and square, see whether the specified posiition is the only place it can go.
function only_valid_location_in_square
( p_candidate pls_integer -- A candidate value to check e.g. 4
, p_position pls_integer -- A position in the row
, p_which_square pls_integer -- the column number, e.g. column 6
, p_square sudoku_element ) -- the column object itself
return boolean
is
v_locations sudoku_cell_tt := p_square.free_locations(); -- Possible locations within this column.
v_which_row pls_integer;
v_which_column pls_integer;
v_results sudoku_cell_tt := sudoku_cell_tt();
-- Offsets for starting loop over specified square
-- e.g. square 6 starts at row 4, column 7
-- (allow column offset to start at 1 instead of more logical 0 because easier for adding to
-- mod() expression that returns 0/1/2).
k_rowoffset constant pls_integer := ceil(p_which_square/3) * 3 -3;
k_column_offset constant pls_integer := mod(p_which_square -1,3) * 3 +1;
begin
if p_candidate is null then
-- Cheap shortcut simplifies validation - null in, null out:
return null;
elsif p_candidate not member of p_square.free_values then
-- Review how we want to handle this. Is it an error or something we can just skip?
raise_application_error
( -20000
, 'Value ' || p_candidate || ' is already in use within square ' || p_which_square );
elsif v_locations.count > 9 then
raise_application_error
( -20000
, 'valid_locations_in_square: value ' || p_candidate || ' has ' || v_locations.count || ' possible locations in square ' || p_which_square || '.' );
end if;
-- Loop through the column's empty locations, checking whether the candidate can go in each one:
<>
for l in v_locations.first..v_locations.last loop
-- Map location n of specified square to a row and column:
v_which_row := ceil(v_locations(l)/3) + k_rowoffset;
v_which_column := mod(v_locations(l) -1,3) + k_column_offset;
-- See whether this value is also free within the row and column:
-- (optimization possible - currently repeat each row and column lookup 3 times)
if p_candidate member of self.s_rows(v_which_row).free_values
and p_candidate member of self.s_columns(v_which_column).free_values
then
-- This is a possible location for this value:
v_results.extend;
v_results(v_results.count) := v_locations(l);
-- We are checking for the case where the value can only go in one position, so no point continuing if > 1:
exit when v_results.count > 1;
end if;
end loop locations;
-- true if there is only one position and it is the specified one:
return v_results.count = 1 and p_position member of v_results;
end only_valid_location_in_square;
-- For a given coordinate pair, find the set of possible values from the intersection of
-- row.free_values, column.free_values and square.free_values. If only one possible value, return it.
function unique_value
( p_row# pls_integer
, p_col# pls_integer
, p_square# pls_integer
, p_row sudoku_element
, p_column sudoku_element
, p_square sudoku_element )
return pls_integer
is
v_candidates sudoku_cell_tt;
v_locations sudoku_cell_tt;
v_result pls_integer;
v_position_in_square pls_integer := mod(p_row# -1,3) * 3 + mod(p_col# -1,3) + 1;
begin
v_candidates := intersection(p_row.free_values, p_column.free_values, p_square.free_values);
-- Relies on intersection returning consecutive non-null values
-- so "count = 1" means we want the first value, avoiding need for loop.
-- This would break if e.g. first value is null and count = 2.
if v_candidates.count = 0 then
-- This exception is handled by caller, which abandons current retry and moves on to next:
raise_application_error
( -20200
, 'Invalid sudoku: cell at row ' || p_row# || ' column ' || p_col# || ' has no possible values.');
elsif v_candidates.count = 1 then
put('Intsc: ');
v_result := v_candidates(v_candidates.first);
elsif v_candidates.count > 1 then
-- Compile with extended diagnostics using conditional compilation:
-- alter type sudoku compile body plsql_ccflags = 'extended_diagnostics:true' reuse settings;
-- or at session level:
-- alter session set plsql_ccflags = 'extended_diagnostics:true';
$if $$extended_diagnostics $then
-- See whether we can eliminate some more with Plan B (Possible Locations algorithm):
put('Row ' || p_row# || ' col ' || p_col# || ': ' || v_candidates.count || ' candidates:');
if p_verbose then -- Parameter to solve() procedure, default false
-- Dump out possible values for unresolved cells, if verbose specified:
for i in v_candidates.first..v_candidates.last loop
put(lpad(v_candidates(i),3));
end loop;
new_line();
end if;
$end
for i in v_candidates.first..v_candidates.last loop
-- Try each candidate to see whether all other locations can be eliminated:
if only_valid_location_in_row(v_candidates(i), p_col#, p_row#, p_row) then
put('Loc-R: ');
v_result := v_candidates(i);
elsif only_valid_location_in_column(v_candidates(i), p_row#, p_col#, p_column) then
put('Loc-C: ');
v_result := v_candidates(i);
else
/*
put
( 'only_valid_location_in_square: row ' || p_row# ||
', column ' || p_col# ||
', square ' || p_square# ||
', position ' || v_position_in_square ||
', value ' || v_candidates(i) || ': ' );
*/
if only_valid_location_in_square(v_candidates(i), v_position_in_square, p_square#, p_square) then
put('Loc-S: ');
v_result := v_candidates(i);
end if;
end if;
end loop;
end if;
return v_result;
end unique_value;
procedure solve_inner
( p_verbose boolean default false )
is
type per_iteration_stats_rectype is record
( checked pls_integer
, resolved pls_integer
, start_time timestamp
, end_time timestamp );
-- Table of stats, one row per iteration:
type stats_array is table of per_iteration_stats_rectype index by pls_integer;
v_stats stats_array;
v_found_value pls_integer;
v_sudoku_changed boolean := true;
v_sudoku_solved boolean := false;
v_square# pls_integer;
v_iteration pls_integer := 0;
begin
<>
while v_sudoku_changed -- Starts out true
and not v_sudoku_solved
and v_iteration <= 81 -- Emergency brake - handy during development
loop
v_sudoku_changed := false;
v_iteration := v_iteration +1;
v_stats(v_iteration).start_time := systimestamp;
v_stats(v_iteration).checked := 0;
v_stats(v_iteration).resolved := 0;
put_line('Iteration ' || v_iteration || ':');
<>
for rw in 1..9 loop
<>
for c in 1..9 loop
if self.s_rows(rw).cells(c) is null then
-- Keep count of number checked for stats:
v_stats(v_iteration).checked := v_stats(v_iteration).checked +1;
v_square# := which_square(rw,c);
-- Look for a value for this cell (function returns null if no unique value):
v_found_value :=
unique_value
( rw
, c
, v_square#
, self.s_rows(rw)
, self.s_columns(c)
, self.s_squares(v_square#) );
if v_found_value is not null then
self.s_rows(rw).set_cell(c,v_found_value);
v_stats(v_iteration).resolved := v_stats(v_iteration).resolved +1;
v_sudoku_changed := true;
put_line('Row ' || rw || ' col ' || c || ' set to ' || v_found_value);
end if;
end if;
end loop cols;
end loop rows;
-- Sudoku is solved if we resolved every unresolved cell this iteration:
v_sudoku_solved := v_stats(v_iteration).checked = v_stats(v_iteration).resolved;
put_line
( 'Checked ' || v_stats(v_iteration).checked ||
', resolved ' || v_stats(v_iteration).resolved || chr(10));
v_stats(v_iteration).end_time := systimestamp;
end loop deductions;
if v_sudoku_solved then
self.status := 'Solved';
else
self.status := 'Unsolved';
end if;
put_line(self.status || ' after ' || v_iteration || ' iterations.' || chr(10));
end solve_inner;
begin
declare
-- Local block to bring variable declarations nearer code:
v_candidates sudoku_cell_tt;
v_last_stable_sudoku sudoku;
v_square# pls_integer;
v_guesses pls_integer := 0;
v_candidate_count_orig pls_integer := 0;
v_what_if_restarts pls_integer := 0;
begin
dbms_application_info.set_module('Sudoku solver', 'Basic');
dbms_application_info.set_client_info(null);
new_line();
put_line('"Intsc" = derived via Intersection check (only one possible value for this cell)');
put_line('"Loc-R/C/S" = derived via possible-locations check (the value could not go anywhere else in its row/column/square)');
put_line('"Guess" = The guessing ("What If?") test eliminated all other values as they resulted in an invalid sudoku'
|| chr(10));
-- This *almost* always resolves the sudoku.
solve_inner(p_verbose);
dbms_application_info.set_action(self.status);
if self.status = 'Solved' then
dbms_application_info.set_client_info(null);
return;
else
dbms_application_info.set_action('Phase 2');
put_line('Best effort without guesswork:');
if p_verbose then
self.print();
end if;
end if;
v_last_stable_sudoku := self;
-- However, the above will abandon the attempt if every remaining blank cell could have
-- two or more values, so we now retry with each candidate value. We only guess one value at a time -
-- * If it leads to an invalid sudoku, it is wrong and can be eliminated. The sudoku reverts to its state
-- prior to the guess and the candidate is removed from the list of candidates for that cell.
-- * If it appears valid but fails to lead to a solution, it is backed out
-- This is apparently an official technique known as "What If", "Guess-and-Check", "Bifurcation", "Backtracking" or "Ariadne's thread"
-- http://en.wikipedia.org/wiki/Sudoku
-- This outermost loop does nothing except allowing the whole "what if" cycle to restart from a stable point
<>
while self.status != 'Solved' and v_what_if_restarts < 9 * 81 and v_guesses < 9 * 81 loop
v_what_if_restarts := v_what_if_restarts +1;
if p_verbose then
if v_what_if_restarts = 1 then
put_line(chr(10) || 'Starting what-if tests');
else
put_line(chr(10) || 'Restarting what-if tests (' || v_what_if_restarts || ')');
self.print();
end if;
end if;
<>
for rw in 1..9 loop
exit when self.status = 'Solved';
put_line(chr(10) || 'Loop "what_if", row ' || rw);
<>
for c in 1..9 loop
exit when self.status = 'Solved';
dbms_application_info.set_client_info('Row ' || rw);
if self.s_rows(rw).cells(c) is null then
put_line('Loop "what_if > cell", row ' || rw || ', column ' || c);
dbms_application_info.set_client_info
( 'Row ' || rw || ', cell ' || c || ', total guesses ' || v_guesses );
v_square# := which_square(rw,c);
$if $$extended_diagnostics $then
if p_verbose then
self.s_rows(rw).print('Row ' || rw, false);
-- self.s_columns(c).print('Column ' || c, false);
-- self.s_squares(v_square#).print('Square ' || v_square#, false);
declare
v_values sudoku_cell_tt := self.s_rows(rw).free_values;
begin
put('Free values for row ' || rw || ': ');
for j in v_values.first..v_values.last loop
begin
put(v_values(j) || ' ');
exception
when no_data_found then null;
end;
end loop;
put_line('');
end;
declare
v_values sudoku_cell_tt := self.s_columns(c).free_values;
begin
put('Free values for column ' || c || ': ');
for j in v_values.first..v_values.last loop
begin
put(v_values(j) || ' ');
exception
when no_data_found then null;
end;
end loop;
put_line('');
end;
declare
v_values sudoku_cell_tt := self.s_squares(v_square#).free_values;
begin
put('Free values for square ' || v_square# || ': ');
for j in v_values.first..v_values.last loop
begin
put(v_values(j) || ' ');
exception
when no_data_found then null;
end;
end loop;
put_line('');
end;
end if;
$end
v_candidates :=
intersection
( self.s_rows(rw).free_values
, self.s_columns(c).free_values
, self.s_squares(v_square#).free_values );
v_candidate_count_orig := v_candidates.count;
if v_candidates.count = 0 then
-- Should never happen :)
-- Something must have gone wrong, because the intersection check above found no possible values
-- for this cell. Either the sudoku is invalid or we made a wrong guess earlier.
-- Revert to last stable version and quit this cell.
put_line('Abandoning guess ' || v_guesses || ' at row ' || rw || ', column ' || c || '. Restoring last stable version.');
self := v_last_stable_sudoku;
if p_verbose then
self.print();
new_line();
end if;
exit cell;
else
<>
for i in v_candidates.first..v_candidates.last loop
exit when self.status = 'Solved';
put_line('Restoring last stable version');
-- self.s_rows := v_last_stable_sudoku.s_rows;
self := v_last_stable_sudoku;
if p_verbose then
self.print();
end if;
v_guesses := v_guesses +1;
-- Set current cell to the next possible value and retry solve_inner().
put ( chr(10) ||
'Guess ' || v_guesses ||
': row ' || rw ||
' col ' || c ||
', trying ' || v_candidates(i) ||
' (#' || (i + v_candidates.count - v_candidate_count_orig) || -- Adjust for changed count
' of ' || v_candidates.count || ' possible values {');
-- Diagnostic message listing remaining candidates:
for j in v_candidates.first..v_candidates.last loop
begin
put(v_candidates(j) || case j when v_candidates.last then '}' else ',' end);
exception
when no_data_found then null; -- May have been eliminated
end;
end loop;
put_line(' )');
self.s_rows(rw).set_cell(c,v_candidates(i));
-- We set a cell to one of its possible values - now see whether that helped:
begin
-- If the current test values are invalid, solve_inner() will fail and raise
-- exception sudoku_broken, and we undo it and continue with the next text value:
solve_inner(p_verbose);
-- If still unsolved after call to main solver, revert to state before current guess:
if self.status = 'Solved' then
put_line
( chr(10) ||
'Guess ' || v_guesses || ' successful' ||
' (value "' || v_candidates(i) ||
'" in row ' || rw ||
', col ' || c || ')' );
end if;
exception
-- If the guess was wrong, some part of the sudoku will not add up,
-- so undo this change and continue on to next guess until one does not fail:
when sudoku_broken then
-- If this guess resulted in an invalid sudoku, we can eliminate this candidate.
put_line(sqlerrm);
put_line
( 'Sudoku was invalid with row ' || rw || ', col ' || c ||
' = ' || v_candidates(i) || ': eliminating as candidate.' );
-- This candidate value cannot go in this cell. Maybe that only leaves one value?
v_candidates.delete(i);
if v_candidates.count = 1 then
-- This is the only value left - assuming sudoku is valid, it must be correct:
self := v_last_stable_sudoku;
self.s_rows(rw).set_cell(c,v_candidates(v_candidates.first));
v_last_stable_sudoku := self;
put_line('Elimination only left value '|| v_candidates(v_candidates.first));
-- self.s_rows(rw).print('Row ' || rw || ' now:', false);
put_line('Saved this version');
put('Guess: ');
put_line('Row ' || rw || ' col ' || c || ' set to ' || v_candidates(v_candidates.first));
-- Restart entire what-if cycle with updated sudoku:
exit what_if;
else
put_line(v_candidates.count || ' candidates remain for row ' || rw || ', col ' || c);
end if;
end;
end loop candidate;
end if; -- if there are any candidates for cell c
end if; -- if the cell is null
end loop cell;
end loop what_if;
end loop what_if_restarts;
end;
end solve;
member function solved_cursor -- Results as ref cursor
return sys_refcursor
is
c_results sys_refcursor;
begin
open c_results for
select min(decode(cell#,1,c)) as col1
, min(decode(cell#,2,c)) as col2
, min(decode(cell#,3,c)) as col3
, min(decode(cell#,4,c)) as col4
, min(decode(cell#,5,c)) as col5
, min(decode(cell#,6,c)) as col6
, min(decode(cell#,7,c)) as col7
, min(decode(cell#,8,c)) as col8
, min(decode(cell#,9,c)) as col9
from ( -- 9i seems to need cast with union
select 1 as row#, rownum as cell#, r.column_value as c from table(cast(self.s_rows(1).cells as sudoku_cell_tt)) r
union all
select 2, rownum, r.column_value from table(cast(self.s_rows(2).cells as sudoku_cell_tt)) r
union all
select 3, rownum, r.column_value from table(cast(self.s_rows(3).cells as sudoku_cell_tt)) r
union all
select 4, rownum, r.column_value from table(cast(self.s_rows(4).cells as sudoku_cell_tt)) r
union all
select 5, rownum, r.column_value from table(cast(self.s_rows(5).cells as sudoku_cell_tt)) r
union all
select 6, rownum, r.column_value from table(cast(self.s_rows(6).cells as sudoku_cell_tt)) r
union all
select 7, rownum, r.column_value from table(cast(self.s_rows(7).cells as sudoku_cell_tt)) r
union all
select 8, rownum, r.column_value from table(cast(self.s_rows(8).cells as sudoku_cell_tt)) r
union all
select 9, rownum, r.column_value from table(cast(self.s_rows(9).cells as sudoku_cell_tt)) r
)
group by row#;
return c_results;
end solved_cursor;
constructor function sudoku
( p_row1 varchar2 default ' '
, p_row2 varchar2 default ' '
, p_row3 varchar2 default ' '
, p_row4 varchar2 default ' '
, p_row5 varchar2 default ' '
, p_row6 varchar2 default ' '
, p_row7 varchar2 default ' '
, p_row8 varchar2 default ' '
, p_row9 varchar2 default ' '
, p_verbose boolean default false )
return self as result
is
begin
self.s_rows := new sudoku_element_tt();
self.s_rows.extend(9);
self.s_rows(1) := sudoku_element(p_row1);
self.s_rows(2) := sudoku_element(p_row2);
self.s_rows(3) := sudoku_element(p_row3);
self.s_rows(4) := sudoku_element(p_row4);
self.s_rows(5) := sudoku_element(p_row5);
self.s_rows(6) := sudoku_element(p_row6);
self.s_rows(7) := sudoku_element(p_row7);
self.s_rows(8) := sudoku_element(p_row8);
self.s_rows(9) := sudoku_element(p_row9);
-- Invoke main constructor (diagnotic messages, solve() etc):
self := new sudoku(self.s_rows, p_verbose);
return;
end sudoku;
constructor function sudoku
( p_rows sudoku_element_tt
, p_verbose boolean default false )
return self as result
is
begin
self.status := 'New';
self.s_rows := p_rows;
if p_verbose then
$if $$extended_diagnostics $then
dbms_output.put_line('Toggle extended diagnostics using conditional compilation:');
dbms_output.put_line(q'|alter type sudoku compile body plsql_ccflags = 'extended_diagnostics:false' reuse settings;|');
dbms_output.put_line('or at session level:');
dbms_output.put_line(q'|alter session set plsql_ccflags = 'extended_diagnostics:false';|' || chr(10));
$else
dbms_output.put_line('Toggle extended diagnostics using conditional compilation:');
dbms_output.put_line(q'|alter type sudoku compile body plsql_ccflags = 'extended_diagnostics:true' reuse settings;|');
dbms_output.put_line('or at session level:');
dbms_output.put_line(q'|alter session set plsql_ccflags = 'extended_diagnostics:true';|' || chr(10));
$end
end if;
dbms_output.put_line('Before:');
self.print();
self.solve(p_verbose);
dbms_output.put_line('After:');
self.print();
dbms_output.put_line(self.status);
return;
end sudoku;
end;
/
show errors type body sudoku
set serveroutput on size 1000000
set serveroutput on size unlimited
set timing on
prompt Native compilation:
begin
for r in (
select o.object_name
from user_objects o
where o.object_name like 'SUDOKU%'
--and o.object_type = 'TYPE BODY'
)
loop
execute immediate 'alter type '||r.object_name||' compile plsql_code_type=native';
end loop;
end;
/
--exec dbms_output.enable(null)
prompt
prompt db-innovations '#3: pencil mark cross-hatching' example
declare
v_sudoku sudoku :=
new sudoku
( sudoku_element_tt
( sudoku_element(' 7 25 ')
, sudoku_element(' 8 792 6 ')
, sudoku_element(' 6 51 7')
, sudoku_element(' 31 ')
, sudoku_element(' 7 2 6 ')
, sudoku_element(' 48 ')
, sudoku_element('7 6391 ')
, sudoku_element('631548792')
, sudoku_element('948217536') )
, false
);
begin
null;
end;
/
declare
v_row sudoku_element;
begin
-- Test validation of a single element containing duplicates:
v_row := new sudoku_element(1,2,3,4,4,6,7,8,9);
v_row.check_valid;
v_row.print;
end;
.
-- Default sudoku_element constructor syntax
declare
v_sudoku sudoku :=
new sudoku
( sudoku_element_tt
( sudoku_element(null,null,null,6, 1, 3, 4, null,null)
, sudoku_element(8, 4, null,null,2, null,3, null,null)
, sudoku_element(5, 6, null,null,null,null,9, null,null)
, sudoku_element(null,null,null,3, null,null,8, 5, 9 )
, sudoku_element(6, null,null,1, null,4, null,null,3 )
, sudoku_element(3, 7, 5, null,null,2, null,null,null)
, sudoku_element(null,null,8, null,null,null,null,7, 1 )
, sudoku_element(null,null,6, null,9, null,null,3, 8 )
, sudoku_element(null,null,2, 8, 3, 6, null,null,null))
);
begin
null;
end;
.
declare
v_sudoku sudoku :=
new sudoku
( sudoku_element_tt
( sudoku_element(2, 5, null,null,null,null,3, null,null)
, sudoku_element(null,3, null,null,null,null,null,7, null)
, sudoku_element(4, null,7, null,null,6, 2, null,null)
, sudoku_element(1, 2, 8, null,3, null,null,null,6 )
, sudoku_element(9, 6, null,null,null,null,null,null,7 )
, sudoku_element(null,null,null,null,8, 9, null,4, 2 )
, sudoku_element(null,null,9, null,2, 1, 4, null,null)
, sudoku_element(5, null,null,8, null,3, 7, 9, null)
, sudoku_element(null,null,null,4, null,null,null,null,null))
);
begin
null;
end;
.
declare
v_sudoku sudoku :=
new sudoku
( sudoku_element_tt
( sudoku_element(2, null,null,null,1, 9, null,4, null)
, sudoku_element(null,8, null,null,null,null,1, 7, null)
, sudoku_element(null,7, null,null,8, 6, 5, null,null)
, sudoku_element(1, null,null,8, null,2, null,null,7 )
, sudoku_element(5, null,3, null,null,null,6, null,4 )
, sudoku_element(8, null,null,4, null,3, null,null,2 )
, sudoku_element(null,null,8, 2, 7, null,null,6, null)
, sudoku_element(null,5, 4, null,null,null,null,9, null)
, sudoku_element(null,1, null,9, 4, null,null,null,8 ))
);
begin
null;
end;
.
set autoprint on
var results refcursor
prompt Test ref cursor output:
prompt (also simplified sudoku_element text input)
declare
v_sudoku sudoku := new sudoku
( '8 9 6 '
, '4 2 7 '
, ' 1 6 4 '
, ' 8 25 '
, '93 1 82'
, ' 23 9 '
, ' 1 7 5 '
, ' 6 3 7'
, ' 8 1 6'
, true );
begin
:results := v_sudoku.solved_cursor;
end;
/
prompt Tony Andrews test case:
prompt http://tonyandrews.blogspot.com/2006/01/plsql-so-doku-solver.html
prompt (also simplified text input)
declare
v_sudoku sudoku := new sudoku
( ' 6 1 4 5 '
, ' 83 56 '
, '2 1'
, '8 4 7 6'
, ' 6 3 '
, '7 9 1 4'
, '5 2'
, ' 72 69 '
, ' 4 5 8 7 '
, true );
begin
null;
end;
/
prompt Test sql interface:
select new sudoku
( ' 6 1 4 5 '
, ' 83 56 '
, '2 1'
, '8 4 7 6'
, ' 6 3 '
, '7 9 1 4'
, '5 2'
, ' 72 69 '
, ' 4 5 8 7 ') as new_sudoku
from dual;
prompt
prompt Wikipedia Sudoku example
prompt http://en.wikipedia.org/wiki/Sudoku
declare
v_sudoku sudoku := new sudoku
( '53 7 '
, '6 195 '
, ' 98 6 '
, '8 6 3'
, '4 8 3 1'
, '7 2 6'
, ' 6 28 '
, ' 419 5'
, ' 8 79'
, false -- "verbose": set to true for diagnostic output messages
);
begin
null;
end;
/
prompt
prompt Bill Magee test:
prompt http://www.billmagee.co.uk/oracle/sudoku/index.html
declare
v_sudoku sudoku := new sudoku
( ' 9 15 '
, '42 8'
, ' 1 9 2'
, ' 5 6 9 '
, ' 8 5 '
, ' 7 3 5 '
, '6 2 3 '
, '3 64'
, ' 52 1 '
, true -- "verbose": set to true for diagnostic output messages
);
begin
null;
end;
.
r
prompt
prompt From "Extra Challenging (Very Hard) Print and Solve Sudoku Puzzles 01-04"
prompt http://puzzles.about.com/library/sudoku/qprsudokux01.htm
declare
v_sudoku sudoku := new sudoku
( ' 2 7'
, ' 7 4 1 '
, '9 5 '
, ' 8 63 2'
, '7 1'
, '2 18 6 '
, ' 4 9'
, ' 3 1 2 '
, '4 8 '
, false -- "verbose": set to true for diagnostic output messages
);
begin
null;
end;
.
r
prompt
prompt Metro 2007-04-05, difficulty rating ***(--)
declare
v_sudoku sudoku := new sudoku
( ' 3 6'
, ' 914 '
, ' 9 '
, ' 32 7 '
, '5 7 8 9'
, '48 '
, '84 5 '
, ' 6 1 '
, '1 87 '
, false -- "verbose": set to true for diagnostic output messages
);
begin
null;
end;
.
r
prompt One for Chris:
declare
v_sudoku sudoku := new sudoku
( ' 3 2 '
, ' 175 286 '
, '2 4 6 3'
, '5 9 4'
, ' 2 1 '
, ' 8 7 '
, ' 9 5 '
, ' 163 '
, ' 7 '
, false
);
begin
null;
end;
.
prompt
prompt Metro 2007-04-20
declare
v_sudoku sudoku := new sudoku
( ' 5 1 8 '
, '5 4 7 '
, ' 9 65 '
, ' 48 5 '
, ' 9 1 '
, ' 8 37 '
, ' 26 9 '
, ' 7 2 4 3'
, ' 1 3 '
, false -- "verbose": set to true for diagnostic output messages
);
begin
null;
end;
.
r
prompt
prompt "Tough Sudoku "
prompt http://sudoku.com.au/sudokutips.aspx?Go=H1-9-1999
declare
v_sudoku sudoku := new sudoku
( ' 34 '
, ' 67 9'
, '82 '
, '3 9 8 '
, ' 1 6 '
, ' 4 5 2'
, ' 61'
, '6 57 '
, ' 38 '
, false -- "verbose": set to true for diagnostic output messages
);
begin
null;
end;
.
r
prompt Requires one "what-if" iteration:
prompt Row 1 col 1 = 1 (1 of 2 possible values {1,8})
declare
v_sudoku sudoku := new sudoku
( ' 7 29563 '
, ' 8 9 '
, '6 9 4 '
, ' 5 94 '
, '49 56'
, ' 1 4 '
, ' 523 8'
, ' 2 3 '
, ' 3 9 1 2 '
, true
);
begin
null;
end;
.
r
prompt
prompt db-innovations 'Times Grand Final Ultra-Fiendish' example
prompt (Cannot currently solve - not attempting)
declare
v_sudoku sudoku := new sudoku
( ' 38 2'
, ' 4 2 5 '
, ' 619 '
, ' 9 2 '
, ' 8 '
, '4 2 1 '
, ' 8 '
, ' 9 3 8 '
, '1 92 '
, false
);
begin
null;
end;
.
l
prompt
prompt Toggle extended diagnostics using conditional compilation:
prompt alter type sudoku compile body plsql_ccflags = 'extended_diagnostics:true' reuse settings;
prompt
prompt or at session level:
prompt alter session set plsql_ccflags = 'extended_diagnostics:true';
prompt
|