Sudoku Solver (Easy Level) in Oracle PL SQL

Data structures used

Sudoku grid consist of this 9x9 cells. Each cell in grid has actual value(decided value) and a list of possible values.

Cell is represented by PL/SQL Object, consisting of a

• Number type which holds actual value, and


• Nested table which holds possible values for cell.

[sourcecode language="sql"]
--Cell
CREATE TYPE cell AS OBJECT (
actual_value number,
poss_values possible_values
)

--create nested table of possible values
CREATE TYPE possible_values AS TABLE OF number;
[/sourcecode]
[sourcecode language="sql"]
--Sudoku grid of 9 columns
CREATE TABLE xx_test (C1 cell,C2 cell,C3 cell,C4 cell,C5 cell,C6 cell,C7 cell,C8 cell,C9 cell,id number)
NESTED TABLE C1.poss_values STORE AS possible_val_tab1
NESTED TABLE C2.poss_values STORE AS possible_val_tab2
NESTED TABLE C3.poss_values STORE AS possible_val_tab3
NESTED TABLE C4.poss_values STORE AS possible_val_tab4
NESTED TABLE C5.poss_values STORE AS possible_val_tab5
NESTED TABLE C6.poss_values STORE AS possible_val_tab6
NESTED TABLE C7.poss_values STORE AS possible_val_tab7
NESTED TABLE C8.poss_values STORE AS possible_val_tab8
NESTED TABLE C9.poss_values STORE AS possible_val_tab9

--set row number for
update xx_test set id = rownum

[/sourcecode]

A block is defined as group of 9 cells like
Block B1 consists of cells
11 12 13
21 22 23
31 32 33

Update Rule for Possible values of cell

Possible values for a cell is calculated by removing actual value that is present in other cells in that particular row, column and block from list of possible values of the cell.

If a value is present in a row/column/block then it should not appear in any other cell in the same row/column/block.

For example, for cell 22, possible value is calculated by removing actual values of all cells in row R2, column C2 and Block B1 from Varray 1..9(all possible values)

Update Rule for Actual Value of a cell
1.Cell containing only one possible value.
2.Value possible only in one cell in a row, column and block

Pseudo Code

For all cells
Check If actual value is null then
check list of possible value for cell. If only one value possible, then update cell with this value.
For all values 1..9 check if the value is not possible in other cells of that particular row column or block then update cell with that value.



[sourcecode language="sql"]
CREATE OR REPLACE PACKAGE APPS.xx_solve
IS
FUNCTION get_block (m NUMBER, n NUMBER)
RETURN block_values;

FUNCTION get_cell_value (m NUMBER, n NUMBER)
RETURN NUMBER;

FUNCTION get_row_values (m NUMBER)
RETURN block_values;

FUNCTION get_col_values (n NUMBER)
RETURN block_values;

FUNCTION get_poss_values (m NUMBER, n NUMBER)
RETURN block_values;

PROCEDURE update_poss_values;

FUNCTION generate_grid (grid VARCHAR2)
RETURN NUMBER;

FUNCTION get_col_loner (m NUMBER, n NUMBER)
RETURN number;
FUNCTION get_row_loner (m NUMBER, n NUMBER)
RETURN number;
FUNCTION get_block_loner (m NUMBER, n NUMBER)
RETURN number;
procedure update_actual_value;
END;
/
[/sourcecode]
[sourcecode language="sql"]
CREATE OR REPLACE PACKAGE BODY APPS.xx_solve
IS

FUNCTION get_block (m NUMBER, n NUMBER)
RETURN block_values
/* A block is group of 9 cells
example Block B1 consists of cells
11 12 13
21 22 23
31 32 33
Input Parameters :cell identified by row and column number
Output is varray containing all the values of a block in which input cell falls
*/
IS
--TYPE block_values IS VARRAY(9) OF INTEGER;
l_block_val   block_values := block_values ();
x             NUMBER       := 3 * m;
y             NUMBER       := 3 * n;
cell_value    NUMBER;
BEGIN
FOR i IN 0 .. 2
LOOP
FOR j IN 0 .. 2
LOOP
l_block_val.EXTEND ();
l_block_val (l_block_val.COUNT) :=
get_cell_value (x + i + 1, y + j + 1);
NULL;
END LOOP;
END LOOP;

RETURN l_block_val;
END;

/*
Input : Cell identifiers
Ouput : Actual value of that paricular cell

*/
FUNCTION get_cell_value (m NUMBER, n NUMBER)
RETURN NUMBER
IS
l_value   NUMBER;
l_qry     VARCHAR2 (500)
:= 'select e.c' || n || '.actual_value from xx_test e where id ='
|| m;
BEGIN
EXECUTE IMMEDIATE l_qry
INTO l_value;

RETURN l_value;
END;

/*
Input: row number
Ouput Varray containing all values in that row
for Row 1 values of cell 11 12 13 14 15 16 17 18 19 will be returned in varray
*/
FUNCTION get_row_values (m NUMBER)
RETURN block_values
IS
l_block_val   block_values   := block_values ();
l_qry         VARCHAR2 (500);
l_value       NUMBER;
BEGIN
FOR n IN 1 .. 9
LOOP
l_qry :=
'select e.c' || n || '.actual_value from xx_test e where id ='
|| m;

EXECUTE IMMEDIATE l_qry
INTO l_value;

l_block_val.EXTEND ();
l_block_val (l_block_val.COUNT) := l_value;
END LOOP;

RETURN l_block_val;
END;

/*
Input: col number
Ouput Varray containing all values in that row
for Column1 values of cell 11 21 31 41 51 61 71 81 91 will be returned in varray
*/
FUNCTION get_col_values (n NUMBER)
RETURN block_values
IS
l_block_val   block_values   := block_values ();
l_qry         VARCHAR2 (500);
l_value       NUMBER;
BEGIN
FOR m IN 1 .. 9
LOOP
l_qry :=
'select e.c' || n || '.actual_value from xx_test e where id ='
|| m;

EXECUTE IMMEDIATE l_qry
INTO l_value;

l_block_val.EXTEND ();
l_block_val (l_block_val.COUNT) := l_value;
END LOOP;

RETURN l_block_val;
END;

/* If value is present in row/column/block tthen hat it should not appear in any other cell in same row/column/block
Possible value for a cell is calculated by removing actual values that are present in other cells for that row column and block
for example for cell 22 possible value is calculated by
removing actual values  of all cells in row R2, column C2 and Block B1 from vaary 1..9
*/
FUNCTION get_poss_values (m NUMBER, n NUMBER)
RETURN block_values
IS
l_block_val   block_values   := block_values ();
l_qry         VARCHAR2 (500);
l_value       NUMBER;
BEGIN
FOR cur IN (SELECT     LEVEL COLUMN_VALUE
FROM DUAL
CONNECT BY LEVEL < 10
MINUS
SELECT COLUMN_VALUE
FROM (SELECT COLUMN_VALUE
FROM TABLE (xx_solve.get_block (FLOOR ((m - 1) / 3),
FLOOR ((n - 1) / 3)
)
)
UNION
SELECT COLUMN_VALUE
FROM TABLE (xx_solve.get_row_values (m))
UNION
SELECT COLUMN_VALUE
FROM TABLE (xx_solve.get_col_values (n)))
WHERE COLUMN_VALUE IS NOT NULL)
LOOP
l_block_val.EXTEND ();
l_block_val (l_block_val.COUNT) := cur.COLUMN_VALUE;
END LOOP;

RETURN l_block_val;
END;

/*For each cell where actual value is not yet decided
update possible value by calling get_poss_value
*/
PROCEDURE update_poss_values
AS
l_qry   VARCHAR2 (2000);
BEGIN
FOR i IN 1 .. 9
LOOP
FOR j IN 1 .. 9
LOOP
IF get_cell_value (i, j) IS NULL
THEN
l_qry :=
'UPDATE TABLE (SELECT e.c'
|| j
|| '.poss_values col
FROM xx_test e
WHERE ID ='
|| i
|| ') p
SET p.COLUMN_VALUE = NULL
WHERE p.COLUMN_VALUE NOT IN (SELECT *
FROM TABLE (xx_solve.get_poss_values ('
|| i
|| ','
|| j
|| ')))';

EXECUTE IMMEDIATE l_qry;
END IF;
END LOOP;
END LOOP;
END;

----------------comma seperated values to generate 81 cell grid---------------
FUNCTION generate_grid (grid VARCHAR2)
RETURN NUMBER
IS
l_qry     VARCHAR2 (2000);
l_val     NUMBER;
counter   NUMBER          := 0;
BEGIN
FOR i IN 1 .. 9
LOOP
FOR j IN 1 .. 9
LOOP
counter := counter + 1;
SELECT decode(substr(grid,counter,1),'0',to_number(null),to_number(substr(grid,counter,1))) into l_val from dual;

--         SELECT DECODE (SUBSTR (grid, INSTR (grid, '0', 1, counter) - 1, 1),
--               '0', NULL,
--               SUBSTR (grid, INSTR (grid, '0', 1, counter) - 1, 1)
--              )
--          INTO l_val
--           FROM DUAL;

DBMS_OUTPUT.put_line (counter||' '||l_val);
--  DBMS_OUTPUT.put_line (l_qry);

IF l_val IS NULL
THEN
l_qry :=
'update xx_test e  set c'
|| j
|| '= cell ('
|| 'null'
|| ', possible_values (1, 2,3,4,5,6,7,8,9)) where id='
|| i;
ELSE
l_qry :=
'update xx_test e  set c'
|| j
|| '= cell ('
|| l_val
|| ', possible_values (1, 2,3,4,5,6,7,8,9)) where id='
|| i;
END IF;

EXECUTE IMMEDIATE l_qry;
END LOOP;
END LOOP;

RETURN 1;
END;

---------- get only possible value in column by comapring all cells possible value for partucular column--------
----return number if only single possible value found for column else return null----------------
/* Check possible values for all cells in a column and if certain value is possible only in one cell then
return it
*/
FUNCTION get_col_loner (m NUMBER, n NUMBER)
RETURN NUMBER
IS
p         possible_values;
t         possible_values;
r         possible_values;
l_qry     VARCHAR2 (2000);
loner     NUMBER;
counter   NUMBER;
BEGIN
p :=
possible_values (NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL
);

--p varray contains all the possible values for cells other than input cell
--r varray contains possible values for input cell

FOR i IN 1 .. 9
LOOP
IF i = m
THEN
l_qry :=
'select e.c'
|| n
|| '.poss_values from xx_test e where id ='
|| i;

EXECUTE IMMEDIATE l_qry
INTO r;
ELSE
l_qry :=
'select e.c'
|| n
|| '.poss_values from xx_test e where id ='
|| i;

EXECUTE IMMEDIATE l_qry
INTO t;
p := p multiset union distinct t;
END IF;
END LOOP;

--perform set operation to find value that is possible only in this cell and not in any other column cells
p:= r multiset except p;
if p.count >0 then
FOR i IN p.FIRST .. p.LAST
LOOP
IF p (i) IS NOT NULL
THEN
counter := counter + 1;
loner := p (i);
END IF;
END LOOP;
end if;
--If only one possible value for this cell then, we can fill the actual value for this cell
IF counter = 1
THEN
DBMS_OUTPUT.put_line ('Found col loner for ' || m || ' , ' || n);
DBMS_OUTPUT.put_line (loner);
RETURN loner;
ELSE
RETURN NULL;
END IF;
END;

---------- get only possible value in block by comapring all cells possible value for partucular column--------
----return number if only single possible value found for block else return null----------------
/* Check possible values for all cells in a  block and if certain value is possible only in one cell then
return it
*/
FUNCTION get_block_loner (m NUMBER, n NUMBER)
RETURN NUMBER
IS
p         possible_values;
t         possible_values;
r         possible_values;
counter   NUMBER          := 0;
l_qry     VARCHAR2 (2000);
x         NUMBER          := 3 * FLOOR ((m - 1) / 3);
y         NUMBER          := 3 * FLOOR ((n - 1) / 3);
i_temp    NUMBER;
j_temp    NUMBER;
loner     NUMBER;
BEGIN
p :=
possible_values (NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL
);

--p varray contains all the possible values for cells other than input cell
--r varray contains possible values for input cell
FOR i IN 0 .. 2
LOOP
FOR j IN 0 .. 2
LOOP
i_temp := x + i + 1;
j_temp := y + j + 1;

IF i_temp = m AND j_temp = n
THEN

l_qry :=
'select e.c'
|| j_temp
|| '.poss_values from xx_test e where id ='
|| i_temp;

dbms_output.put_line('processing '||i_temp||' '||j_temp);

EXECUTE IMMEDIATE l_qry
INTO r;
ELSE
IF get_cell_value (i_temp, j_temp) IS NULL
THEN
dbms_output.put_line('processing '||i_temp||' '||j_temp);
l_qry :=
'select e.c'
|| j_temp
|| '.poss_values from xx_test e where id ='
|| i_temp;

EXECUTE IMMEDIATE l_qry
INTO t;
p := p multiset union distinct t;

--p:= r multiset except p;

END IF;
END IF;
END LOOP;
END LOOP;

--perform set operation to find value that is possible only in this cell and not in any other block cells

p:= r multiset except p;

IF p.count>0 then
FOR i IN p.FIRST .. p.LAST
LOOP
IF p (i) IS NOT NULL
THEN
counter := counter + 1;
loner := p (i);
END IF;
END LOOP;
END IF;
IF counter = 1
THEN
DBMS_OUTPUT.put_line ('Found block loner for ' || m || ' , ' || n);
DBMS_OUTPUT.put_line (loner);
RETURN loner;
ELSE
RETURN NULL;
END IF;
END;

FUNCTION get_row_loner (m NUMBER, n NUMBER)
RETURN NUMBER
IS
p         possible_values;
t         possible_values;
r         possible_values;
l_qry     VARCHAR2 (2000);
loner     NUMBER;
counter   NUMBER;
BEGIN
p :=
possible_values (NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL
);

FOR i IN 1 .. 9
LOOP
IF i = n
THEN
l_qry :=
'select e.c'
|| i
|| '.poss_values from xx_test e where id ='
|| m;

EXECUTE IMMEDIATE l_qry
INTO r;
ELSE
l_qry :=
'select e.c'
|| i
|| '.poss_values from xx_test e where id ='
|| m;

EXECUTE IMMEDIATE l_qry
INTO t;
p := p multiset union distinct t;
END IF;
END LOOP;

p:= r multiset except p;
if p.count>0 then
FOR i IN p.FIRST .. p.LAST
LOOP
IF p (i) IS NOT NULL
THEN
counter := counter + 1;
loner := p (i);
END IF;
END LOOP;
end if;
IF counter = 1
THEN
DBMS_OUTPUT.put_line ('Found row loner for ' || m || ' , ' || n);
DBMS_OUTPUT.put_line (loner);
RETURN loner;
ELSE
RETURN NULL;
END IF;
END;

/*Main procedure that calls other procedure to find actual value for each cell
Actual value is updated in case of following cases
1.If poss_value for cell contains only one value
2.If get_row_loner return not null value, that is,  if certain value is possible in only this cell in a row
3.If get_col_loner return not null value, that is, if certain value is possible in only this cell in a col
4.If get_block_loner return not null value, that is, if certain value is possible in only this cell in a block
*/
PROCEDURE update_actual_value
AS
l_qry     VARCHAR2 (1000);
l_value   NUMBER;
l_flag    NUMBER          := 0;
BEGIN
FOR i IN 1 .. 9
LOOP
FOR j IN 1 .. 9
LOOP
IF get_cell_value (i, j) IS NULL
THEN
------only one possible value then ------------------
DBMS_OUTPUT.put_line (   'Checking actual value for '
|| i
|| ' , '
|| j
);
l_qry :=
'SELECT COLUMN_VALUE
FROM TABLE (SELECT e.c'
|| j
|| '.poss_values
FROM xx_test e
WHERE ID ='
|| i
|| ')
WHERE COLUMN_VALUE IS NOT NULL';

BEGIN
EXECUTE IMMEDIATE l_qry
INTO l_value;
-- update based on point 1 metioned above
EXECUTE IMMEDIATE    'UPDATE xx_test e   SET e.c'
|| j
|| '.actual_value ='
|| l_value
|| ' WHERE ID ='
|| i;

xx_solve.update_poss_values;
DBMS_OUTPUT.put_line
(   'only single possible value found for '
|| i
|| ' , '
|| j
|| ' value : '
|| l_value
);
EXCEPTION
WHEN TOO_MANY_ROWS
THEN
NULL;
WHEN NO_DATA_FOUND
THEN
NULL;
END;

----------------------------------------------------------------
IF get_cell_value (i, j) IS NULL
THEN
--update based on point 2-4 mentioned above
SELECT COALESCE (xx_solve.get_block_loner (i, j), xx_solve.get_row_loner (i, j),
xx_solve.get_col_loner (i, j)
)
INTO l_value
FROM DUAL;

IF l_value IS NOT NULL
THEN
EXECUTE IMMEDIATE    'UPDATE xx_test e   SET e.c'
|| j
|| '.actual_value ='
|| l_value
|| ' WHERE ID ='
|| i;

xx_solve.update_poss_values;
END IF;
END IF;
END IF;
END LOOP;
END LOOP;
END;
END;
/

[/sourcecode]
[sourcecode language="sql"]
DROP VIEW APPS.XX_SOLVE_V;

/* Formatted on 2012/10/12 09:22 (Formatter Plus v4.8.8) */
CREATE OR REPLACE FORCE VIEW apps.xx_solve_v (ID,
c1,
c2,
c3,
c4,
c5,
c6,
c7,
c8,
c9
)
AS
SELECT a.ID, c1, c2, c3, c4, c5, c6, c7, c8, c9
FROM (SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c1
FROM (SELECT DISTINCT e.ID,
DECODE (e.c1.actual_value,
NULL, COLUMN_VALUE,
e.c1.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c1.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) a,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c2
FROM (SELECT DISTINCT e.ID,
DECODE (e.c2.actual_value,
NULL, COLUMN_VALUE,
e.c2.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c2.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) b,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c3
FROM (SELECT DISTINCT e.ID,
DECODE (e.c3.actual_value,
NULL, COLUMN_VALUE,
e.c3.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c3.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) c,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c4
FROM (SELECT DISTINCT e.ID,
DECODE (e.c4.actual_value,
NULL, COLUMN_VALUE,
e.c4.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c4.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) d,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c5
FROM (SELECT DISTINCT e.ID,
DECODE (e.c5.actual_value,
NULL, COLUMN_VALUE,
e.c5.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c5.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) e,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c6
FROM (SELECT DISTINCT e.ID,
DECODE (e.c6.actual_value,
NULL, COLUMN_VALUE,
e.c6.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c6.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) f,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c7
FROM (SELECT DISTINCT e.ID,
DECODE (e.c7.actual_value,
NULL, COLUMN_VALUE,
e.c7.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c7.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) g,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c8
FROM (SELECT DISTINCT e.ID,
DECODE (e.c8.actual_value,
NULL, COLUMN_VALUE,
e.c8.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c8.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) h,
(SELECT   ID,
REPLACE
(XMLAGG (XMLELEMENT (e, COLUMN_VALUE || ',')).EXTRACT
('//text()'),
',',
''
) c9
FROM (SELECT DISTINCT e.ID,
DECODE (e.c9.actual_value,
NULL, COLUMN_VALUE,
e.c9.actual_value
) COLUMN_VALUE
FROM xx_test e, TABLE (e.c9.poss_values) b
ORDER BY ID, COLUMN_VALUE)
GROUP BY ID) i
WHERE a.ID = b.ID
AND b.ID = c.ID
AND c.ID = d.ID
AND d.ID = e.ID
AND e.ID = f.ID
AND f.ID = g.ID
AND g.ID = h.ID
AND h.ID = i.ID;

[/sourcecode]
[sourcecode language="sql"]
SELECT e.c1.actual_value "1" , e.c2.actual_value "2", e.c3.actual_value "3",
e.c4.actual_value "4", e.c5.actual_value "5", e.c6.actual_value "6",
e.c7.actual_value "7", e.c8.actual_value "8", e.c9.actual_value "9"
FROM xx_test e

--generate sample grid

DECLARE
n NUMBER;
BEGIN
n :=
xx_solve.generate_grid
('300050090004000200300500006090000708006000300200010000070000070004008000200405000020900007001008000800090070005');
COMMIT;
END;

[/sourcecode]

References
List of Hard Sudoku puzzle strings - Sudoku Puzzles