puzzleup2012谜题，请用SQL或PLSQL解答

〇〇

No: 04       August 15, 2012  

Three Kings


What is the number of ways to place 3 kings on a standard chessboard so that no one attacks the others?

If the problem was asked for 3x3 board the answer would be 8.



[ You can answer this problem starting from Thursday at 11:00 (GMT) ]

〇〇

No: 04       August 15, 2012

Three Kings What is the number of ways to place 3 kings on a standard chessboard so that no one attacks the others? If the problem was asked for 3x3 board the answer would be 8. [ You can answer this problem starting from Thursday at 11:00 (GMT) ]

newkid

三个王
在一个标准的棋盘上摆放三个王，让他们不能互相攻击。总共有多少种摆放方法？

如果这个问题是在3X3的棋盘上提出，那么答案是8.

注：国际象棋的王可以攻击上下左右相邻的棋子。

这个题太简单了，连去重复都不要求！

udfrog

No 4. Three kings

1. with t as (
   
2. select        c, r
   
3. from        (select rownum c from dual connect by rownum<=8),
   
4.         (select rownum r from dual connect by rownum<=8)
   
5. )
   
6. select        count(*)/6
   
7. from        t a, t b, t c
   
8. where        (abs(a.c-b.c)>1 or abs(a.r-b.r)>1)
   
9. and        (abs(a.c-c.c)>1 or abs(a.r-c.r)>1)
   
10. and        (abs(b.c-c.c)>1 or abs(b.r-c.r)>1);
    

复制代码

〇〇

newkid 发表于 2012-8-16 03:44
三个王
在一个标准的棋盘上摆放三个王，让他们不能互相攻击。总共有多少种摆放方法？

3个王
with t as(select level l from dual connect by level<=25)
select /*count(*)*/ a.l,b.l,c.l from t a, t b, t c
where a.l>=7 and c.l<=19 and a.l<b.l and b.l-a.l not in(1,4,5,6)
and b.l<c.l and c.l-b.l not in(1,4,5,6)
and c.l-a.l not in(1,4,5,6)
and mod(a.l,5)not in(0,1)
and mod(b.l,5)not in(0,1)
and mod(c.l,5)not in(0,1)
;

udfrog

plsql虽然看起来繁琐,但是性能要比笛卡尔积好

1. declare
   
2. cnt        int:=0;
   
3. begin
   
4.         for c1 in 1..8 loop
   
5.                 for r1 in 1..8 loop
   
6.                         for c2 in 1..8 loop
   
7.                                 for r2 in 1..8 loop
   
8.                                         continue when abs(c1-c2)<=1 and abs(r1-r2)<=1;
   
9.                                         for c3 in 1..8 loop
   
10.                                                 for r3 in 1..8 loop
    
11.                                                         continue when (abs(c1-c3)<=1 and abs(r1-r3)<=1) or (abs(c2-c3)<=1 and abs(r2-r3)<=1);
    
12.                                                         cnt:=cnt+1;
    
13.                                                 end loop;
    
14.                                         end loop;
    
15.                                 end loop;
    
16.                         end loop;
    
17.                 end loop;
    
18.         end loop;
    
19.         dbms_output.put_line(cnt/6);
    
20. end;
    
21. /

复制代码

udfrog

1. with t as (
   
2. select        c, r
   
3. from        (select rownum c from dual connect by rownum<=8),
   
4.         (select rownum r from dual connect by rownum<=8)
   
5. )
   
6. select        count(*)
   
7. from        t a, t b, t c
   
8. where        (a.c+1<b.c or (a.c+1=b.c and abs(a.r-b.r)>1) or (a.c=b.c and a.r+1<b.r))
   
9. and        (b.c+1<c.c or (b.c+1=c.c and abs(b.r-c.r)>1) or (b.c=c.c and b.r+1<c.r))
   
10. and        (a.c+1<c.c or (a.c+1=c.c and abs(a.r-c.r)>1) or (a.c=c.c and a.r+1<c.r));

复制代码

可以尽早的把重复路线去掉,这样当棋盘变宽时,性能优势就出来了.

〇〇

with t as(select level l,trunc((level-1)/3)r,mod(level-1,3)c from dual connect by level<=9)
select /*count(*)*/ a.l,b.l,c.l from t a, t b, t c
where
a.l<b.l and b.l<c.l
and power(b.r-a.r,2)+power(b.c-a.c,2)>2.5
and power(c.r-b.r,2)+power(c.c-b.c,2)>2.5
and power(c.r-a.r,2)+power(c.c-a.c,2)>2.5
;

〇〇

udfrog 发表于 2012-8-16 08:35
可以尽早的把重复路线去掉,这样当棋盘变宽时,性能优势就出来了.

确实
SQL> with t as (
  2  select        c, r
  3  from        (select rownum c from dual connect by rownum<=18),
  4          (select rownum r from dual connect by rownum<=18)
  5  )
  6  select        count(*)
  7  from        t a, t b, t c
  8  where        (a.c+1<b.c or (a.c+1=b.c and abs(a.r-b.r)>1) or (a.c=b.c and a.r+1<b.r))
  9  and        (b.c+1<c.c or (b.c+1=c.c and abs(b.r-c.r)>1) or (b.c=c.c and b.r+1<c.r))
10  and        (a.c+1<c.c or (a.c+1=c.c and abs(a.r-c.r)>1) or (a.c=c.c and a.r+1<c.r));

  COUNT(*)
----------
   5239808

已用时间:  00: 00: 04.33
SQL> with t as(select level l,trunc((level-1)/18)r,mod(level-1,18)c from dual connect by level<=18*18)
  2  select count(*)from t a, t b, t c
  3  where
  4  a.l<b.l and b.l<c.l
  5  and power(b.r-a.r,2)+power(b.c-a.c,2)>2.5
  6  and power(c.r-b.r,2)+power(c.c-b.c,2)>2.5
  7  and power(c.r-a.r,2)+power(c.c-a.c,2)>2.5
  8  ;

  COUNT(*)
----------
   5239808

已用时间:  00: 00: 07.06
SQL> with t as(select level l from dual connect by level<=20*20)
  2  select count(*)from t a, t b, t c
  3  where a.l>=20 and c.l<=19*20 and a.l<b.l and b.l-a.l not in(1,19,20,21)
  4  and b.l<c.l and c.l-b.l not in(1,19,20,21)
  5  and c.l-a.l not in(1,19,20,21)
  6  and mod(a.l,20)not in(0,1)
  7  and mod(b.l,20)not in(0,1)
  8  and mod(c.l,20)not in(0,1)
  9  ;

  COUNT(*)
----------
   5239808

已用时间:  00: 00: 09.96

〇〇

udfrog 发表于 2012-8-16 08:35
可以尽早的把重复路线去掉,这样当棋盘变宽时,性能优势就出来了.

利用镜像更快
SQL> with t as(select level l,trunc((level-1)/18)r,mod(level-1,18)c from dual connect by level<=18*18)
  2  select count(*)*2 from t a, t b, t c
  3  where
  4  a.l<b.l and b.l<c.l and b.l<=18*9
  5  and power(b.r-a.r,2)+power(b.c-a.c,2)>2.5
  6  and power(c.r-b.r,2)+power(c.c-b.c,2)>2.5
  7  and power(c.r-a.r,2)+power(c.c-a.c,2)>2.5
  8  ;

COUNT(*)*2
----------
   5239808

已用时间:  00: 00: 03.13