Skip to content

Instantly share code, notes, and snippets.

@crazycloud

crazycloud/data_structure.sql

Created July 25, 2012 10:38
Show Gist options
  • Save crazycloud/3175482 to your computer and use it in GitHub Desktop.
Save crazycloud/3175482 to your computer and use it in GitHub Desktop.
Download ZIP
PL sql package to solve easy and medium sudoku
Raw
data_structure.sql
--create 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;
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
update xx_test set id = rownum
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;
Raw
view.sql
DROP VIEW APPS.XX_SOLVE_V;
/* Formatted on 2012/07/25 11:10 (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;
Raw
xx_solve.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;
/
CREATE OR REPLACE PACKAGE BODY APPS.xx_solve
IS
/* 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
*/
FUNCTION get_block (m NUMBER, n NUMBER)
RETURN block_values
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 certain value is present in row/column/block then,
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 values 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, 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 (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;
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;
--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;
EXECUTE IMMEDIATE l_qry
INTO r;
ELSE
IF get_cell_value (i_temp, j_temp) IS NULL
THEN
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;
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;
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;
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;
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;
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;
/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment