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.
