ORACLE SUDOKU SOLVER
Bill 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 Sudoku

Sudoku 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
An important principle of Sudoku is that each puzzle should only have one solution and that it should always be solvable through logic and deduction without any need for guessing.
 9    15 
42      8
  1 9   2
  5 6  9 
   8 5   
 7  3 5  
6   2 3  
3      64
 52    1 

The Code

Create 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

Comments/Thoughts

This isn't as efficient as Tonys version in that it will keep revisiting rule attempts regardless of prior success or not.

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