-- PL/SQL Sudoku Solver (Oracle 10g) -- William Robertson 2007, www.williamrobertson.net -- Improved version incorporating additional cross-hatching algorithm. -- Used new 10g collection operator MEMBER OF as it simplifies coding (otherwise would have -- to code additional loops to test each element in collection looking for match with value). -- Allow optional parameter set feed off col 1 new_value 1 SELECT NULL AS "1" FROM dual WHERE 1=2; -- "&1" now has value passed on command line, or null DECLARE PROCEDURE drop_type (p_object_name VARCHAR2) IS -- Drop type, handling exception: -- ORA-04043: object xx does not exist no_such_type EXCEPTION; PRAGMA EXCEPTION_INIT(no_such_type, -4043); BEGIN EXECUTE IMMEDIATE 'DROP TYPE ' || p_object_name || ' FORCE'; DBMS_OUTPUT.PUT_LINE('Type ' || p_object_name || ' dropped.'); EXCEPTION WHEN no_such_type THEN DBMS_OUTPUT.PUT_LINE('Type ' || p_object_name || ' not found.'); END drop_type; BEGIN IF UPPER('&1') = 'REBUILD' THEN drop_type('sudoku'); drop_type('sudoku_element_tt'); drop_type('sudoku_element'); drop_type('sudoku_cell_tt'); ELSE DBMS_OUTPUT.PUT_LINE ( 'Specify REBUILD on command line to drop sudoku types before attempting to create them.' ); DBMS_OUTPUT.NEW_LINE(); END IF; END; / set feed 1 -- Originally made SUDOKU_CELL_TT a VARRAY because it made sense to limit it to nine values, -- however the 10g multiset operators (MEMBER OF, MULTISET EXCEPT etc) only work on nested table collections, -- and SUDOKU_ELEMENT contains validation that prevents more values than this being supplied anyway, so I -- decided a nested table collection type was better in this case. -- -- CREATE OR REPLACE TYPE sudoku_cell_tt AS VARRAY(9) OF NUMBER(1) CREATE OR REPLACE TYPE sudoku_cell_tt AS TABLE OF NUMBER(1) / 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 ) / 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 -- Handy 10g collection member uniqueness check: -- (actually doesn't appear to help performance as I hoped it would) 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 -- (In 10g we can replace procedural loops with MULTISET EXCEPT x y, where x is the full set 1-9 and y is self.cells) MEMBER FUNCTION free_values RETURN sudoku_cell_tt IS -- Start with the whole set, then remove those in use -- v_free sudoku_cell_tt := sudoku_cell_tt(1,2,3,4,5,6,7,8,9); -- n PLS_INTEGER := 1; BEGIN -- MS operator 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; / 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 ); / 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. Simple. -- 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 ); -- NB 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 PROMPT "set serveroutput ON size unlimited" requires SQL*Plus 10g: set serveroutput on size 1000000 set serveroutput on size unlimited set timing on 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 (new simple text input is available in version 4) 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; -- pre-10g SQL*Plus only (DBMS_OUTPUT processing used not to be invoked following SQL calls): exec null 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 -- Could not solve with mk2 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; . r -- The Metro example below is particularly hard: also tested with Tony Andrews solution (could not solve either): -- (See Tony's blog for CELL_PKG etc) begin cell_pkg.solve( ' 5 1 8 5 4 7 9 65 48 5 9 1 8 37 26 9 7 2 4 3 1 3 '); end; . -- ...and the Bill Magee sudoku solver: BEGIN SUDOKU_PKG.SOLVE ( ' 5 1 8 ' , '5 4 7 ' , ' 9 65 ' , ' 48 5 ' , ' 9 1 ' , ' 8 37 ' , ' 26 9 ' , ' 7 2 4 3' , ' 1 3 ' ); END; . SELECT c1,c2,c3,c4,c5,c6,c7,c8,c9 FROM sudoku_layup ORDER BY y PROMPT PROMPT Metro 2007-04-20 PROMPT (not solveable with mk3, solved with mk4) 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 PROMPT (not solveable with mk3, solved with mk4) 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 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