Friday, October 12, 2012

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.