PL/SQL So Doku Solver

So Doku has taken over the UK, if not the world, in the last year. I am now addicted, but at first I couldn't see the point in these puzzle and prefered to write a program to solve them for me. What was the point in that? Absolutely none! But in case you ever feel the need to get a Su Doku puzzle solved without actualy doing it yourself, here is the code - think of it as a late Christmas present!

First, we need to create a table:

create table cells
  ( x number(1,0) not null
  , y number(1,0) not null
  , z varchar2(9)
  , done varchar2(1) not null
  , constraint cells_pk primary key (x, y)
  )
/

Then a package:

create or replace package cell_pkg as
  procedure solve(p_state in varchar2);
  procedure print;
end;
/

create or replace package body cell_pkg as
  procedure solve(p_state in varchar2)
  is
    v varchar2(1);
    cnt integer;
    processed integer;
    it_failed exception;
  begin
    -- Set up a clean board
    delete cells;
    for r in 1..9 loop
      for c in 1..9 loop
        insert into cells (x,y,z,done) values (r,c,'123456789','N');
      end loop;
    end loop;
    -- Apply initial state
    for r in 1..9 loop
      for c in 1..9 loop
        v := substr(p_state,(r-1)*9+c,1);
        if v between '1' and '9' then
          update cells
             set z = v
           where x = r
             and y = c;
        end if;
      end loop;
    end loop;
    -- Start processing
    loop
      processed := 0;
      -- Process cells that are solved but not yet marked as "done":
      for rec in (select * from cells where length(z)=1 and done='N')
      loop
        -- Remove that cell's value from the possible values for other cells
        -- in same row, column or square
        update cells
           set z = replace(z,rec.z)
         where (  x = rec.x
               or y = rec.y
               or (   floor((x-1)/3) = floor((rec.x-1)/3)
                  and floor((y-1)/3) = floor((rec.y-1)/3)
                  )
               )
           and (x <> rec.x or y <> rec.y); -- Exclude self!
        -- Now mark this cell as done
        update cells
           set done = 'Y'
         where x = rec.x and y = rec.y;
        -- Note how many cells processed on this pass
        processed := processed+1;
      end loop;
      -- Look for cells that are not solved, but where they are the only cell
      -- in their row, column or square containing a given value
      for i in 1..9 loop
        for rec in (select * from cells c1
                    where  length(z) > 1
                    and    z like '%'||i||'%'
                    and    (  not exists
                               (select null
                                from   cells c2
                                where  c2.x = c1.x -- Same row
                                and    (c1.x <> c2.x or c1.y <> c2.y) -- Exclude self!
                                and    c2.z like '%'||i||'%'
                               )
                           or not exists
                              (select null
                               from   cells c2
                               where  c2.y = c1.y -- Same column
                               and    (c1.x <> c2.x or c1.y <> c2.y) -- Exclude self!
                               and    c2.z like '%'||i||'%'
                               )
                           or not exists
                              (select null
                               from   cells c2
                               where  floor((c2.x-1)/3) = floor((c1.x-1)/3) -- Same
                               and    floor((c2.y-1)/3) = floor((c1.y-1)/3) -- square
                               and (c1.x <> c2.x or c1.y <> c2.y) -- Exclude self!
                               and c2.z like '%'||i||'%'
                              )
                           )
                   )
        loop
          update cells
             set z = i
           where x = rec.x
             and y = rec.y;
          -- Note how many cells processed on this pass
          processed := processed+1;
        end loop;
      end loop;
      -- Have we solved it yet?
      select count(*) into cnt from cells where length(z) > 1 and rownum = 1;
      exit when cnt = 0;
      -- No.  If we didn't achieve anything on this pass then give up
      if processed = 0 then
        raise it_failed;
      end if;
    end loop;
    print;
    dbms_output.put_line('SUCCESS!!!');
  exception
    when it_failed then
      print;
      dbms_output.put_line('FAILED!!!');
  end;

  procedure print
  is
  begin
    for rec in (select * from cells order by x,y)
    loop
      dbms_output.put(rec.z||' ');
      if rec.y = 9 then
        dbms_output.put_line('');
      end if;
    end loop;
  end;
end;
/

Now, how to use it. Let's take the following Su Doku puzzle as an example:

.6.1.4.5.
..83.56..
2.......1
8..4.7..6
..6...3..
7..9.1..4
5.......2
..72.69..
.4.5.8.7.

We can solve this as follows:

begin
cell_pkg.solve(' 6 1 4 5   83 56  2       18  4 7  6  6   3  7  9 1  45       2  72 69   4 5 8 7 ');
end;
/

(Enter all the grid values reading from left to right, top to bottom, including ALL spaces).
The output will look like this:

9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3
SUCCESS!!!

But perhaps you can do better? If you can write a better version, please let me know!

UPDATE 20 April 2006: Bill Magee has picked up the challenge and run with it, and his improved version is here.