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