ORACLE SUDOKU SOLVERBill Magee 20th April 2006 Like many others I've recently been getting somewhat carried away with the craze for Sudoku puzzles. Tony Andrews wrote an Oracle Sudoku Solver which got me interested in seeing if I could expand on his version.
## What is SudokuSudoku is a number puzzle with a few quite simple rules. You start with a 9x9 grid, subdivided into 9 smaller 3x3 grids. Some cells will already contain a number from 1 to 9. Your task is to fill in the empty cells so that....- Each column and row contains each of the numbers from 1 to 9
- Each 3x3 grid also contains each of the numbers from 1 to 9
## The CodeCreate a simple table for processing... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

create table sudoku ( x number(1), y number(1), xg number(1), yg number(1), z varchar2(9) ); | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Create a simple trigger to populate the subgrid x,y values... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

create or replace trigger sudoku_xyg_trg before insert on sudoku for each row begin :new.xg := floor((:new.x-1)/3); :new.yg := floor((:new.y-1)/3); end; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The following view lays up the table into a readable sudoku grid... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

create or replace view sudoku_layup as select c1.y, c1.z as c1, c2.z as c2, c3.z as c3, c4.z as c4, c5.z as c5, c6.z as c6, c7.z as c7, c8.z as c8, c9.z as c9 from sudoku c1, sudoku c2, sudoku c3, sudoku c4, sudoku c5, sudoku c6, sudoku c7, sudoku c8, sudoku c9 where c1.x = 1 and c2.x = 2 and c3.x = 3 and c4.x = 4 and c5.x = 5 and c6.x = 6 and c7.x = 7 and c8.x = 8 and c9.x = 9 and c2.y = c1.y and c3.y = c1.y and c4.y = c1.y and c5.y = c1.y and c6.y = c1.y and c7.y = c1.y and c8.y = c1.y and c9.y = c1.y order by c1.y; | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

And finally the actual code (note the comments/annotation are in gray)... | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

CREATE OR REPLACE package sudoku_pkg as procedure Solve(inRow1 in varchar2, inRow2 in varchar2, inRow3 in varchar2, inRow4 in varchar2, inRow5 in varchar2, inRow6 in varchar2, inRow7 in varchar2, inRow8 in varchar2, inRow9 in varchar2 ); function each_of_sub_in( insub in varchar2, inmain in varchar2) return binary_integer; PRAGMA RESTRICT_REFERENCES( each_of_sub_in, RNDS, WNDS, WNPS ); end; / CREATE OR REPLACE package body sudoku_pkg as procedure Populate( inRow1 in varchar2, inRow2 in varchar2, inRow3 in varchar2, inRow4 in varchar2, inRow5 in varchar2, inRow6 in varchar2, inRow7 in varchar2, inRow8 in varchar2, inRow9 in varchar2 ) is begin delete from sudoku; for i in 1..9 loop insert into sudoku(x,y,z) values (i,1,trim(substr(inrow1,i,1))); insert into sudoku(x,y,z) values (i,2,trim(substr(inrow2,i,1))); insert into sudoku(x,y,z) values (i,3,trim(substr(inrow3,i,1))); insert into sudoku(x,y,z) values (i,4,trim(substr(inrow4,i,1))); insert into sudoku(x,y,z) values (i,5,trim(substr(inrow5,i,1))); insert into sudoku(x,y,z) values (i,6,trim(substr(inrow6,i,1))); insert into sudoku(x,y,z) values (i,7,trim(substr(inrow7,i,1))); insert into sudoku(x,y,z) values (i,8,trim(substr(inrow8,i,1))); insert into sudoku(x,y,z) values (i,9,trim(substr(inrow9,i,1))); end loop; update sudoku set z = '123456789' where z = '.'; end Populate; function each_of_sub_in( insub in varchar2, inmain in varchar2) return binary_integer is result binary_integer; begin result := 1; for i in 1..length( insub ) loop if instr( inmain, substr(insub,i,1) ) = 0 then result := 0; end if; end loop; return result; end; function EliminateSinglesInRow return binary_integer is Result binary_integer default 0; begin for rec in (select x,y,z from sudoku where length(z) = 1) loop update sgcolor="white">9 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

It isn't infallible, there are puzzles which it cannot solve. Whether it is because the puzzle is unsolvable, or just that this code can't solve it I'm not quite sure :-(

Websudoku offers many puzzles of varying difficulty.

Feel free to email me with any thoughts or comments