Puzzleup 2013挑战赛即将开始

newkid

〇〇 发表于 2013-8-1 14:33
96可以=95*1+1*5
95又不行了
。。

你这是干啥呢？想要人肉？我上面已经把几个不可能的X列出来了，最小85，你去动脑筋吧。

lastwinner

newkid 发表于 2013-8-1 21:52
你这是干啥呢？想要人肉？我上面已经把几个不可能的X列出来了，最小85，你去动脑筋吧。

take as draft

lastwinner

newkid 发表于 2013-7-31 23:25
哪里用那么麻烦，就是笛卡尔积嘛，一下子就算出来了：
SELECT LEVEL N FROM DUAL WHERE LEVEL>1 CONNECT B ...

结果是对的但是逻辑上有问题，因为你预先判断出最小值不会超过100而又没写明推理

newkid

lastwinner 发表于 2013-8-2 01:53
结果是对的但是逻辑上有问题，因为你预先判断出最小值不会超过100而又没写明推理

这不用推理了吧，最小单位1u, 所以不可能超过100。

lastwinner

newkid 发表于 2013-8-2 02:47
这不用推理了吧，最小单位1u, 所以不可能超过100。

这理由就不对啊，你怎么就知道最小值一定要不超过100，而不是101呢？

newkid

lastwinner 发表于 2013-8-3 00:14
这理由就不对啊，你怎么就知道最小值一定要不超过100，而不是101呢？

我把CONNECT BY LEVEL<=100改成CONNECT BY LEVEL<=101不就行了？101肯定是候选答案之一。

lastwinner

newkid 发表于 2013-8-3 00:43
我把CONNECT BY LEVEL

对，这样才严谨
手工推断出一个可能值，然后以此为上限去找符合条件的最小值

newkid

#3

Six Kings

In how many different ways can six kings be placed on a 6x6 chessboard so that no one attacks the others?

If the problem was asked for a 3x3 board and 3 kings, then the answer would be 8.

在6X6的国际象棋棋盘上摆放六个王，使得他们不能互相攻击，有几种摆法？
如果是在3X3的棋盘上摆放三个王，则答案为8.

注：国际象棋的王每次可以在横、竖‘、斜方向走一格。

这个和皇后问题很像。

newkid

这本来是个挺无聊的题目，碰上我这个无聊的人就来做一做。用的是经典的比特掩码法。

递归WITH方法：
VAR N NUMBER;
EXEC :N:=6;

WITH k AS (
SELECT POWER(2,LEVEL-1) id ------- 二进制的一位
      ,TRUNC((LEVEL-1)/:N) X
      ,MOD(LEVEL-1,:N) Y
  FROM DUAL
CONNECT BY LEVEL<=:N*:N
)
,king AS (
SELECT k1.id,SUM(k2.id) AS m  ----- m表示攻击范围
  FROM k k1,k k2
WHERE k1.id<>k2.id
       AND ABS(k1.x-k2.x)<=1 AND ABS(k1.y-k2.y)<=1
GROUP BY k1.id
)
,t(cnt,id,all_id,m) AS (
SELECT 1 cnt,id,id,m
  FROM king
UNION ALL
SELECT t.cnt+1
      ,king.id
      ,t.all_id+king.id
      ,t.m + king.m - BITAND(t.m, king.m) --- BITOR
  FROM t,king
WHERE t.cnt<:N
       AND king.id>t.id
       AND BITAND(t.m, king.id)=0
)
SELECT COUNT(*) FROM t WHERE cnt  = :N;

  COUNT(*)
----------
     62266

Elapsed: 00:00:02.89


笛卡尔积，速度快得多：
WITH k AS (
SELECT POWER(2,LEVEL-1) id ------- 二进制的一位
      ,TRUNC((LEVEL-1)/6) X
      ,MOD(LEVEL-1,6) Y
  FROM DUAL
CONNECT BY LEVEL<=6*6
)
,king AS (
SELECT k1.id,SUM(k2.id) AS m
  FROM k k1,k k2
WHERE k1.id<>k2.id
       AND ABS(k1.x-k2.x)<=1 AND ABS(k1.y-k2.y)<=1
GROUP BY k1.id
)
SELECT COUNT(*)
  FROM king k1,king k2,king k3,king k4,king k5,king k6
WHERE k1.id<k2.id AND k2.id<k3.id AND k3.id<k4.id AND k4.id<k5.id AND k5.id<k6.id
       AND BITAND(k1.m, k2.id)=0
       AND BITAND(k1.m, k3.id)=0
       AND BITAND(k1.m, k4.id)=0
       AND BITAND(k1.m, k5.id)=0
       AND BITAND(k1.m, k6.id)=0
       AND BITAND(k2.m, k3.id)=0
       AND BITAND(k2.m, k4.id)=0
       AND BITAND(k2.m, k5.id)=0
       AND BITAND(k2.m, k6.id)=0
       AND BITAND(k3.m, k4.id)=0
       AND BITAND(k3.m, k5.id)=0
       AND BITAND(k3.m, k6.id)=0
       AND BITAND(k4.m, k5.id)=0
       AND BITAND(k4.m, k6.id)=0
       AND BITAND(k5.m, k6.id)=0
       ;

  COUNT(*)
----------
     62266

Elapsed: 00:00:00.66
      
BITAND只支持两个操作数，换成十进制加法(因为没有十进制位操作，改用字符串方法，效率很低):

WITH k AS (
SELECT POWER(10,LEVEL-1) id ------- 十进制的一位
      ,TRUNC((LEVEL-1)/6) X
      ,MOD(LEVEL-1,6) Y
  FROM DUAL
CONNECT BY LEVEL<=6*6
)
,king AS (
SELECT k1.id,SUM(k2.id) AS m
  FROM k k1,k k2
WHERE k1.id<>k2.id
       AND ABS(k1.x-k2.x)<=1 AND ABS(k1.y-k2.y)<=1
GROUP BY k1.id
)
SELECT COUNT(*)
  FROM king k1,king k2,king k3,king k4,king k5,king k6
WHERE k1.id<k2.id AND k2.id<k3.id AND k3.id<k4.id AND k4.id<k5.id AND k5.id<k6.id
       AND INSTR(TRANSLATE(k1.m+k2.m+k3.m+k4.m+k5.m+k6.m,'0123456','0111111') ---- 所有攻击范围掩码相加后，大于1的位全部转换成1, 达到类似BITOR的效果
                 +k1.id+k3.id+k4.id+k5.id+k6.id  ---- 相加后如果2没有出现，则达到类似BITAND=0的效果
                ,'2')=0;

  COUNT(*)
----------
     62266

Elapsed: 00:00:08.21

〇〇

8*8 8好像做过