n王后问题的优化

〇〇

同样的sql,oracle比sqlite慢
sqlite> WITH RECURSIVE
   ...>   n(n) as(values(12)),
   ...>   p(p,r,c) AS (
   ...>     VALUES(1,1,1)
   ...>     UNION SELECT ALL
   ...>     p+1,p/n+1,p%n+1 FROM p,n WHERE p < n*n
   ...>     ),
   ...>   w as(select p,2<<(c-1)w,2<<(N-1+r-c)w1,2<<(r+c-2)w2 from p,n),
   ...>   b(board, n_queens,w,w1,w2)as(
   ...>     SELECT p||'', 1 ,w,w1,w2
   ...>       FROM w,n where  p<=n
   ...>     UNION all
   ...>     SELECT
   ...>       board||p ,N_queens + 1 ,b.w+w.w,b.w1+w.w1,b.w2+w.w2
   ...>       FROM b, w,n
   ...>     WHERE n_queens <n
   ...>       and p >n_queens*N and p<=(n_queens+1)*N
   ...>       and b.w&w.w=0 and b.w1&w.w1=0 and b.w2&w.w2=0
   ...> )
   ...> select count(*) board from b,n where n_queens =n
   ...> ;
14200
Run Time: real 17.788 user 17.269311 sys 0.202801

SQL> with p(p,r,c)
  2  as(select level,ceil(level/:n),mod(level-1,:n)+1 from dual connect by level<=:n*:n)
  3  ,w as(select p,power(2,c-1)w,power(2,:N-1+r-c)w1,power(2,r+c-2)w2 from p)
  4  ,b(board, n_queens,w,w1,w2)as(
  5      SELECT cast(p as varchar(200)), 1 ,w,w1,w2
  6        FROM w where  p<=:N
  7      UNION all
  8      SELECT
  9        board||p ,N_queens + 1 ,b.w+w.w,b.w1+w.w1,b.w2+w.w2
10        FROM b, w
11      WHERE n_queens <:N
12        and p >n_queens*:N and p<=(n_queens+1)*:N
13        and bitand(b.w,w.w)=0 and bitand(b.w1,w.w1)=0 and bitand(b.w2,w.w2)=0
14  )
15  select count(*)board from b where n_queens =:N
16  ;

     BOARD
----------
     14200

已用时间:  00: 00: 24.57

〇〇

sql和java比还是差太多
http://www.ituring.com.cn/article/273298

〇〇

(normal)result of 14 Q is 365596,time is 1905311 ms (mthred)result of 14 Q is 365596,time is 311290 ms          (mthred+half)result of 14 Q is 365596,time is 179771 ms

〇〇

上面是在手机上运行的结果，arm c4droid