[roger]

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: