If you want to write a program to solve sudokus, you can use almost any programming language. And PL/SQL too!

Solving a Sudoku can basically be done in two ways:

• applying rules
• brute force

See Oracle PL/SQL Sudoku Solver or How to solve sudoku puzzles for an explanation of some of the rules you can use for solving a Sudoku. But my I will describe my program. I use a nested table, so I started with the definition of some types.

create or replace type mog is object
( r number(1)
, c number(1)
, b number(1)
, v number(1)
, p sys.dbms_debug_vc2coll
)
/
create or replace type tab_mog is table of mog
/

In the type mog I can store the row, column and block of a cell in the sodoku, the solution value for the cell and the possible solutions for the cell in the nested table p. As input for my function I use a refcursor, which should contain a query with 9 records with 9 columns, for instance

```select count(v) from table( sudoku( cursor(
select '','','','1','','','','','' from dual union all
select '','','','','','5','8','1','' from dual union all
select '','','5','','4','2','','','6' from dual union all
select '6','','4','5','','','','','' from dual union all
select '','2','','','9','','','8','' from dual union all
select '','','','','','6','2','','9' from dual union all
select '9','','','8','1','','7','','' from dual union all
select '','1','6','3','','','','','' from dual union all
select '','','','','','9','','','' from dual
) ) );```

This refcursor is converted to a nested table of the type tab_mog

```  fetch rc bulk collect into z;
--
x := tab_mog();
x.extend(81);
for i in z.first .. z.last
loop
for j in 1 .. 9
loop
x( ( i - 1 ) * 9 + j ) := mog( i
, j
, trunc( ( i - 1 ) / 3 ) * 3 + ( trunc( ( j - 1 ) / 3 ) + 1 )
, case j
when 1 then z( i ).c1
when 2 then z( i ).c2
when 3 then z( i ).c3
when 4 then z( i ).c4
when 5 then z( i ).c5
when 6 then z( i ).c6
when 7 then z( i ).c7
when 8 then z( i ).c8
when 9 then z( i ).c9
end
, null
);
end loop;
end loop;```

On this nested table I can apply 3 other functions, a simple rule based version, a more advanced rule based version and a brute force solver.

The simple rule based version determines possible values for every cell, and uses this information to solve the sudoku.

```      select mog( r, c, b, v
, nvl2( v
, sys.dbms_debug_vc2coll( v )
, nvl( p
, sys.dbms_debug_vc2coll( '1','2','3','4','5','6','7','8','9' )
multiset except ( select cast( collect( to_char( v ) ) as sys.dbms_debug_vc2coll )
from table( x ) yy
where yy.r = xx.r
or    yy.c = xx.c
or    yy.b = xx.b
)
)
)
)
bulk collect into y
from table( x ) xx;
--
select mog( r, c, b
, case
when xx.v is not null then xx.v
when cardinality( xx.p ) = 1 then ( select to_number( column_value ) from table( xx.p ) )
else ( select to_number( z.column_value )
from table( select ( xx.p multiset except distinct
cast( collect( case when yy.r = xx.r
and yy.c &lt;&gt; xx.c
then cast( pyy.column_value as varchar2(1) )
end
) as sys.dbms_debug_vc2coll
)
) multiset union
( xx.p multiset except distinct
cast( collect( case when yy.c = xx.c
and yy.r &lt;&gt; xx.r
then cast( pyy.column_value as varchar2(1) )
&amp;nb

sp;                                    end
) as sys.dbms_debug_vc2coll
)
) multiset union
( xx.p multiset except distinct
cast( collect( case when yy.b = xx.b
and ( yy.r &lt;&gt; xx.r or yy.c &lt;&gt; xx.c )
then cast( pyy.column_value as varchar2(1) )
end
) as sys.dbms_debug_vc2coll
)
) multiset except distinct sys.dbms_debug_vc2coll( null )
from table( y ) yy
, table( yy.p ) pyy
) z
)
end
, null
)
bulk collect into x
from table( y ) xx;```

With this simple rule most sudokus can be solved (more than I can do by hand), the version wich uses the more advanced rules can solve even more, but even that version can’t solve the following sudoku

```Su do ku   So lv er   by Am is
-- -- -- - -- -- -- - -- -- --
3  8                     2
1  4       2          5
2          4  6    1  9```
``` 8     1    9          2
3     9       8
4     2          1       8  9```
```    8
9          3       8
1  4                  9  2```
`11 rows selected.`

The brute force version is a very simple recursive function. It solves every soduku, the more diffucult the sudoku the faster! For above sudoku it needs 2 seconds, but for some it may take more than 2 minutes.

```    select m
bulk collect into y
from ( select mog( r, c, b, v
, sys.dbms_debug_vc2coll( '1','2','3','4','5','6','7','8','9' )
multiset except ( select cast( collect( to_char( v ) ) as sys.dbms_debug_vc2coll )
from table( x ) yy
where yy.r = xx.r
or    yy.c = xx.c
or    yy.b = xx.b
)
) m
from table( x ) xx
where v is null
)
order by cardinality( m.p );
--
if y.count = 0
then
return 81;
end if;
--
if y( 1 ).p.count = 0
then
return 0;
end if;
--
for j in y( 1 ).p.first .. y( 1 ).p.last
loop
x( ( y( 1 ).r - 1 ) * 9 +  y( 1 ).c ).v := y( 1 ).p( j );
if brute_force( x ) &gt; 0
then
return 81;
end if;
x( ( y( 1 ).r - 1 ) * 9 +  y( 1 ).c ).v := null;
end loop;
return 0;```

So to solve all sudokus the best way is to start of with the simple rule based version, and than continue with the brute force version.

The code runs only on a Oracle 10.2 database.

Anton

(I have added the zip with the sourcecode)

Share.

1. Is there also such a thing as an obfuscated PL/SQL contest?

After reading your post, I couldn’t resist to do the same thing, in Java of course! Click here for my post containing my solution.

2. Anton Scheffer on

Thats looking good, I have requested an APEX workspace right away. My next project will be a APEX front end for my Sudoku solver.

3. Anton,

That is an interesting demo of collections. I will have to study it.

A while back, I wrote an app to solv Sudoku puzzles using SQL with an Application Express front end.
It uses a little PL/SQL to glue it together, but the solution of the puzzles is just straight SQL.

You can see it in action here: http://apex.oracle.com/pls/otn/f?p=45570:1

You can download a script to create the database objects here: http://apex.oracle.com/pls/otn/wwv_flow_file_mgr.get_file?p_security_group_id=563610923303911988&p_fname=sudobj.sql&p_inline=NO
An export of the APEX application is here: http://apex.oracle.com/pls/otn/wwv_flow_file_mgr.get_file?p_security_group_id=563610923303911988&p_fname=f45570.sql&p_inline=NO

Enjoy,
Doug Case