楼主: newkid

[精华] ITPUB第2届“盛拓传媒杯”SQL数据库编程大赛第二期参考思路

[复制链接]
论坛徽章:
20
SQL大赛参与纪念
日期:2013-12-06 14:03:45生肖徽章:狗
日期:2013-12-09 14:28:47生肖徽章:猪
日期:2013-12-09 14:28:472009架构师大会纪念徽章
日期:2015-08-03 13:54:362010系统架构师大会纪念
日期:2015-08-03 13:54:362011系统架构师大会纪念章
日期:2015-08-03 13:54:362012系统架构师大会纪念章
日期:2015-08-03 13:54:362013系统架构师大会纪念章
日期:2015-08-03 13:54:362014系统架构师大会纪念章
日期:2015-08-03 13:54:36生肖徽章:鸡
日期:2013-12-09 14:28:47
31#
发表于 2013-11-30 17:13 | 只看该作者
大师就是大师,慢慢消化

使用道具 举报

回复
论坛徽章:
520
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
32#
 楼主| 发表于 2013-12-1 10:35 | 只看该作者
〇〇 发表于 2013-11-30 12:44
25楼和model比还是很慢
set lines 120 pages 50000
set head on

你发这些数据很难看懂,必须说明一下每个ID到底代表着什么。
下周我再把丑陋递归法重新改一下,看看有没有提高。

使用道具 举报

回复
论坛徽章:
520
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
33#
 楼主| 发表于 2013-12-1 11:00 | 只看该作者
本帖最后由 newkid 于 2013-12-4 06:39 编辑

闲着也是闲着,丑陋法改出来了,不比MODEL(我自己写的MODEL)慢:
WITH cells AS (                      ------- 构造所有单元格及其坐标
   SELECT LEVEL cell_id              -------- 从左上角开始,从左到右从上到下从1开始编号
         ,CEIL(LEVEL/:v_width) r     -------- 行号,1~v_height
         ,MOD(LEVEL-1,:v_width)+1 c  -------- 列号,1~v_width
         ,SUBSTR(:v_str,LEVEL,1) cnt -------- 该单元格周围的地雷数目
     FROM DUAL CONNECT BY LEVEL<=:v_width*:v_height
)
,cells2 AS (
SELECT cell_id,r,c,DECODE(cnt,' ',0,TO_NUMBER(cnt)) AS cnt
       ------ 如果每个方位的邻居不存在,比如边界上,把该邻居的id设为大数999999, 这样SUBSTR不报错只是返回NULL
      ,CASE WHEN r>1 AND c>1         THEN cell_id-:v_width-1 ELSE 999999 END AS n1  ---- 左上方邻居的id
      ,CASE WHEN r>1                 THEN cell_id-:v_width   ELSE 999999 END AS n2  ---- 正上方邻居的id
      ,CASE WHEN r>1 AND c<:v_width  THEN cell_id-:v_width+1 ELSE 999999 END AS n3  ---- 右上方邻居的id
      ,CASE WHEN c>1                 THEN cell_id-1          ELSE 999999 END AS n4  ---- 左边邻居的id
      ,CASE WHEN c<:v_width          THEN cell_id+1          ELSE 999999 END AS n5  ---- 右边邻居的id
      ,CASE WHEN r<:v_height AND c>1 THEN cell_id+:v_width-1 ELSE 999999 END AS n6  ---- 左下方邻居的id
      ,CASE WHEN r<:v_height         THEN cell_id+:v_width   ELSE 999999 END AS n7  ---- 正下方邻居的id
      ,CASE WHEN r<:v_height AND c<:v_width THEN cell_id+:v_width+1 ELSE 999999 END AS n8  ---- 右下方邻居的id
       ------- 用CASE计算周围的空位数,比较难看的写法
      ,CASE WHEN cnt=' ' THEN 0
            ELSE CASE WHEN r>1 THEN
                      CASE WHEN c>1 THEN DECODE(SUBSTR(:v_str,cell_id-:v_width-1,1),' ',1,0) ELSE 0 END
                     +DECODE(SUBSTR(:v_str,cell_id-:v_width,1),' ',1,0)
                     +CASE WHEN c<:v_width THEN DECODE(SUBSTR(:v_str,cell_id-:v_width+1,1),' ',1,0) ELSE 0 END
                 ELSE 0
                 END
                +CASE WHEN c>1 THEN DECODE(SUBSTR(:v_str,cell_id-1,1),' ',1,0) ELSE 0 END
                +CASE WHEN c<:v_width THEN DECODE(SUBSTR(:v_str,cell_id+1,1),' ',1,0) ELSE 0 END
                +CASE WHEN r<:v_height THEN
                      CASE WHEN c>1 THEN DECODE(SUBSTR(:v_str,cell_id+:v_width-1,1),' ',1,0) ELSE 0 END
                     +DECODE(SUBSTR(:v_str,cell_id+:v_width,1),' ',1,0)
                     +CASE WHEN c<:v_width THEN DECODE(SUBSTR(:v_str,cell_id+:v_width+1,1),' ',1,0) ELSE 0 END
                 ELSE 0
                 END
       END AS empty_cnt
  from cells c1
)
,empty_cells AS (
SELECT  --------- 找出所有空位及其邻居位置, 空位是未标数字的单元格,可能有地雷也可能没有               
       cc.*
      ,CASE WHEN n1=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n1,1))),0) END AS cnt1
      ,CASE WHEN n2=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n2,1))),0) END AS cnt2
      ,CASE WHEN n3=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n3,1))),0) END AS cnt3
      ,CASE WHEN n4=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n4,1))),0) END AS cnt4
      ,CASE WHEN n5=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n5,1))),0) END AS cnt5
      ,CASE WHEN n6=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n6,1))),0) END AS cnt6
      ,CASE WHEN n7=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n7,1))),0) END AS cnt7
      ,CASE WHEN n8=999999 THEN TO_NUMBER(NULL) ELSE NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,n8,1))),0) END AS cnt8
      ,ROWNUM empty_id ---------- 按顺序为空位取编号,递归的时候每层编号递增,按序猜测每个空位
  FROM (SELECT * FROM cells2
         WHERE cnt=0          ------- 空位
        ORDER BY CASE WHEN cell_id<=2*:v_width THEN c ELSE 9999 END  -------------- 霹雳火思路
                          ,CASE WHEN cell_id<=2*:v_width THEN r ELSE 9999 END
                          ,cell_id
       ) cc
)
,guess AS (SELECT 0 AS mine FROM DUAL UNION ALL SELECT 1 FROM DUAL)
,t(cnt_str   ---- 所有格子的计数器, 合并为一个字符串。当猜测为地雷时,就把周围8个计数器都减1
  ,m_cnt     ---- 到目前为止猜测为地雷的总数, 达到:V_CNT时就结束
  ,empty_id  ---- 目前要猜测哪个空位
  ,res       ---- 最后输出的结果。每猜出一个雷就拼一个 * 进去
  ,empty_cnt_str ---- 每个格子周围的空位计数器,即未猜测的格子数。每结束一个空位的猜测,周围的8个计数器都减1
  ) AS (
SELECT CAST(:v_str AS VARCHAR2(1000))  -------- 计数器初始化
      ,0   ------- 未猜测之前总雷数为0   
      ,1   ------- 从第一个空位开始遍历
      ,CAST(:v_str AS VARCHAR2(1000))  -------- 输出初始为原分布,在递归过程中嵌入地雷
      ,CAST(LISTAGG(CASE WHEN cnt>0 THEN TO_CHAR(empty_cnt) ELSE ' ' END)  ---- 把所有空位计数器合并为一个字符串, 标有数字的才计数
        WITHIN GROUP (ORDER BY cell_id) AS VARCHAR2(1000))
  FROM cells2
WHERE NOT EXISTS (SELECT 1 FROM cells2 WHERE cnt>empty_cnt) ---如果数字比周围的空位还多,说明题目有错,显然无解
UNION ALL
SELECT ----- 开始更新地雷计数器
       CASE WHEN guess.mine=0 THEN cnt_str---- 如果当前猜无雷,则计数器保持原样
       ELSE --------用“抠字眼”的方法把周围的计数器拿出来修改再拼回去,比较难看的写法
       CASE WHEN e.r>1 AND e.c>1 THEN SUBSTR(t.cnt_str,1,e.cell_id-:v_width-2)
                                 ||CASE WHEN e.cnt1>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n1,1)-1) ELSE SUBSTR(t.cnt_str,e.n1,1) END
                                 ||CASE WHEN e.cnt2>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n2,1)-1) ELSE SUBSTR(t.cnt_str,e.n2,1) END
                                 ||CASE WHEN e.cnt3>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n3,1)-1) WHEN e.cnt3=0 THEN SUBSTR(t.cnt_str,e.n3,1) END
                                 ||CASE WHEN e.cnt3 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n3+1,e.n4-e.n3-1) ELSE SUBSTR(t.cnt_str,e.n2+1,e.n4-e.n2-1) END
                                 ||CASE WHEN e.cnt4>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n4,1)-1) ELSE SUBSTR(t.cnt_str,e.n4,1) END
                                 ||SUBSTR(t.cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n5+1,e.n6-e.n5-1) ELSE SUBSTR(t.cnt_str,e.cell_id+1,e.n6-e.cell_id-1) END
                                             ||CASE WHEN e.cnt6>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n6,1)-1) ELSE SUBSTR(t.cnt_str,e.n6,1) END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n7,1)-1) ELSE SUBSTR(t.cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n8+1) ELSE SUBSTR(t.cnt_str,e.n7+1) END
                                   END
           WHEN e.r=1 AND e.c>1 THEN SUBSTR(t.cnt_str,1,e.cell_id-2)
                                 ||CASE WHEN e.cnt4>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n4,1)-1) ELSE SUBSTR(t.cnt_str,e.n4,1) END
                                 ||SUBSTR(t.cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n5+1,e.n6-e.n5-1) ELSE SUBSTR(t.cnt_str,e.cell_id+1,e.n6-e.cell_id-1) END
                                             ||CASE WHEN e.cnt6>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n6,1)-1) ELSE SUBSTR(t.cnt_str,e.n6,1) END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n7,1)-1) ELSE SUBSTR(t.cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n8+1) ELSE SUBSTR(t.cnt_str,e.n7+1) END
                                   END
          WHEN e.r>1 AND e.c=1 THEN SUBSTR(t.cnt_str,1,e.cell_id-:v_width-1)
                                 ||CASE WHEN e.cnt2>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n2,1)-1) ELSE SUBSTR(t.cnt_str,e.n2,1) END
                                 ||CASE WHEN e.cnt3>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n3,1)-1) WHEN e.cnt3=0 THEN SUBSTR(t.cnt_str,e.n3,1) END
                                 ||CASE WHEN e.cnt3 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n3+1,e.cell_id-e.n3-1) END
                                 ||SUBSTR(t.cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n5+1,e.n7-e.n5-1)  END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n7,1)-1) ELSE SUBSTR(t.cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n8+1) ELSE SUBSTR(t.cnt_str,e.n7+1) END
                                   END
          WHEN e.r=1 AND e.c=1 THEN SUBSTR(t.cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n5+1,e.n7-e.n5-1)  END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n7,1)-1) ELSE SUBSTR(t.cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.cnt_str,e.n8+1) ELSE SUBSTR(t.cnt_str,e.n7+1) END
                                   END
          END
       END  ----- 更新地雷计数器结束
      ,m_cnt + guess.mine ---- 总雷数递增或不变,取决于当前猜测
      ,t.empty_id+1  ------- 空单元格编号推进
      ,SUBSTR(res,1,cell_id-1)||CASE WHEN guess.mine=1 THEN '*' ELSE ' ' END||SUBSTR(res,cell_id+1) ---在输出结果中嵌入地雷
       ----------用“抠字眼”的方法把周围的计数器拿出来修改再拼回去,比较难看的写法
      ,CASE WHEN e.r>1 AND e.c>1 THEN SUBSTR(t.empty_cnt_str,1,e.cell_id-:v_width-2)
                                 ||CASE WHEN e.cnt1>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n1,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n1,1) END
                                 ||CASE WHEN e.cnt2>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n2,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n2,1) END
                                 ||CASE WHEN e.cnt3>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n3,1)-1) WHEN e.cnt3=0 THEN SUBSTR(t.empty_cnt_str,e.n3,1) END
                                 ||CASE WHEN e.cnt3 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n3+1,e.n4-e.n3-1) ELSE SUBSTR(t.empty_cnt_str,e.n2+1,e.n4-e.n2-1) END
                                 ||CASE WHEN e.cnt4>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n4,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n4,1) END
                                 ||SUBSTR(t.empty_cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.empty_cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.empty_cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n5+1,e.n6-e.n5-1) ELSE SUBSTR(t.empty_cnt_str,e.cell_id+1,e.n6-e.cell_id-1) END
                                             ||CASE WHEN e.cnt6>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n6,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n6,1) END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n7,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.empty_cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n8+1) ELSE SUBSTR(t.empty_cnt_str,e.n7+1) END
                                   END
           WHEN e.r=1 AND e.c>1 THEN SUBSTR(t.empty_cnt_str,1,e.cell_id-2)
                                 ||CASE WHEN e.cnt4>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n4,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n4,1) END
                                 ||SUBSTR(t.empty_cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.empty_cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.empty_cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n5+1,e.n6-e.n5-1) ELSE SUBSTR(t.empty_cnt_str,e.cell_id+1,e.n6-e.cell_id-1) END
                                             ||CASE WHEN e.cnt6>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n6,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n6,1) END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n7,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.empty_cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n8+1) ELSE SUBSTR(t.empty_cnt_str,e.n7+1) END
                                   END
          WHEN e.r>1 AND e.c=1 THEN SUBSTR(t.empty_cnt_str,1,e.cell_id-:v_width-1)
                                 ||CASE WHEN e.cnt2>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n2,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n2,1) END
                                 ||CASE WHEN e.cnt3>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n3,1)-1) WHEN e.cnt3=0 THEN SUBSTR(t.empty_cnt_str,e.n3,1) END
                                 ||CASE WHEN e.cnt3 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n3+1,e.cell_id-e.n3-1) END
                                 ||SUBSTR(t.empty_cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.empty_cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.empty_cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n5+1,e.n7-e.n5-1)  END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n7,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.empty_cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n8+1) ELSE SUBSTR(t.empty_cnt_str,e.n7+1) END
                                   END
          WHEN e.r=1 AND e.c=1 THEN SUBSTR(t.empty_cnt_str,e.cell_id,1)
                                 ||CASE WHEN e.cnt5>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n5,1)-1) WHEN e.cnt5=0 THEN SUBSTR(t.empty_cnt_str,e.n5,1) END
                                 ||CASE WHEN e.r=:V_HEIGHT THEN SUBSTR(t.empty_cnt_str,e.n5+1)
                                        ELSE   CASE WHEN e.cnt5 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n5+1,e.n7-e.n5-1)  END
                                             ||CASE WHEN e.cnt7>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n7,1)-1) ELSE SUBSTR(t.empty_cnt_str,e.n7,1) END
                                             ||CASE WHEN e.cnt8>0 THEN TO_CHAR(SUBSTR(t.empty_cnt_str,e.n8,1)-1) WHEN e.cnt8=0 THEN SUBSTR(t.empty_cnt_str,e.n8,1) END
                                             ||CASE WHEN e.cnt8 IS NOT NULL THEN SUBSTR(t.empty_cnt_str,e.n8+1) ELSE SUBSTR(t.empty_cnt_str,e.n7+1) END
                                   END
       end                                      
  FROM t
      ,empty_cells e
      ,guess  ---和两种猜测做笛卡尔积:0:没有地雷,1:有地雷
WHERE t.empty_id<=(SELECT MAX(empty_id) FROM empty_cells)   ------- 空位编号推进直至最大
       AND t.empty_id=e.empty_id   ------连接到empty_cells表,取当前猜测空位的坐标、邻居等信息
       AND  t.m_cnt<:v_cnt  ---- 总雷数不能溢出
       AND  CASE WHEN SUBSTR(t.res,e.n1,1)=' ' OR SUBSTR(t.cnt_str,e.n1,1)='0' THEN 0  ---- 如果邻居已经被猜为无雷,或者计数器已经饱和,必须猜0
                 ------- 如果邻居剩下未猜格子数等于未分配地雷数,必须猜1                    
                 WHEN SUBSTR(t.res,e.n1,1)='*' OR e.cnt1>0 AND SUBSTR(t.empty_cnt_str,e.n1,1)=SUBSTR(t.cnt_str,e.n1,1) THEN 1
                 ELSE guess.mine ---- 否则不限
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.res,e.n2,1)=' ' OR SUBSTR(t.cnt_str,e.n2,1)='0' THEN 0 -------邻居2-8的规则同邻居1
                 WHEN SUBSTR(t.res,e.n2,1)='*' OR e.cnt2>0 AND SUBSTR(t.empty_cnt_str,e.n2,1)=SUBSTR(t.cnt_str,e.n2,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.cnt_str,e.n3,1)='0' THEN 0  
                 WHEN e.cnt3>0 AND SUBSTR(t.empty_cnt_str,e.n3,1)=SUBSTR(t.cnt_str,e.n3,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.res,e.n4,1)=' ' OR SUBSTR(t.cnt_str,e.n4,1)='0' THEN 0  
                 WHEN SUBSTR(t.res,e.n4,1)='*' OR e.cnt4>0 AND SUBSTR(t.empty_cnt_str,e.n4,1)=SUBSTR(t.cnt_str,e.n4,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.cnt_str,e.n5,1)='0' THEN 0  ---- 从5号邻居开始为未猜测,去掉前两个规则的判断
                 WHEN e.cnt5>0 AND SUBSTR(t.empty_cnt_str,e.n5,1)=SUBSTR(t.cnt_str,e.n5,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.cnt_str,e.n6,1)='0' THEN 0  
                 WHEN e.cnt6>0 AND SUBSTR(t.empty_cnt_str,e.n6,1)=SUBSTR(t.cnt_str,e.n6,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.cnt_str,e.n7,1)='0' THEN 0
                 WHEN e.cnt7>0 AND SUBSTR(t.empty_cnt_str,e.n7,1)=SUBSTR(t.cnt_str,e.n7,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
       AND  CASE WHEN SUBSTR(t.cnt_str,e.n8,1)='0' THEN 0
                 WHEN e.cnt8>0 AND SUBSTR(t.empty_cnt_str,e.n8,1)=SUBSTR(t.cnt_str,e.n8,1) THEN 1
                 ELSE guess.mine
            END=guess.mine
)
SELECT res
FROM t
WHERE m_cnt=:v_cnt ---------- 总雷数必须符合
       AND cnt_str=TRANSLATE(:v_str,'12345678','00000000') ------ 正确的猜测结果,应该所有的计数器都为零
       AND ROWNUM=1  ---------- 有多种答案的话只选任一种
;

使用道具 举报

回复
论坛徽章:
407
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
34#
发表于 2013-12-1 11:13 | 只看该作者
newkid 发表于 2013-12-1 10:35
你发这些数据很难看懂,必须说明一下每个ID到底代表着什么。
下周我再把丑陋递归法重新改一下,看看有没 ...

133-你新改的model
134-你新改的递归

使用道具 举报

回复
论坛徽章:
37
2014年世界杯参赛球队:墨西哥
日期:2015-05-19 13:12:21懒羊羊
日期:2015-03-20 13:29:14美羊羊
日期:2015-03-21 08:13:58ITPUB长老会成员
日期:2015-05-07 15:11:10秀才
日期:2015-07-29 15:08:59
35#
发表于 2013-12-1 20:48 | 只看该作者

使用道具 举报

回复
论坛徽章:
520
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
36#
 楼主| 发表于 2013-12-2 04:44 | 只看该作者
在霹雳哥的教诲下,我又赶制了这个MODEL, 现在代码更少了,速度更快了!改进之处:去掉所有计数器,改在判断的时候即时计算;去掉最后一个规则,因为在九宫格只剩两个未确定的情况下,第三个规则已经覆盖了第四个规则。
递归写法随后再优化。

WITH cells AS (                      ------- 构造所有单元格及其坐标
   SELECT LEVEL cell_id              -------- 从左上角开始,从左到右从上到下从1开始编号
         ,CEIL(LEVEL/:v_width) r     -------- 行号,1~v_height
         ,MOD(LEVEL-1,:v_width)+1 c  -------- 列号,1~v_width
         ,NVL(TO_NUMBER(TRIM(SUBSTR(:v_str,LEVEL,1))),0) cnt -------- 该单元格周围的地雷数目
     FROM DUAL CONNECT BY LEVEL<=:v_width*:v_height
)
,guess AS (SELECT 0 AS mine FROM DUAL UNION ALL SELECT 1 FROM DUAL)
,cells2 AS (
SELECT guess.mine AS solution_id
      ,cells.cell_id
      ,cells.r
      ,cells.c
      ,cells.cnt
      ,CASE WHEN cells.cell_id=1 AND cells.cnt=0 THEN guess.mine ELSE 0 END AS guess_val
      ,COUNT(CASE WHEN cell_id>1 AND cnt=0 THEN 1 END) OVER(PARTITION BY guess.mine) AS empty_cells_cnt
  FROM cells,guess
WHERE guess.mine=0 AND SUBSTR(:v_str,1,1)<>' ' OR SUBSTR(:v_str,1,1)=' '
)
,empty_cells AS (
  SELECT r,c,ROW_NUMBER() OVER(ORDER BY CASE WHEN cell_id<=2*:v_width THEN c ELSE 9999 END
                                       ,CASE WHEN cell_id<=2*:v_width THEN r ELSE 9999 END
                                       ,cell_id
                              ) empty_id
    FROM cells
   WHERE cnt=0 AND cell_id>1  ---- 跳过(1,1)
)
,t AS (
SELECT * FROM cells2
MODEL IGNORE NAV
      REFERENCE e
         ON (SELECT * FROM empty_cells)
         DIMENSION BY (empty_id)
         MEASURES (r,c)
      MAIN m
      PARTITION BY (solution_id)
      DIMENSION BY (r,c)
      MEASURES (cnt,guess_val,r r2, c c2,empty_cells_cnt)
      RULES SEQUENTIAL ORDER
         ITERATE (10000) ----- 循环次数设为不可能达到的上限
         UNTIL (ITERATION_NUMBER >=empty_cells_cnt[1,1])
         (
          r2[1,1] = e.r[ITERATION_NUMBER+1]
         ,c2[1,1] = e.c[ITERATION_NUMBER+1]
         ,guess_val[r2[1,1],c2[1,1]]
                =CASE WHEN r2[1,1] =1 THEN
                      CASE WHEN cnt[r2[1,1],c2[1,1]-1]=0 THEN guess_val[r2[1,1],c2[1,1]-1]
                           WHEN guess_val[r2[1,1],c2[1,1]-2]+guess_val[r2[1,1]+1,c2[1,1]-2]+guess_val[r2[1,1]+1,c2[1,1]-1]<cnt[r2[1,1],c2[1,1]-1] THEN 1
                           ELSE 0
                      END
                      WHEN c2[1,1] =1 THEN
                      CASE WHEN cnt[r2[1,1]-1,c2[1,1]]=0 THEN guess_val[r2[1,1]-1,c2[1,1]]
                           WHEN guess_val[r2[1,1]-2,c2[1,1]]+guess_val[r2[1,1]-2,c2[1,1]+1]+guess_val[r2[1,1]-1,c2[1,1]+1]<cnt[r2[1,1]-1,c2[1,1]] THEN 1
                           ELSE 0
                      END
                      WHEN cnt[r2[1,1]-1,c2[1,1]-1]=0 THEN guess_val[r2[1,1]-1,c2[1,1]-1]
                      WHEN guess_val[r2[1,1]-2,c2[1,1]-2]+guess_val[r2[1,1]-2,c2[1,1]-1]+guess_val[r2[1,1]-2,c2[1,1]]
                          +guess_val[r2[1,1]-1,c2[1,1]-2]+guess_val[r2[1,1]-1,c2[1,1]]
                          +guess_val[r2[1,1],c2[1,1]-2]+guess_val[r2[1,1],c2[1,1]-1]<cnt[r2[1,1]-1,c2[1,1]-1]
                      THEN 1
                      ELSE 0
                 END
         )
)
SELECT res
  into :v_result
  FROM (
SELECT LISTAGG(CASE WHEN cnt=0 THEN CASE WHEN guess_val=1 THEN '*' ELSE ' ' END ELSE TO_CHAR(cnt) END) WITHIN GROUP (ORDER BY r,c) as res
FROM t
GROUP BY solution_id
HAVING SUM(guess_val)=:v_cnt
)
WHERE ROWNUM=1
;

使用道具 举报

回复
论坛徽章:
407
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
37#
发表于 2013-12-2 07:14 | 只看该作者
34楼确实很快而且正确
ID             1     2     3     4     5     6     7     8     9    10    11    12    13    14    15   100
---------- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
136          .05   .01     0     0   .01     0   .02   .04   .03   .04   .02   .04   .04   .02   .01  4.17

使用道具 举报

回复
求职 : 数据库开发
论坛徽章:
16
2013年新春福章
日期:2013-02-25 14:51:24美羊羊
日期:2015-03-04 14:54:27凯迪拉克
日期:2014-11-20 09:13:05马上有钱
日期:2014-02-18 16:49:312014年新春福章
日期:2014-02-18 16:49:31优秀写手
日期:2013-12-18 09:29:13法拉利
日期:2013-10-18 16:22:26ITPUB社区12周年站庆徽章
日期:2013-10-08 17:44:42ITPUB社区12周年站庆徽章
日期:2013-10-08 15:00:34ITPUB社区12周年站庆徽章
日期:2013-10-08 14:54:39
38#
发表于 2013-12-2 07:56 | 只看该作者
大师,好!我的头像能说明问题了

使用道具 举报

回复
论坛徽章:
520
奥运会纪念徽章:垒球
日期:2008-09-15 01:28:12生肖徽章2007版:鸡
日期:2008-11-17 23:40:58生肖徽章2007版:马
日期:2008-11-18 05:09:48数据库板块每日发贴之星
日期:2008-11-29 01:01:02数据库板块每日发贴之星
日期:2008-12-05 01:01:03生肖徽章2007版:虎
日期:2008-12-10 07:47:462009新春纪念徽章
日期:2009-01-04 14:52:28数据库板块每日发贴之星
日期:2009-02-08 01:01:03生肖徽章2007版:蛇
日期:2009-03-09 22:18:532009日食纪念
日期:2009-07-22 09:30:00
39#
 楼主| 发表于 2013-12-3 06:49 | 只看该作者
下面来介绍一种来自超级简洁且高效的解题思路,来自霹雳火pilisky:

观察如下的阵形:
ABC
DEf
Ghi

其中,大写的ABCDEG是已经确定的单元格,其中可能有数字,可能有空位,所有ABCDEG中空位都已经被确定为“有雷”或者“无雷”。
注意这里的“确定”指的是根据先前对其他空位的猜测得出的结论,并不一定是正确的,其正确性我们在最后进行验证。

而小写的fhi则是有待确定的单元格,其中标有数字的单元格当然不用确定。未标数字的空位可能是一个/两个/三个。

现在考察单元格E。

1. 如果E为空位,那么根据我们前面的假设,E已经被确定了。那么,根据前面的前两条推理规则(空位之间的传染性),我们可以确定,fhi中的空位具有和E一样的值。

2. 如果E是标有数字的单元格,那么就存在两种情况:
   a.已经确定的周边地雷总数<数字E
     此时,fhi中所有空位都必须确定为地雷。因为fhi这三个位置是相邻的,不存在这样的可能,即其中一个空位为地雷而另一个却不是。
   b.已经确定的周边地雷总数>=数字E
     此时,所有地雷都已找到,fhi中所有空位都必须确定为无雷。这是显而易见的。

所以,根据"ABCDEG已经确定"这个前提,我们可以确定fhi中所有的空位值。

以上阵形完全适用于边界情况,边界无非就是有些邻居不存在,不存在的邻居当然无雷,不影响数字E的推理。几种变型举例如下:
变型1: 当阵形处于上边界,变成这样:
DEf
Ghi
此时fhi可以根据同样的规则从E推断出来。

变型2: 当阵形处于下边界,变成这样:
ABC
DEf
此时f可以根据同样的规则从E推断出来。

变型3: 当阵形处于左边界,变成这样:
BC
Ef
hi
此时fhi可以根据同样的规则从E推断出来。

变型4: 当阵形处于右边界,变成这样:
AB
DE
Gh
此时h可以根据同样的规则从E推断出来。

变型5: 当阵形处于左上角边界,变成这样:
Ef
hi
此时fhi可以根据同样的规则从E推断出来。

其他变型无非也就是上述的组合,都可以通过E推理出来。

上述阵形的确认方法已经证明完毕,现在我们就要利用它来推广到所有阵形。可以用数学归纳法。

以左上角为起点,此时相当于变型5:
Ef
hi

如果E有数字,那么就只有一种确定解。
如果E为空位,不妨“有雷”“无雷”都尝试一下,看看最后哪种假设是正确的。

于是,以左上角E为起点,我们能够确定fhi的空位值。

沿着边界往外推理:
Efj
hik
这时候,就相当于上述的变型1, 那么j,k可以推理出来。

继续往外推:
Efjlnpr
hikmoqs .....

直至第1,2行全部推理完毕。

从第三行开始,假设我们需要推理下属的1,2位置:
Ef
hi
12

这相当于上述的变型3, 位置1,2可以从h推理出来。
往右边推:
Efjlnpr
hikmoqs .....
123456....

然后继续第四行,第五行,....直至整个阵形推理完毕。

使用道具 举报

回复
论坛徽章:
407
紫蛋头
日期:2012-05-21 10:19:41迷宫蛋
日期:2012-06-06 16:02:49奥运会纪念徽章:足球
日期:2012-06-29 15:30:06奥运会纪念徽章:排球
日期:2012-07-10 21:24:24鲜花蛋
日期:2012-07-16 15:24:59奥运会纪念徽章:拳击
日期:2012-08-07 10:54:50奥运会纪念徽章:羽毛球
日期:2012-08-21 15:55:33奥运会纪念徽章:蹦床
日期:2012-08-21 21:09:51奥运会纪念徽章:篮球
日期:2012-08-24 10:29:11奥运会纪念徽章:体操
日期:2012-09-07 16:40:00
40#
发表于 2013-12-3 07:27 | 只看该作者
newkid 发表于 2013-12-3 06:49
下面来介绍一种来自超级简洁且高效的解题思路,来自霹雳火pilisky:

观察如下的阵形:

好文。

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

TOP技术积分榜 社区积分榜 徽章 团队 统计 知识索引树 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 未成年人举报专区 
京ICP备16024965号-8  北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表