原来的版本,不能计算大于11的N,因为那使oracle的bitand溢出了。在的指点下,用同列,同左斜线,同右斜线3个bitmap代替用格子标号的1个bitmap。
with p(p,r,c) as(select level,ceil(level/:n),mod(level-1,:n)+1 from dual connect by level<=:n*:n) ,w as(select p,power(2,c-1)w,power(2,:N-1+r-c)w1,power(2,r+c-2)w2 from p) ,b(board, n_queens,w,w1,w2)as( SELECT lpad('-',p-1,'-')||'*', 1 ,w,w1,w2 FROM w where p<=:N UNION all SELECT rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w,b.w1+w.w1,b.w2+w.w2 FROM b, w WHERE n_queens <:N and p >n_queens*:N and p<=(n_queens+1)*:N and bitand(b.w,w.w)=0 and bitand(b.w1,w.w1)=0 and bitand(b.w2,w.w2)=0 ) select rpad(board,:N*:N,'-')board from b where n_queens =:N ;
计算n=12大约50秒.
with p(p,r,c) as(select level,ceil(level/:n),mod(level-1,:n)+1 from dual connect by level<=:n*:n) ,w as(select p,power(2,c-1)w,power(2,:N-1+r-c)w1,power(2,r+c-2)w2 from p) ,b(board, n_queens,w,w1,w2)as( SELECT lpad('-',p-1,'-')||'*', 1 ,w,w1,w2 FROM w where p<=ceil(:N/2) UNION all SELECT rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w,b.w1+w.w1,b.w2+w.w2 FROM b, w WHERE n_queens <:N and p >n_queens*:N and p<=case when mod(:N,2)=1 and b.w=power(2,(:N-1)/2) -- mid of row 1 is set then (n_queens+1)*:N-(:N+1)/2 else (n_queens+1)*:N end and bitand(b.w,w.w)=0 and bitand(b.w1,w.w1)=0 and bitand(b.w2,w.w2)=0 ), hf as(select rpad(board,:N*:N,'-')board from b where n_queens =:N) select * from hf union all select listagg(reverse(substr(board,(l-1)*:N+1,:N))) within group(order by l) from hf a,(select level l from dual connect by level<=:N)b group by board ;
利用对称,大约26秒。看来对于大的N,基本可以节约1半时间。