September 6, 2005: On solving a sudoku with Oracle

A sudoku is a puzzle that consists of a 9x9 grid whose cells contain numbers between 1 and 9. At the beginning, only a few of these celles are filled in, and it's the solver's task to fill in every cell according to the following three rules:

Each row has no duplicate values in its cells
Each column has no duplicate values in its cells
The grid is split into 9 non-overlapping 3x3 blocks. These blocks also have no duplicate values.

See also the wikipedia entry on sudoku. Most likely, you'll find a more concise description for sudoku.

I have given myself the task to solve a sudoku with Oracle. Here's my solution.

First, we need a table to store the values of the cells in the grid. As we're progressing with the sudoku's solution, more and more values will be inserted into this table.

create table sudoku_values (
  row_    number(1) not null,
  col_    number(1) not null,
  v       number(1) not null,
  primary key (col_, row_)
);

This table is filled with the initial values (also called givens):

insert into sudoku_values values (1, 2, 6);
insert into sudoku_values values (1, 4, 1);
insert into sudoku_values values (1, 6, 4);
insert into sudoku_values values (1, 8, 5);

insert into sudoku_values values (2, 3, 8);
insert into sudoku_values values (2, 4, 3);
insert into sudoku_values values (2, 6, 5);
insert into sudoku_values values (2, 7, 6);

insert into sudoku_values values (3, 1, 2);
insert into sudoku_values values (3, 9, 1);

insert into sudoku_values values (4, 1, 8);
insert into sudoku_values values (4, 4, 4);
insert into sudoku_values values (4, 6, 7);
insert into sudoku_values values (4, 9, 6);

insert into sudoku_values values (5, 3, 6);
insert into sudoku_values values (5, 7, 3);

insert into sudoku_values values (6, 1, 7);
insert into sudoku_values values (6, 4, 9);
insert into sudoku_values values (6, 6, 1);
insert into sudoku_values values (6, 9, 4);

insert into sudoku_values values (7, 1, 5);
insert into sudoku_values values (7, 9, 2);

insert into sudoku_values values (8, 3, 7);
insert into sudoku_values values (8, 4, 2);
insert into sudoku_values values (8, 6, 6);
insert into sudoku_values values (8, 7, 9);

insert into sudoku_values values (9, 2, 4);
insert into sudoku_values values (9, 4, 5);
insert into sudoku_values values (9, 6, 8);
insert into sudoku_values values (9, 8, 7);

A view is created that shows for every cell all possible values that can be inserted without breaking the rules:

create view sudoku_possible as
select row_, col_, n, cnt from (
  with numbers as (select level n from dual connect by level < 10) 
  select
    count(n) over (partition by col_, row_) cnt, 
    n,
    row_,
    col_
  from (
    -- First all possible combinations of values, rows and columns is created
    -- This (first select-) statement returns 9 x 9 x 9 records
    select all_numbers.n n, 
           all_rows.n    row_, 
           all_cols.n    col_  
      from numbers all_numbers cross join numbers all_rows 
                               cross join numbers all_cols
    -- Then, for each column, the values need to be eliminated that are already present on the
    -- particular column.
    minus select v, all_rows.n, all_cols.n 
      from sudoku_values cross join numbers all_cols 
                         cross join numbers all_rows
      where col_ = all_cols.n
    -- Same thing for each row
    minus select v, all_rows.n, all_cols.n 
      from sudoku_values cross join numbers all_rows 
                         cross join numbers all_cols 
      where row_ = all_rows.n
    -- Same thing for each 3x3 block
    minus select v, all_rows.n, all_cols.n
      from sudoku_values cross join numbers all_rows 
                         cross join numbers all_cols 
      where ceil(row_/3) + 3*ceil(col_/3) = ceil(all_rows.n/3) + 3*ceil(all_cols.n/3)
  )
) s
-- Finally, already existing cells must not be returned
where not exists (select 1 from sudoku_values v where v.row_ = s.row_ and v.col_ = s.col_) ;

Of course, the interesting cells are those whose cnt=1.

Also, a function is needed that solves the sudoku:

create function sudoku_solve(savepoint_level in number) return boolean as
  -- cnt will be set to the numbers of filled in cells in sudoku_values
  cnt             number;
  -- last_cnt is used to see if we're doing any progression at all
  last_cnt        number := 0;
begin

  loop -- loop until...
    select count(*) into cnt from sudoku_values;

    -- cnt equals 81, in which case the sudoku is solved
    if cnt = 81 then return true; end if;

    if last_cnt = cnt then -- not doing any progression, we'll have to take a wild guess from other possibilities:
      -- looping over other possibile values until either...
      for r in (select row_, col_, n from sudoku_possible where cnt > 1 order by cnt) loop
        -- creating a savepoint in case we're wrong
        execute immediate 'savepoint sp' || savepoint_level;
        insert into sudoku_values values (r.row_, r.col_, r.n);
        -- ... the sudoke was solved, or ...
        if sudoku_solve(savepoint_level+1) then 
          return true;
        else
          --  .. we realize we guessed wrong
          --  in which case we roll back to the last savepoint and make a new guess.
          execute immediate 'rollback to savepoint sp' || savepoint_level;
        end if;
      end loop;

      -- all guesses could not solve the sudoku, so return false:
      return false;
    else
      last_cnt := cnt;
      -- insert the obvious values:
      insert into sudoku_values select row_, col_, n from sudoku_possible where cnt=1;

    end if;

  end loop;
end;
/

The function in action:

declare
  solved  boolean;
begin
  solved := sudoku_solve(0);
  dbms_output.put_line(case when solved then 'solved' else 'not solved' end);
end;
/

I am lucky, the sudoku was solved:

solved

The solution can then be displayed with

with numbers as (select level n from dual connect by level < 10) 
select
  substr(row_ || '|',1,2) " r",
  to_char(max(case when col_ = 1 then v else null end), '9') " 1",
  to_char(max(case when col_ = 2 then v else null end), '9') " 2",
  to_char(max(case when col_ = 3 then v else null end), '9') " 3",
  to_char(max(case when col_ = 4 then v else null end), '9') " 4",
  to_char(max(case when col_ = 5 then v else null end), '9') " 5",
  to_char(max(case when col_ = 6 then v else null end), '9') " 6",
  to_char(max(case when col_ = 7 then v else null end), '9') " 7",
  to_char(max(case when col_ = 8 then v else null end), '9') " 8",
  to_char(max(case when col_ = 9 then v else null end), '9') " 9"
from
  (select n col_ from numbers) cross join
  (select n row_ from numbers)       join
  sudoku_values using(col_, row_)
group by
  row_;

 r  1  2  3  4  5  6  7  8  9
-- -- -- -- -- -- -- -- -- --
1|  9  6  3  1  7  4  2  5  8
2|  1  7  8  3  2  5  6  4  9
3|  2  5  4  6  8  9  7  3  1
4|  8  2  1  4  3  7  5  9  6
5|  4  9  6  8  5  2  3  1  7
6|  7  3  5  9  6  1  8  2  4
7|  5  8  9  7  1  3  4  6  2
8|  3  1  7  2  4  6  9  8  5
9|  6  4  2  5  9  8  1  7  3

Updates

René Hauck has discovered that my solver has a bug. There are cases when the solver seems to solve a sudoku, but after inspecting the solution, it turns out that the solution is wrong. Unfortunately, I am too busy at the moment to track the bug and correct it.

Daniel Morgan has also written a sudoku solver which can be found here.

Phil Winfield writes:


Hello Rene
I was amazed by your approach to the solution of a Sudoku puzzle. The view is a
wonderful approach to this problem which I have not seen anywhere else.  I very
easily ported this to an Oracle HTML DB application for you to see -
http://htmldb.oracle.com/pls/otn/f?p=38916:1 In the afternoon it appears to
hang as this server gets very busy. I have placed some extra code in the
solution function to fail if it goes over 30 seconds. Apart from that, it is as
you created it.  

Best regards
Phil Winfield

Eppo von Straten has also sent me an email:


Hi,

Thanks for a great website and lots of nice contributions.

I read your article on sudoku and i may have a less brute force approch.  The
idea is to repeat a process of searching for cells that can only contain one
digit as a result of of the differnt constraints , only one occurence of each
digit per row, column, block.

I set up my basetable to contain not only rows, cols and digits but also the
blocknumber (1 to 9).

Then repeatedly count the number of digits each cell can contain using the
constraints from row, column and block where this equals 1 and update these.

Here's the program:

create table sb (
  rij   number(1),
  kolom number(1),
  digit number(1),
  blok  number(1)
);

insert into sb (rij, kolom, digit, blok) values (1, 1, null, 1);
insert into sb (rij, kolom, digit, blok) values (1, 2,    7, 1);
insert into sb (rij, kolom, digit, blok) values (1, 3, null, 1);
insert into sb (rij, kolom, digit, blok) values (1, 4,    3, 2);
insert into sb (rij, kolom, digit, blok) values (1, 5, null, 2);
insert into sb (rij, kolom, digit, blok) values (1, 6,    9, 2);
insert into sb (rij, kolom, digit, blok) values (1, 7, null, 3);
insert into sb (rij, kolom, digit, blok) values (1, 8, null, 3);
insert into sb (rij, kolom, digit, blok) values (1, 9, null, 3);
insert into sb (rij, kolom, digit, blok) values (3, 1,    5, 1);
insert into sb (rij, kolom, digit, blok) values (3, 2,    6, 1);
insert into sb (rij, kolom, digit, blok) values (3, 3, null, 1);
insert into sb (rij, kolom, digit, blok) values (3, 4, null, 2);
insert into sb (rij, kolom, digit, blok) values (3, 5,    8, 2);
insert into sb (rij, kolom, digit, blok) values (3, 6, null, 2);
insert into sb (rij, kolom, digit, blok) values (3, 7, null, 3);
insert into sb (rij, kolom, digit, blok) values (3, 8,    4, 3);
insert into sb (rij, kolom, digit, blok) values (3, 9, null, 3);
insert into sb (rij, kolom, digit, blok) values (4, 1, null, 4);
insert into sb (rij, kolom, digit, blok) values (4, 2,    1, 4);
insert into sb (rij, kolom, digit, blok) values (4, 3, null, 4);
insert into sb (rij, kolom, digit, blok) values (4, 4,    9, 5);
insert into sb (rij, kolom, digit, blok) values (4, 5, null, 5);
insert into sb (rij, kolom, digit, blok) values (4, 6, null, 5);
insert into sb (rij, kolom, digit, blok) values (4, 7, null, 6);
insert into sb (rij, kolom, digit, blok) values (4, 8, null, 6);
insert into sb (rij, kolom, digit, blok) values (4, 9,    8, 6);
insert into sb (rij, kolom, digit, blok) values (6, 1,    8, 4);
insert into sb (rij, kolom, digit, blok) values (6, 2, null, 4);
insert into sb (rij, kolom, digit, blok) values (6, 3, null, 4);
insert into sb (rij, kolom, digit, blok) values (6, 4, null, 5);
insert into sb (rij, kolom, digit, blok) values (6, 5, null, 5);
insert into sb (rij, kolom, digit, blok) values (6, 6,    4, 5);
insert into sb (rij, kolom, digit, blok) values (6, 7, null, 6);
insert into sb (rij, kolom, digit, blok) values (6, 8,    9, 6);
insert into sb (rij, kolom, digit, blok) values (6, 9, null, 6);
insert into sb (rij, kolom, digit, blok) values (5, 1, null, 4);
insert into sb (rij, kolom, digit, blok) values (5, 2, null, 4);
insert into sb (rij, kolom, digit, blok) values (5, 3,    5, 4);
insert into sb (rij, kolom, digit, blok) values (5, 4, null, 5);
insert into sb (rij, kolom, digit, blok) values (5, 5,    1, 5);
insert into sb (rij, kolom, digit, blok) values (5, 6, null, 5);
insert into sb (rij, kolom, digit, blok) values (5, 7,    2, 6);
insert into sb (rij, kolom, digit, blok) values (5, 8, null, 6);
insert into sb (rij, kolom, digit, blok) values (5, 9, null, 6);
insert into sb (rij, kolom, digit, blok) values (7, 1, null, 7);
insert into sb (rij, kolom, digit, blok) values (7, 2,    2, 7);
insert into sb (rij, kolom, digit, blok) values (7, 3, null, 7);
insert into sb (rij, kolom, digit, blok) values (7, 4, null, 8);
insert into sb (rij, kolom, digit, blok) values (7, 5,    6, 8);
insert into sb (rij, kolom, digit, blok) values (7, 6, null, 8);
insert into sb (rij, kolom, digit, blok) values (7, 7, null, 9);
insert into sb (rij, kolom, digit, blok) values (7, 8,    7, 9);
insert into sb (rij, kolom, digit, blok) values (7, 9,    9, 9);
insert into sb (rij, kolom, digit, blok) values (9, 1, null, 7);
insert into sb (rij, kolom, digit, blok) values (9, 2, null, 7);
insert into sb (rij, kolom, digit, blok) values (9, 3, null, 7);
insert into sb (rij, kolom, digit, blok) values (9, 4,    2, 8);
insert into sb (rij, kolom, digit, blok) values (9, 5, null, 8);
insert into sb (rij, kolom, digit, blok) values (9, 6,    8, 8);
insert into sb (rij, kolom, digit, blok) values (9, 7, null, 9);
insert into sb (rij, kolom, digit, blok) values (9, 8,    3, 9);
insert into sb (rij, kolom, digit, blok) values (9, 9, null, 9);
insert into sb (rij, kolom, digit, blok) values (8, 1, null, 7);
insert into sb (rij, kolom, digit, blok) values (8, 2,    4, 7);
insert into sb (rij, kolom, digit, blok) values (8, 3,    1, 7);
insert into sb (rij, kolom, digit, blok) values (8, 4,    7, 8);
insert into sb (rij, kolom, digit, blok) values (8, 5, null, 8);
insert into sb (rij, kolom, digit, blok) values (8, 6, null, 8);
insert into sb (rij, kolom, digit, blok) values (8, 7, null, 9);
insert into sb (rij, kolom, digit, blok) values (8, 8, null, 9);
insert into sb (rij, kolom, digit, blok) values (8, 9, null, 9);
insert into sb (rij, kolom, digit, blok) values (2, 1, null, 1);
insert into sb (rij, kolom, digit, blok) values (2, 2, null, 1);
insert into sb (rij, kolom, digit, blok) values (2, 3, null, 1);
insert into sb (rij, kolom, digit, blok) values (2, 4, null, 2);
insert into sb (rij, kolom, digit, blok) values (2, 5, null, 2);
insert into sb (rij, kolom, digit, blok) values (2, 6,    2, 2);
insert into sb (rij, kolom, digit, blok) values (2, 7,    7, 3);
insert into sb (rij, kolom, digit, blok) values (2, 8,    1, 3);
insert into sb (rij, kolom, digit, blok) values (2, 9, null, 3);
commit;

declare
  l_aantal       number(2);
  l_vorig_aantal number(2);
begin
 l_aantal       := 81;
 l_vorig_aantal := 99;
 while l_aantal > 0 and l_aantal < l_vorig_aantal loop
   for r in (
     select * from ( 
       select count(0) aantal, rij , kolom, max(testdigit) testdigit from 
         (select * from sb where digit is null     ) sb,
         (select distinct sb.blok testdigit from sb) onetonine
       where onetonine.testdigit not in (select nvl(digit,0) from sb sbr where sbr.rij   = sb.rij)   and 
             onetonine.testdigit not in (select nvl(digit,0) from sb sbk where sbk.kolom = sb.kolom) and 
             onetonine.testdigit not in (select nvl(digit,0) from sb sbc where sbc.blok  = sb.blok)
       group by rij , kolom
     )
     where aantal = 1 ) loop
       update sb set digit = r.testdigit where sb.rij = r.rij and sb.kolom = r.kolom;
   end loop;
   l_vorig_aantal := l_aantal;
   select count(0) into l_aantal from sb where digit is null;
 end loop;
end;
/

More on Oracle

This is an on Oracle article. The most current articles of this series can be found here.


	René Nyffenegger's collection of things on the web
	René Nyffenegger on Oracle - Most wanted - Feedback - Follow @renenyffenegger