Solving a Sudoku with Collections

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 <> 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 <> xx.r
                                                                 then cast( pyy.column_value as varchar2(1) )
                          &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 <> xx.r or yy.c <> 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 ) > 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)