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:

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.

Post a Comment