-- PL/SQL Soduku Solver (Oracle 9.2)
-- William Robertson 2006, www.williamrobertson.net

SET serveroutput ON size 1000000 format TRUNCATED

-- set term off

-- DROP TYPE sudoku;
-- DROP TYPE sudoku_element_tt;
-- DROP TYPE sudoku_element FORCE;
-- DROP TYPE sudoku_cell_tt;

CREATE OR REPLACE TYPE sudoku_cell_tt AS VARRAY(9) 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")
	( p_label VARCHAR2 DEFAULT NULL )
, MEMBER PROCEDURE set_cell
	( p_position POSITIVE
	, p_value POSITIVE )
, MEMBER FUNCTION free_list     -- Returns the set of missing numbers for a set
	RETURN sudoku_cell_tt
, MEMBER PROCEDURE print
	( p_name VARCHAR2 DEFAULT NULL )  -- Optional label
, 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 )
	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

-- 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 Body SUDOKU_ELEMENT:
CREATE OR REPLACE TYPE BODY sudoku_element
AS
	MEMBER PROCEDURE check_valid
		( p_label VARCHAR2 DEFAULT NULL )  -- Label for use in error message e.g. "Column 5"
	IS
		v_available sudoku_cell_tt := NEW sudoku_cell_tt(NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL);
	BEGIN
		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.');
			ELSE
				v_available(self.cells(i)) := self.cells(i);  -- Placeholder: this slot now taken
			END IF;
		END LOOP;
	END check_valid;


	MEMBER PROCEDURE set_cell
		( p_position POSITIVE
		, p_value POSITIVE )
	IS
	BEGIN
		self.cells(p_position) := p_value;
		check_valid;
	END set_cell;


	-- Values not in self.cells
	-- (in 10g this would be MULTISET EXCEPT x y, where x is the full set 1-9 and y is self.cells)
	MEMBER FUNCTION free_list
		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
		FOR i IN 1..9 LOOP
			IF self.cells(i) IS NOT NULL THEN  -- See if a value is held in element i
				v_free(self.cells(i)) := NULL;
			END IF;
		END LOOP;

		RETURN v_free;
	END free_list;


	/*
	-- Return a VARRAY version of [self] object:
	MEMBER FUNCTION to_table
		RETURN sudoku_cell_tt
	IS
		v_set sudoku_cell_tt := sudoku_cell_tt();  -- Starts out empty
		v_set_ix PLS_INTEGER := 0;
	BEGIN
		FOR i IN 1..9 LOOP
			IF self.cells(i) IS NOT NULL THEN
				v_set.EXTEND;
				v_set_ix := v_set_ix +1;
				v_set(v_set_ix) := self.cells(i);
			END IF;
		END LOOP;

		RETURN v_set;
	END to_table;
	*/


	MEMBER PROCEDURE print
		( p_name VARCHAR2 DEFAULT NULL )  -- Optional label
	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));
		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 )
		RETURN SELF AS RESULT
	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);

		check_valid();
		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;
/
set term on

show errors type body sudoku_element

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(6)            -- 'New'|'Solved'|'Failed'
, MEMBER PROCEDURE print
, 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
);
/

show errors type sudoku

PROMPT Type body SUDOKU:
CREATE OR REPLACE TYPE BODY sudoku
AS
	MEMBER PROCEDURE print
	IS
	BEGIN
		FOR i IN 1..9 LOOP
			self.s_rows(i).print('Row ' || i);
		END LOOP;
		DBMS_OUTPUT.NEW_LINE();
	END print;

	-- 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_LIST method,
	-- Thus for each null cell we will look for
	-- INTERSECT(row.free_list, column.free_list, square.free_list)  -- pseudo-code
	-- and hope for a single value, i.e. candidates.COUNT = 1.
	MEMBER PROCEDURE solve
		( p_verbose BOOLEAN DEFAULT FALSE )
	IS
		-- Dummy null sudoku_element with short name:
		nada CONSTANT SUDOKU_ELEMENT := SUDOKU_ELEMENT();

		-- Reminder: sudoku_element_tt is a varray of sudoku_cell_tts, i.e. 9 columns of 9 elements each:
		v_columns  SUDOKU_ELEMENT_TT := SUDOKU_ELEMENT_TT(nada,nada,nada,nada,nada,nada,nada,nada,nada);
		v_squares  SUDOKU_ELEMENT_TT := SUDOKU_ELEMENT_TT(nada,nada,nada,nada,nada,nada,nada,nada,nada);

		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:
		-- (In 10g this would be MULTISET INTERSECT, except the one below rather cleverly accepts 3 sets)
		-- Third set is optional
		FUNCTION multiset_intersect
			( 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 := sudoku_cell_tt();
		BEGIN
			IF p_set1.COUNT > 0 AND p_set2.COUNT > 0 THEN

				FOR i IN p_set1.FIRST..p_set1.LAST LOOP
					IF p_set1(i) IS NOT NULL THEN
						FOR j IN p_set2.FIRST..p_set2.LAST LOOP
							IF p_set2(j) = p_set1(i) THEN
								v_result.EXTEND;
								v_result(v_result.COUNT) := p_set1(i);
								EXIT;
							END IF;
						END LOOP;
					END IF;
				END LOOP;

			END IF;

			-- Repeat for third set, if populated:
			IF p_set3 IS NOT NULL AND v_result IS NOT NULL
			THEN
				v_result := multiset_intersect(p_set3,v_result);
			END IF;

			RETURN v_result;
		END multiset_intersect;


		-- Determine which square a (row,column) coordinate falls in:
		FUNCTION which_square
			( p_row# PLS_INTEGER
			, p_col# PLS_INTEGER )
			RETURN PLS_INTEGER
		IS
			v_intersect SUDOKU_CELL_TT;
			v_result PLS_INTEGER;
		BEGIN
			-- A row limits result to one of three possible squares, and so does a column:
			-- use handy intersect function above to find square which is in both sets.
			v_intersect :=
				multiset_intersect (
				CASE
					WHEN p_row# <= 3 THEN sudoku_cell_tt(1,2,3)
					WHEN p_row# <= 6 THEN sudoku_cell_tt(4,5,6)
					ELSE sudoku_cell_tt(7,8,9)
				END,
				CASE
					WHEN p_col# <= 3 THEN sudoku_cell_tt(1,4,7)
					WHEN p_col# <= 6 THEN sudoku_cell_tt(2,5,8)
					ELSE sudoku_cell_tt(3,6,9)
				END );

			-- multiset_intersect function returned a sudoku_cell_tt collection with 1 non-null value:
			-- Find it by checking each value (possibly this can be simplified):
			FOR i IN v_intersect.FIRST..v_intersect.LAST LOOP
				IF v_intersect(i) IS NOT NULL THEN
					v_result := v_intersect(i);
					EXIT;
				END IF;
			END LOOP;

			RETURN v_result;
		END which_square;


		-- Derive values of a column from a set of rows (self.s_rows):
		-- (possibly this belongs in a "sudoku_column" subtype, but I'm not going there)
		PROCEDURE sync_column
			( p_column IN OUT NOCOPY SUDOKU_ELEMENT
			, p_which_column IN PLS_INTEGER )
		IS
		BEGIN
			FOR i IN 1..9 LOOP
				p_column.cells(i) := self.s_rows(i).cells(p_which_column);
			END LOOP;

			p_column.check_valid('Column ' || p_which_column);
		END sync_column;


		-- Derive values of a square from a set of rows (self.s_rows):
		PROCEDURE sync_square
			( p_square IN OUT NOCOPY SUDOKU_ELEMENT  -- A square to populate via OUT param
			, p_which_square IN PLS_INTEGER )        -- Which square in sudoku (1-9)
		IS
			v_row# PLS_INTEGER;
			v_col# PLS_INTEGER;
		BEGIN
			FOR i IN 1..9 LOOP
				-- Transform square#:element# into row#:column# using maths (brain now hurts):
				v_row# := CEIL(i/3) + FLOOR(p_which_square/3 -.1) * 3;
				v_col# := MOD(i -1,3) + 1 + MOD(p_which_square -1,3) * 3;

				p_square.cells(i) := self.s_rows(v_row#).cells(v_col#);
			END LOOP;

			p_square.check_valid('Square ' || p_which_square);
		END sync_square;


		-- Apologies in advance for nesting frenzy. Many of the following procedures would
		-- ideally be private to the type body, but there is currently no such thing:
		PROCEDURE solve_inner
			( p_columns IN OUT NOCOPY SUDOKU_ELEMENT_TT
			, p_squares IN OUT NOCOPY SUDOKU_ELEMENT_TT
			, 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;


			-- For a given coordinate pair, find the set of possible values from the intersection of
			-- row.free_list, column.free_list and square.free_list. If only one possible value, return it.
			FUNCTION unique_value
				( p_row# PLS_INTEGER
				, p_col# PLS_INTEGER
				, p_square# PLS_INTEGER
				, p_rows SUDOKU_ELEMENT_TT
				, p_columns SUDOKU_ELEMENT_TT
				, p_squares SUDOKU_ELEMENT_TT )
				RETURN PLS_INTEGER
			IS
				v_candidates SUDOKU_CELL_TT;
				v_result PLS_INTEGER;
			BEGIN
				v_candidates :=
					multiset_intersect
					( p_rows(p_row#).free_list
					, p_columns(p_col#).free_list
					, p_squares(p_square#).free_list );

				-- NB relies on multiset_intersect 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
					v_result := v_candidates(v_candidates.FIRST);

				ELSIF v_candidates.COUNT > 1
				AND p_verbose  -- Parameter to SOLVE() procedure, default false
				THEN
					-- Dump out possible values for unresolved cells, if verbose specified:
					PUT('Row ' || p_row# || ' col ' || p_col# || ': ' || v_candidates.COUNT || ' candidates:');
					FOR i IN v_candidates.FIRST..v_candidates.LAST LOOP
						PUT(LPAD(v_candidates(i),3));
					END LOOP;
					NEW_LINE();
				END IF;

				RETURN v_result;
			END unique_value;

		BEGIN
			FOR i IN 1..9 LOOP
				sync_column(p_columns(i), i);
				sync_square(p_squares(i), i);
			END LOOP;

			WHILE v_sudoku_changed  -- Starts out true
			LOOP
				v_sudoku_changed := FALSE;

				v_iteration := v_iteration +1;
				EXIT WHEN v_iteration >= 80;  -- Emergency brake, was handy during development

				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, p_columns, p_squares);

							IF v_found_value IS NOT NULL THEN
								self.s_rows(rw).set_cell(c,v_found_value);
								sync_column(p_columns(c), c);
								sync_square(p_squares(v_square#), v_square#);

								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;
				END LOOP;

				-- 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;

			IF v_sudoku_solved THEN
				self.status := 'Solved';
			ELSE
				self.status := 'Failed';
			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_backup_sudoku SUDOKU;
			v_square# PLS_INTEGER;
			v_retries PLS_INTEGER := 0;
		BEGIN
			-- This *almost* always resolves the sudoku.
			solve_inner(v_columns,v_squares,p_verbose);
			v_backup_sudoku := self;

			-- However, the above will abandon the attempt if every remaining blank cell could have
			-- two or more values, so we have to retry with each possible value:
			<<all_retries>>
			WHILE self.status = 'Failed' LOOP
				<<try_each_ambiguous>>
				FOR rw IN 1..9 LOOP
					FOR c IN 1..9 LOOP
						IF self.s_rows(rw).cells(c) IS NULL THEN
							v_square# := which_square(rw,c);

							v_candidates :=
								multiset_intersect
								( self.s_rows(rw).free_list
								, v_columns(c).free_list
								, v_squares(v_square#).free_list );

							IF v_candidates.COUNT = 0 THEN
								-- Sadly we appear to have gone down a blind alley, because it turns out
								-- there are no possible values for this cell. Either the sudoku is invalid
								-- or we made a wrong guess earlier and it's too bloody hard to go back now:
								EXIT all_retries;
							END IF;

							FOR i IN v_candidates.FIRST..v_candidates.LAST LOOP
								-- Set current cell to the next possible value and retry solve_inner():

								v_retries := v_retries +1;

								PUT ( CHR(10) ||
								'Retry ' || v_retries ||
								': row ' || rw ||
								', col ' || c ||
								', trying ' || v_candidates(i) ||
								' (#' || i || ' of ' || v_candidates.COUNT || ' possible values {');

								FOR j IN v_candidates.FIRST..v_candidates.LAST LOOP
									PUT(v_candidates(j) || CASE j WHEN v_candidates.LAST THEN '}' ELSE ',' END);
								END LOOP;
								PUT_LINE(' )');

								self.s_rows(rw).cells(c) := v_candidates(i);
								sync_column(v_columns(c), c);
								sync_square(v_squares(v_square#), v_square#);

								-- We set a cell to one of its possible values - now see whether that helped:
								BEGIN
									solve_inner(v_columns,v_squares,p_verbose);

									PUT_LINE('Status after retry #' || v_retries || ': ' || self.status);

									IF self.status = 'Failed' THEN
										-- Failed to solve it this time around, but no exception raised so
										-- it is still valid - save the current state before continuing:
										v_backup_sudoku := self;
									END IF;

									-- Restart the loop:
									EXIT try_each_ambiguous;
								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
										-- Undo that attempt, because evidently it sucked:
										self := v_backup_sudoku;
										PUT_LINE
										( 'Sudoku was not solvable with row ' || rw || ', col ' || c ||
										' = ' || v_candidates(i) );
								END;
							END LOOP;
						END IF;
					END LOOP;
				END LOOP try_each_ambiguous;
			END LOOP all_retries;
		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_rows SUDOKU_ELEMENT_TT
		, p_verbose BOOLEAN DEFAULT FALSE )
		RETURN SELF AS RESULT
	IS
	BEGIN
		self.status := 'New';
		self.s_rows := p_rows;

		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

-- break on name skip1
SELECT name, type, COUNT(*)
FROM   user_source
WHERE  name like 'SUDOKU%'
GROUP BY name, type
ORDER BY name, type

set term on

-- Some tests:
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;
.

set timi on

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

-- Test ref cursor output:
DECLARE
	v_sudoku SUDOKU :=
		NEW SUDOKU
		( SUDOKU_ELEMENT_TT
			( SUDOKU_ELEMENT(' 1 3    6')
			, SUDOKU_ELEMENT(' 2 5  7 1')
			, SUDOKU_ELEMENT(' 9 761  4')
			, SUDOKU_ELEMENT('  4 1 5  ')
			, SUDOKU_ELEMENT('3 7   2 9')
			, SUDOKU_ELEMENT('  2 9 8  ')
			, SUDOKU_ELEMENT('5  926 3 ')
			, SUDOKU_ELEMENT('2 8  3 9 ')
			, SUDOKU_ELEMENT('6    4 7 '))
		);
BEGIN
	IF v_sudoku.status = 'Failed' THEN
		v_sudoku.solve(TRUE);
	END IF;
	:results := v_sudoku.solved_cursor;
END;
.

-- Tony Andrews test case:
-- http://tonyandrews.blogspot.com/2006/01/plsql-so-doku-solver.html
-- This requires the second stage in the solve() procedure because the first
-- series of passes ends with only ambiguous cells.
DECLARE
	v_sudoku SUDOKU :=
		NEW SUDOKU
		( SUDOKU_ELEMENT_TT
			( SUDOKU_ELEMENT(' 6 1 4 5 ')
			, SUDOKU_ELEMENT('  83 56  ')
			, SUDOKU_ELEMENT('2       1')
			, SUDOKU_ELEMENT('8  4 7  6')
			, SUDOKU_ELEMENT('  6   3  ')
			, SUDOKU_ELEMENT('7  9 1  4')
			, SUDOKU_ELEMENT('5       2')
			, SUDOKU_ELEMENT('  72 69  ')
			, SUDOKU_ELEMENT(' 4 5 8 7 '))
		);
BEGIN
	NULL;
END;
/

-- Test SQL:
SELECT NEW SUDOKU
       ( SUDOKU_ELEMENT_TT
         ( SUDOKU_ELEMENT(' 6 1 4 5 ')
         , SUDOKU_ELEMENT('  83 56  ')
         , SUDOKU_ELEMENT('2       1')
         , SUDOKU_ELEMENT('8  4 7  6')
         , SUDOKU_ELEMENT('  6   3  ')
         , SUDOKU_ELEMENT('7  9 1  4')
         , SUDOKU_ELEMENT('5       2')
         , SUDOKU_ELEMENT('  72 69  ')
         , SUDOKU_ELEMENT(' 4 5 8 7 '))
       ) AS new_sudoku
FROM dual;

exec null


-- Test diagnostic output:
DECLARE
	v_sudoku SUDOKU :=
		NEW SUDOKU
		( SUDOKU_ELEMENT_TT
			( SUDOKU_ELEMENT(' 6 1 4 5 ')
			, SUDOKU_ELEMENT('  83 56  ')
			, SUDOKU_ELEMENT('2       1')
			, SUDOKU_ELEMENT('8  4 7  6')
			, SUDOKU_ELEMENT('  6   3  ')
			, SUDOKU_ELEMENT('7  9 1  4')
			, SUDOKU_ELEMENT('5       2')
			, SUDOKU_ELEMENT('  72 69  ')
			, SUDOKU_ELEMENT(' 4 5 8 7 '))
		, TRUE
		);
BEGIN
	NULL;
END;
/

set timi off