Monday, January 02, 2006

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.

1 comment:

William Robertson said...

I've been meaning to have a go at a Sudoku solver for a while, and I finally have:
www.williamrobertson.net/code/sudoku.pls

Unfortunately although the idea behind it is rather elegant if I say so myself, by the time I had the whole thing in place (including the extra passes I found I needed when it couldn't solve your test example) it had turned into a bit a monster with 600+ lines in two object types, and two collection types.

The rather elegant idea was that a Sudoku Element object could hold 9 integers in a varray, with a method to return its free list (the numbers not yet used in it). Then a Sudoku object would consist of a varray of 9 Sudoku Elements and a solve() method. The candidate values for any blank cell would be an array given by (in pseudocode):

candidates :=
multiset intersect
( row.free_list
, column.free_list
, square.free_list );

If candidates.COUNT = 1, then we have the only value that can go in that cell. The sudoku.solve() method would therefore just repeatedly loop over the rows applying the above function until either it filled in all the blanks or it had to give up because the only remaining blanks had more than one value. Which as luck would have it is what happened with your test case.

Anyway it was fun, and I might even write it up as an article on programming with PL/SQL objects.