n王后问题的优化

〇〇

用rpad代替lpad,更简短
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<=:N
    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<=(n_queens+1)*:N
      and bitand(b.w,sw)=0
)
select rpad(board,:N*:N,'-')board from b where n_queens =:N
;

〇〇

〇〇 发表于 2016-10-29 10:05
这个论坛的搜索功能越改越差了
你觉得sql最多n算到几？

bitand最多算到11
SQL> exec :n:=12

PL/SQL 过程已成功完成。

已用时间:  00: 00: 00.01
SQL> set autot trace
SQL> /
      and bitand(b.w,sw)=0
          *
第 15 行出现错误:
ORA-01426: 数字溢出


已用时间:  00: 00: 00.06

SQL> exec :n:=11

PL/SQL 过程已成功完成。

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

已选择2680行。

已用时间:  00: 00: 12.73

〇〇

newkid 发表于 2016-10-29 10:08
用BITAND判断纵横斜线上是否有子，肯定比NOT EXISTS快。

对数字溢出的,能否用2个number分别表示高位和低位合起来判断？

〇〇

这个改造自C程序的位操作
#include <stdio.h>
#include <stdlib.h>
int n = 12;
int q(int i, int j, int k, int l)
{
int ans = 0;
for(int a = ((1 << n) - 1) & ~(i | j | k), p = a & -a; a!=0; a ^= p, p = a & -a)
ans += q(i + p, (j + p) * 2, (k + p) / 2, l + 1);
return l == n ? 1 : ans;
}
int main(int argc,char*argv[])
{
if (argc==2)n=atoi(argv[1]);
printf("%d\n", q(0, 0, 0, 0));
}

---------------
create or replace function bitor(x IN NUMBER,y IN NUMBER)
return number is
begin
return (x + y) - BITAND(x, y);
end;
/
create or replace function bitxor(x IN NUMBER,y IN NUMBER)
return number is
begin
return (x + y) - BITAND(x, y)*2;
end;
/

create or replace function bitnot(x IN NUMBER) --~x=x^0xffff
return number is
begin
return (x -1 ) - BITAND(x, -1)*2;
end;
/
create or replace function bitlmv(x IN NUMBER,y IN NUMBER)
return number is
begin
return x* power(2,y);
end;
/

create or replace function q(n int, i int, j int, k int, l int)
return int
as
ans int:= 0;
a int;
p int;
begin
a := bitand((bitlmv(1, n) - 1) , bitnot(bitor(bitor(i , j ), k)));
p := bitand(a , -a);
while(a<>0)loop
ans :=ans+ q(n,(i + p), (j + p) * 2, trunc((k + p) / 2), l + 1);
         a := bitxor(a,p);
         p := bitand(a , -a);
end loop;
return  case l when n then 1 else ans end;
end;
/

SQL> select q(8,0, 0, 0, 0)from dual;

Q(8,0,0,0,0)
------------
          92

已用时间:  00: 00: 00.06
SQL> select level,q(level,0, 0, 0, 0)nq from dual connect by level<=12;

     LEVEL         NQ
---------- ----------
         1          1
         2          0
         3          0
         4          2
         5         10
         6          4
         7         40
         8         92
         9        352
        10        724
        11       2680
        12      14200

已选择12行。

已用时间:  00: 00: 07.12

〇〇

原来的程序
ans += q(i | p, (j | p) * 2, (k | p) / 2, l + 1);
改为
ans += q(i + p, (j + p) * 2, (k + p) / 2, l + 1);
也没错

〇〇

14楼程序的注释版
/***********************************************************************/
/* 目前最快的N皇后递归解决方法                                          */
/************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
long sum=0,upperlim=1;
//该算法的思想是遍历每一行(虽然算法中没有直接体现行遍历),然后对每一行中的所有
//有效列(即与上面行已放置皇后在列和左右对角线方向上不会造成冲突的列)进行尝试
//row是代表已经遍历的列，1表示该列已被皇后占有了
void GetSum(long row, long rightdiagonal, long leftdiagonal)
{
    if (row != upperlim)
    {
        //下面进行行遍历
        //row表示当前行中每一列放置了皇后,则该列在之后的行遍历中均不能再放置皇后了
        //rightdiagonal表示在下一行的尝试中当前放置点的左一列位置(下一行左一列的点与当前放置
        //点刚好形成了右对角线,会造成冲突)不可用
        //同样的leftdiagonal表示在下一行的尝试中当前放置点的右一列(下一行右一列的点与当前放置
        //点刚好形成了左对角线,会造成冲突)不可用
        long pos = upperlim & ~(row | leftdiagonal | rightdiagonal);
        //这里得到该行中所有可以尝试,即有效的列(格),然后从右到左进行尝试
        //如果遍历到的该行上的每一列已经都是无效的话则无需进行下一行的尝试了,方案失败.
       while (pos)
        {
            //该位操作能得到一个二进制数组中最右面的1的位置,如pos = 00010110进行如下操作之后
            //p = 00000010,p的作用是取得当前遍历的行中所有有效列的最右面的一列(格)(其实每次取
            //最左的列也行的)
            long p = pos & -pos;
            pos -= p;
            //p代表的是当前行上放置的列,递归调用函数遍历下一行
            //此时需将本行的尝试的列在row中标记上表明下一行不可再在此列放置皇后了
            //同时,在下一行中,本放置点的左一列和右一列也需标记为不可再放置
            GetSum(row+p, (rightdiagonal+p)<<1, (leftdiagonal+p)>>1);
        }
    }     
    else    //每一列都被皇后占领了,表示该方案可行  
    {
        sum++;
    }
}
int main(int argc, char *argv[])
{
    time_t tm; int n=15;
    if(argc!=1)
        n=atoi(argv[1]);
    tm=time(0);
    if((n<1)||(n>32))
    {
        printf(" heh..I can't calculate that.\n");
        //exit(-1);
    }

    printf("%d Queens\n",n);
    //upperlim中低n位为1，用于标识探索是否已完成
    upperlim=(upperlim<<n) - 1;
    GetSum(0,0,0);
    printf("Number of solutions is %ld, %d seconds\n", sum,(int)(time(0)-tm));
    return 0;
}

〇〇

create or replace function h(n int, i int, j int, k int, l int)
return int
as
ans int:= 0;
a int;
p int;
function bit_or(x IN NUMBER,y IN NUMBER)
return number is
begin
return (x + y) - BITAND(x, y);
end;
function bit_xor(x IN NUMBER,y IN NUMBER)
return number is
begin
return (x + y) - BITAND(x, y)*2;
end;
function bit_not(x IN NUMBER) --~x=x^0xffff
return number is
begin
return (x -1 ) - BITAND(x, -1)*2;
end;
begin
a := bitand((power(2, n) - 1) , bit_not(bit_or(bit_or(i , j ), k)));
p := bitand(a , -a);
while(a<>0)loop
ans :=ans+ h(n,(i + p), (j + p) * 2, trunc((k + p) / 2), l + 1);
         a := bit_xor(a,p);
         p := bitand(a , -a);
end loop;
return  case l when n then 1 else ans end;
end;
/
select h(12,0, 0, 0, 0)from dual;

SQL> alter session set plsql_code_type='NATIVE';

会话已更改。

已用时间:  00: 00: 00.06

SQL> alter function h compile;

函数已更改。

已用时间:  00: 00: 00.34

newkid

看不懂这个最快算法改进在哪里？
用SQL也是逐行尝试，设置列和对角占用标记。你当然可以用多个NUMBER来表示这些标记，相应的也就要多个BITAND操作。

〇〇

我也觉得就是二进制运算，但是快了，另一个更快的是把递归改成栈   http://www.jsomers.com/nqueen_demo/nqueens.html   

newkid

你11楼似乎是用一个二进制来表示两条斜线，分开左右不就行了吗，轻易就能表达30个QUEEN。
如果算法上没有突破，抠这些细节其实很没意思。