n王后问题的优化

〇〇

〇〇 发表于 2016-11-2 15:55
原来重点不是递归，而是取半个盘，然后翻转

with p(p,r,c,w)
as(select level,ceil(level/:n),mod(level-1,:n)+1,power(2,level-1) from dual connect by level<=:n*:n)
,w as(select q.p,q.r,q.c,q.w,sum(p.w)sw from p,p q where
p.r=q.r or p.c=q.c or q.r-q.c=p.r-p.c or q.r+q.c=p.r+p.c
group by q.p,q.r,q.c,q.w)
,b(board, n_queens,w)as(
    SELECT lpad('-',p-1,'-')||'*', 1 ,w
      FROM p where  p<=(case mod(:N,2) when 0 then :N/2 else (:N+1)/2 end)
    UNION all
    SELECT
      rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w
      FROM b, w
    WHERE n_queens <:N
      and p >n_queens*:N and
    p<=case when mod(:N,2)=1 and /*N_queens=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,sw)=0
)
select rpad(board,:N*:N,'-')board from b where n_queens =:N
;

〇〇

SQL> exec :n:=10

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL> /

     BOARD
----------
       362

已用时间:  00: 00: 01.43
SQL> with p(p,r,c,w)
  2  as(select level,ceil(level/:n),mod(level-1,:n)+1,power(2,level-1) from dual connect by level<=:n*:n)
  3  ,w as(select q.p,q.r,q.c,q.w,sum(p.w)sw from p,p q where
  4  p.r=q.r or p.c=q.c or q.r-q.c=p.r-p.c or q.r+q.c=p.r+p.c
  5  group by q.p,q.r,q.c,q.w)
  6  ,b(board, n_queens,w)as(
  7      SELECT lpad('-',p-1,'-')||'*', 1 ,w
  8        FROM p where  p<=:N
  9      UNION all
10      SELECT
11        rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w
12        FROM b, w
13      WHERE n_queens <:N
14        and p >n_queens*:N and p<=(n_queens+1)*:N
15        and bitand(b.w,sw)=0
16  )
17  select count(rpad(board,:N*:N,'-'))board from b where n_queens =:N
18  ;

     BOARD
----------
       724

已用时间:  00: 00: 02.21

〇〇

并行多线程
http://www.cnblogs.com/kwliu/p/3627931.html
http://www.cnblogs.com/newflydd/articles/5097256.html

newkid

〇〇 发表于 2016-11-2 12:43
n=16,左斜线也有31条了

两个角可以不用管，只需29条。
翻转旋转对称的思路我们在其它题目经常用。

〇〇

这个题除了y轴翻转，其他的在途中不好排除

〇〇

加上翻转代码，还是快了1/3

SQL> truncate table temp;

表被截断。

已用时间:  00: 00: 00.01
SQL> exec :n:=10

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> insert into temp
  2  with p(p,r,c,w)
  3  as(select level,ceil(level/:n),mod(level-1,:n)+1,power(2,level-1) from dual connect by level<=:n*:n)
  4  ,w as(select q.p,q.r,q.c,q.w,sum(p.w)sw from p,p q where
  5  p.r=q.r or p.c=q.c or q.r-q.c=p.r-p.c or q.r+q.c=p.r+p.c
  6  group by q.p,q.r,q.c,q.w)
  7  ,b(board, n_queens,w)as(
  8      SELECT lpad('-',p-1,'-')||'*', 1 ,w
  9        FROM p where  p<=(case mod(:N,2) when 0 then :N/2 else (:N+1)/2 end)
10      UNION all
11      SELECT
12        rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w
13        FROM b, w
14      WHERE n_queens <:N
15        and p >n_queens*:N and
16      p<=case when mod(:N,2)=1 and /*N_queens=1 and*/ b.w=power(2,(:N-1)/2) -- mid of row 1 is set
17     then (n_queens+1)*:N-(:N+1)/2
18     else (n_queens+1)*:N end
19        and bitand(b.w,sw)=0
20  ),
21  hf as(select rpad(board,:N*:N,'-')board from b where n_queens =:N)
22  select * from hf
23  union all
24  select listagg(reverse(substr(board,(l-1)*:N+1,:N)))
25  within group(order by l) from hf a,(select level l from dual connect by level<=:N)b
26  group by board
27  ;

已创建 724 行。

已用时间:  00: 00: 01.00
SQL> truncate table temp2;

表被截断。

已用时间:  00: 00: 00.07
SQL> create table temp2 (board varchar(256));
create table temp2 (board varchar(256))
             *
第 1 行出现错误:
ORA-00955: 名称已由现有对象使用


已用时间:  00: 00: 00.06
SQL> insert into temp2
  2  with p(p,r,c,w)
  3  as(select level,ceil(level/:n),mod(level-1,:n)+1,power(2,level-1) from dual connect by level<=:n*:n)
  4  ,w as(select q.p,q.r,q.c,q.w,sum(p.w)sw from p,p q where
  5  p.r=q.r or p.c=q.c or q.r-q.c=p.r-p.c or q.r+q.c=p.r+p.c
  6  group by q.p,q.r,q.c,q.w)
  7  ,b(board, n_queens,w)as(
  8      SELECT lpad('-',p-1,'-')||'*', 1 ,w
  9        FROM p where  p<=:N
10      UNION all
11      SELECT
12        rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w
13        FROM b, w
14      WHERE n_queens <:N
15        and p >n_queens*:N and p<=(n_queens+1)*:N
16        and bitand(b.w,sw)=0
17  )
18  select rpad(board,:N*:N,'-')board from b where n_queens =:N
19  ;

已创建 724 行。

已用时间:  00: 00: 01.49

SQL> select count(*) from(select * from temp2 intersect select * from temp);

  COUNT(*)
----------
       724

已用时间:  00: 00: 00.03

〇〇

再想上下翻转，不正确，而且就在最后一行，没什么用

==========
var n number;
exec :n:=8

with p(p,r,c,w)
as(select level,ceil(level/:n),mod(level-1,:n)+1,power(2,level-1) from dual connect by level<=:n*:n)
,w as(select q.p,q.r,q.c,q.w,sum(p.w)sw from p,p q where
p.r=q.r or p.c=q.c or q.r-q.c=p.r-p.c or q.r+q.c=p.r+p.c
group by q.p,q.r,q.c,q.w)
,b(board, n_queens,w)as(
    SELECT lpad('-',p-1,'-')||'*', 1 ,w
      FROM p where  p<=(case mod(:N,2) when 0 then :N/2 else (:N+1)/2 end)
    UNION all
    SELECT
      rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w
      FROM b, w
    WHERE n_queens <:N
      and p >case when n_queens=:N-1 then n_queens*:N+:N/2 else n_queens*:N end
    p<=case when mod(:N,2)=1 and /*N_queens=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,sw)=0
),
hf as(select rpad(board,:N*:N,'-')board from b where n_queens =:N)
select count(*) from hf;

24

〇〇

newkid 发表于 2016-11-2 22:18
两个角可以不用管，只需29条。
翻转旋转对称的思路我们在其它题目经常用。

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,7+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 count(rpad(board,:N*:N,'-'))board from b where n_queens =:N
;
n=8 9还对
n=10 11 12全错

〇〇

找到bug了，7应该改为:N-1
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
;

〇〇

同样的bitand对短的数据执行速度更快
SQL> exec :n:=11

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.00
SQL>
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 lpad('-',p-1,'-')||'*', 1 ,w,w1,w2
  6        FROM w where  p<=:N
  7      UNION all
  8      SELECT
  9        rpad(board,p-1,'-') || '*' ,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(rpad(board,:N*:N,'-'))board from b where n_queens =:N
16  ;

     BOARD
----------
      2680

已用时间:  00: 00: 08.24
SQL> with p(p,r,c,w)
  2  as(select level,ceil(level/:n),mod(level-1,:n)+1,power(2,level-1) from dual connect by level<=:n*:n)
  3  ,w as(select q.p,q.r,q.c,q.w,sum(p.w)sw from p,p q where
  4  p.r=q.r or p.c=q.c or q.r-q.c=p.r-p.c or q.r+q.c=p.r+p.c
  5  group by q.p,q.r,q.c,q.w)
  6  ,b(board, n_queens,w)as(
  7      SELECT lpad('-',p-1,'-')||'*', 1 ,w
  8        FROM p where  p<=:N
  9      UNION all
10      SELECT
11        rpad(board,p-1,'-') || '*' ,N_queens + 1 ,b.w+w.w
12        FROM b, w
13      WHERE n_queens <:N
14        and p >n_queens*:N and p<=(n_queens+1)*:N
15        and bitand(b.w,sw)=0
16  )
17  select count(rpad(board,:N*:N,'-'))board from b where n_queens =:N
18  ;

     BOARD
----------
      2680

已用时间:  00: 00: 12.57