Thursday, December 13, 2007

sudoku by pl/sql

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
/
create or replace function sudoku( rc in sys_refcursor, how in varchar2 := 'ALL' )
return tab_mog
is
type r9 is record
( c1 varchar2(5)
, c2 varchar2(5)
, c3 varchar2(5)
, c4 varchar2(5)
, c5 varchar2(5)
, c6 varchar2(5)
, c7 varchar2(5)
, c8 varchar2(5)
, c9 varchar2(5)
);
type t9 is table of r9;
z t9;
--
x tab_mog;
cnt pls_integer;
--
function simple( x in out tab_mog )
return pls_integer
is
y tab_mog;
--
cnt_v1 pls_integer;
cnt_v2 pls_integer;
begin
--
select count( v )
into cnt_v1
from table( x );
--
loop
--
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) )
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;
--
select count( v )
into cnt_v2
from table( x );
--
exit when cnt_v2 = cnt_v1 or cnt_v2 = 81;
cnt_v1 := cnt_v2;
--
end loop;
--
select mog( r, c, b, v
, nvl2( v
, sys.dbms_debug_vc2coll( 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
)
)
)
bulk collect into y
from table( x ) xx;
--
x := y;
--
return cnt_v2;
end;
--
function brute_force( x in out tab_mog )
return pls_integer
is
y tab_mog;
begin
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;
end;
--
function rule( x in out tab_mog )
return pls_integer
is
y tab_mog;
-- cross hatching row
chr tab_mog;
-- cross hatching column
chc tab_mog;
-- possible candidates
pcr tab_mog;
pcc tab_mog;
pcb tab_mog;
--
cnt_v1 pls_integer;
cnt_v2 pls_integer;
cnt_v3 pls_integer;
begin
cnt_v1 := 0;
loop
loop
cnt_v2 := simple( x );
exit when cnt_v2 = 81;
--
-- cross hatching row
select mog( aa.r
, null
, aa.b
, null
, cast( collect( cast( paa.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
multiset except distinct cast( collect( cast( pbb.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
)
bulk collect into chr
from table( x ) aa
, table( aa.p ) paa
, table( x ) bb
, table( bb.p ) pbb
where bb.b = aa.b
and bb.r <> aa.r
group by aa.r
, aa.b;
--
-- cross hatching column
select mog( null
, aa.c
, aa.b
, null
, cast( collect( cast( paa.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
multiset except distinct cast( collect( cast( pbb.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
)
bulk collect into chc
from table( x ) aa
, table( aa.p ) paa
, table( x ) bb
, table( bb.p ) pbb
where bb.b = aa.b
and bb.c <> aa.c
group by aa.c
, aa.b;
--
select mog( r, c, b, v
, xx.p
multiset intersect ( select case when cardinality ( cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll ) ) > 0
then cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
else sys.dbms_debug_vc2coll( '1','2','3', '4', '5', '6', '7', '8', '9' )
end
from table( chr ) ch
, table( ch.p ) pch
where ch.r = xx.r
and ch.b = xx.b
and ( cardinality( ch.p ) = 3
or ( cardinality( ch.p ) = 2
and exists ( select 'x'
from table( x ) yy
where yy.r = xx.r
and yy.b = xx.b
and yy.c <> xx.c
and cardinality( yy.p multiset intersect ch.p ) = 0
)
)
)
)
multiset intersect ( select case when cardinality ( cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll ) ) > 0
then cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
else sys.dbms_debug_vc2coll( '1','2','3', '4', '5', '6', '7', '8', '9' )
end
from table( chc ) ch
, table( ch.p ) pch
where ch.c = xx.c
and ch.b = xx.b
and ( cardinality( ch.p ) = 3
or ( cardinality( ch.p ) = 2
and exists ( select 'x'
from table( x ) yy
where yy.c = xx.c
and yy.b = xx.b
and yy.r <> xx.r
and cardinality( yy.p multiset intersect ch.p ) = 0
)
)
)
)
)
bulk collect into y
from table( x ) xx;
--
select mog( r, c, b, v
, xx.p
multiset except distinct ( select cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( chr ) ch
, table( ch.p ) pch
where ch.r = xx.r
and ch.b <> xx.b
)
multiset except distinct ( select cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( chc ) ch
, table( ch.p ) pch
where ch.c = xx.c
and ch.b <> xx.b
)
)
bulk collect into x
from table( y ) xx;
--
-- reverse cross hatching row
select mog( aa.r
, null
, aa.b
, null
, cast( collect( cast( paa.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
multiset except distinct cast( collect( cast( pbb.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
)
bulk collect into chr
from table( x ) aa
, table( aa.p ) paa
, table( x ) bb
, table( bb.p ) pbb
where bb.r = aa.r
and bb.b <> aa.b
group by aa.r
, aa.b;
--
-- reverse cross hatching column
select mog( null
, aa.c
, aa.b
, null
, cast( collect( cast( paa.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
multiset except distinct cast( collect( cast( pbb.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
)
bulk collect into chc
from table( x ) aa
, table( aa.p ) paa
, table( x ) bb
, table( bb.p ) pbb
where bb.c = aa.c
and bb.b <> aa.b
group by aa.c
, aa.b;
--
y := x;
--
select mog( r, c, b, v
, xx.p
multiset except distinct ( select cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( chr ) ch
, table( ch.p ) pch
where ch.r <> xx.r
and ch.b = xx.b
)
multiset except distinct ( select cast( collect( cast( pch.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( chc ) ch
, table( ch.p ) pch
where ch.c <> xx.c
and ch.b = xx.b
)
)
bulk collect into x
from table( y ) xx;
--
exit when cnt_v1 = cnt_v2;
cnt_v1 := cnt_v2;
end loop;

exit when cnt_v2 = 81 or cnt_v2 = cnt_v3;
-- possible candidates
-- row
select mog( i
, null
, null
, null
, ps_cv
)
bulk collect into pcr
from ( select ind.i
, possible_sets.column_value ps_cv
, ( select sum( case cardinality( aa.p multiset except possible_sets.column_value )
when 0 then 1
end
)
from table( x ) aa
where aa.v is null
and aa.r = ind.i
) nr_candidates
from table( powermultiset( sys.dbms_debug_vc2coll( '1','2','3', '4', '5', '6', '7', '8', '9' ) ) ) possible_sets
, ( select level i
from dual
connect by level < 10
) ind
where cardinality( possible_sets.column_value ) in ( 2, 3, 4, 5 )
)
where nr_candidates = cardinality( ps_cv );
-- column
select mog( null
, i
, null
, null
, ps_cv
)
bulk collect into pcc
from ( select ind.i
, possible_sets.column_value ps_cv
, ( select sum( case cardinality( aa.p multiset except possible_sets.column_value )
when 0 then 1
end
)
from table( x ) aa
where aa.v is null
and aa.c = ind.i
) nr_candidates
from table( powermultiset( sys.dbms_debug_vc2coll( '1','2','3', '4', '5', '6', '7', '8', '9' ) ) ) possible_sets
, ( select level i
from dual
connect by level < 10
) ind
where cardinality( possible_sets.column_value ) in ( 2, 3, 4, 5 )
)
where nr_candidates = cardinality( ps_cv );
-- block
select mog( null
, null
, i
, null
, ps_cv
)
bulk collect into pcb
from ( select ind.i
, possible_sets.column_value ps_cv
, ( select sum( case cardinality( aa.p multiset except possible_sets.column_value )
when 0 then 1
end
)
from table( x ) aa
where aa.v is null
and aa.b = ind.i
) nr_candidates
from table( powermultiset( sys.dbms_debug_vc2coll( '1','2','3', '4', '5', '6', '7', '8', '9' ) ) ) possible_sets
, ( select level i
from dual
connect by level < 10
) ind
where cardinality( possible_sets.column_value ) in ( 2, 3, 4, 5 )
)
where nr_candidates = cardinality( ps_cv );
--
y := x;
--
select mog( r, c, b, v
, xx.p
multiset except distinct ( select cast( collect( cast( ppc.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( pcr ) pc
, table( pc.p ) ppc
where pc.r = xx.r
and cardinality ( xx.p multiset except pc.p ) > 0
)
multiset except distinct ( select cast( collect( cast( ppc.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( pcc ) pc
, table( pc.p ) ppc
where pc.c = xx.c
and cardinality ( xx.p multiset except pc.p ) > 0
)
multiset except distinct ( select cast( collect( cast( ppc.column_value as varchar2(1) ) ) as sys.dbms_debug_vc2coll )
from table( pcb ) pc
, table( pc.p ) ppc
where pc.b = xx.b
and cardinality ( xx.p multiset except pc.p ) > 0
)
)
bulk collect into x
from table( y ) xx;
--
cnt_v3 := cnt_v2;
end loop;
return cnt_v2;
end;
--
begin
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;
--
cnt := 0;
if upper( how ) in ( 'ALL', 'SIMPLE' )
then
cnt := simple( x );
end if;
if upper( how ) in ( 'RULE' ) and cnt < 81
then
cnt := rule( x );
end if;
if upper( how ) in ( 'ALL', 'BRUTE' ) and cnt < 81
then
cnt := brute_force( x );
end if;
--
return x;
--
end;
/

Test:
set scan on
set verify off

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
), '&&how' ) );

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

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

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

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

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

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


column c1 format 9 heading "Su"
column c2 format 9 heading "do"
column c3 format 9 heading "ku"
column c4 format 9 heading "So"
column c5 format 9 heading "lv"
column c6 format 9 heading "er"
column c7 format 9 heading "by"
column c8 format 9 heading "Am"
column c9 format 9 heading "is"

select c1, c2, c3, '' " ", c4, c5, c6, '' " ", c7, c8, c9
from ( select r
, sum( case when c = 1 then v end ) c1
, sum( case when c = 2 then v end ) c2
, sum( case when c = 3 then v end ) c3
, sum( case when c = 4 then v end ) c4
, sum( case when c = 5 then v end ) c5
, sum( case when c = 6 then v end ) c6
, sum( case when c = 7 then v end ) c7
, sum( case when c = 8 then v end ) c8
, sum( case when c = 9 then v end ) c9
from table( sudoku( cursor(
select '','3','8','','','','','','2' from dual union all
select '','','4','','2','','','5','' from dual union all
select '','','','','','6','1','9','' from dual union all
select '','','','9','','','2','','' from dual union all
select '','','','','8','','','','' from dual union all
select '4','','2','','','1','','','' from dual union all
select '','8','','','','','','','' from dual union all
select '','9','','','3','','8','','' from dual union all
select '1','','','','','','9','2','' from dual
), '&&how' ) )
group by r
union all
select 3 + 1/2, null, null, null, null, null, null, null, null, null
from dual
union all
select 6 + 1/2, null, null, null, null, null, null, null, null, null
from dual
)
order by r
/
undef how

No comments: