ITPUB论坛-中国最专业的IT技术社区

 
 注册
热搜:
查看: 48519|回复: 36

[精华] ITPUB第3届“盛拓传媒杯”SQL数据库编程大赛第1题参考解题思路

[复制链接]
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
跳转到指定楼层
1#
发表于 2015-12-19 05:34 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 lastwinner 于 2015-12-19 16:07 编辑

活动见:/thread-1943911-1-1.html
第2题及附加题: /thread-2048984-1-1.html

第一题:
最自然的解题思路,就是模拟真人下棋的情况,而SQL的优势在于它不会放过每个可能下子的位置,最终自然会得到所有的结局。从空棋盘开始,尝试在每个空位下子,每下一子就查看是否出现胜局,如果胜负已分则不再继续。所有空位已满也不再继续。

递归WITH子查询允许你在递归部分进行很多灵活的判断和计算,我们可以在这个递归部分拼出当前棋局、下子的顺序,以及判断胜负。

为了判断胜负,可以事先把所有获胜的三子连线情况都找出来,然后每下一步都进行匹配。匹配方式也有多种思路,我偏爱用BITAND的方法,即把棋盘的每一个位置用二进制的一位来表示,空位为0, 有子则为1,这样用POWER(2,9)就可以表示整个棋盘的占位情况,而每种获胜的情况则是三个二进制数相加;用BITAND可以得知某一棋局在三个获胜位是否全部都有棋子。

第一步先来生成棋盘布局,按要求把棋盘的位置编号1-9, 同时算出这个位子的二进制表示,及其行列坐标,用如下的子查询实现:
WITH
cells AS (SELECT LEVEL pos,POWER(2,LEVEL-1) b,CEIL(LEVEL/3) r,MOD(LEVEL-1,3)+1 c FROM DUAL CONNECT BY LEVEL<=9)
-- 获胜情况总共才八种(三横三纵,加上两个对角线),可以用枚举的方法写出来。如果想要做得灵活一点,以便扩展到M,N,K的情况,可以用如下递归思路:
-- 选任意一个棋子作为起点;
-- 从当前棋子向四个方向各走一步,新加入的棋子的二进制位也加入到总和;
-- 走三步(得到三个棋子)则停止。
--
-- 用递归WITH实现如下:
,w (win_bits,cnt,r,c,direction) as (
--- win_bits表示三个连续棋子的二进制之和; cnt表示累计几个棋子,满三个即停;r,c为行列坐标,direction表示哪个方向
SELECT b,1,r,c,direction FROM cells,(SELECT LEVEL direction FROM DUAL CONNECT BY LEVEL<=4) ----从棋盘m任选一点开始,和四种方向做笛卡尔积
UNION ALL
SELECT w.win_bits+cells.b,w.cnt+1,cells.r,cells.c ,w.direction
FROM w,cells
WHERE w.cnt<3 ----满三个即停止
      ----- 下面从四个方向来加入棋子。并不是每个起点都能得到连续三个棋子,下面的坐标关系自然会过滤掉不合格的
      AND (direction=1 AND cells.c=w.c AND cells.r=w.r+1 -----如果方向1, 则加入同列、下一行的位子
           OR direction=2 AND cells.r=w.r AND cells.c=w.c+1 -----如果方向2, 则加入同行、下一列的位子
           OR direction=3 AND cells.r=w.r+1 AND cells.c=w.c+1 -----如果方向3, 则加入下一行、下一列的位子(右下方)
           OR direction=4 AND cells.r=w.r+1 AND cells.c=w.c-1 -----如果方向4, 则加入下一行、上一列的位子(左下方)
           )
)
,win as (select win_bits from w where cnt=3) ---- 选出那些走满三步的记录,这里有8个二进制数字,代表了8种获胜布局
--- 下面开始用递归WITH来模拟所有可能的棋局。所需要的数据结构如下:
,t(board  ----- 到目前为止所有X,O的分布
  ,x ------- X下过了哪些位置,用二进制之和表示
  ,o ------- O下过了哪些位置,用二进制之和表示
  ,step ----- 当前走了几步(双方一共下了几子)
  ,winner ----- 如果胜负已分,在这里标出
  ,moves ----- 到目前为止所有下子顺序,即棋谱
  )
AS (
--------- 递归的起点是从X下第一子开始
SELECT CAST(RPAD('-',pos-1,'-')||'X'||RPAD('-',9-pos,'-') AS VARCHAR2(9)) board  ----- 把X的位置拼入空棋盘
     ,b X
     ,0 O
     ,1
     ,CAST(NULL AS VARCHAR2(1))
     ,CAST(pos AS VARCHAR2(10))
FROM cells
UNION ALL
------- 下面是递归的部分,在这里算出所有的变化
SELECT SUBSTR(t.board,1,cells.pos-1)  ------ 把选中的下一个棋子按照其位置拼到棋盘中去。其位置即m.pos表示的1-9的整数
       ||CASE WHEN MOD(t.step,2)=0 THEN 'X' ELSE 'O' END ----- 根据当前步数算出下一个子应该是X或者O
       ||SUBSTR(t.board,cells.pos+1)
      ,CASE WHEN MOD(t.step,2)=0 THEN t.x+cells.b ELSE t.x END ---- 如果下一子是X, 把其二进制叠加到t.x,否则保持原样
      ,CASE WHEN MOD(t.step,2)=1 THEN t.o+cells.b ELSE t.o END ---- 对O的处理,方法同上
      ,t.step+1
      ,CASE WHEN MOD(t.step,2)=0
            THEN (SELECT 'X' FROM win WHERE BITAND(t.x+cells.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 如果轮到X走子,用BITAND判断走后是否出现胜局
            ELSE (SELECT 'O' FROM win WHERE BITAND(t.o+cells.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 判断O是否获胜,方法同X
       END           
      ,moves||cells.pos ---- 把下一个子的落子情况拼到棋谱中
  FROM t JOIN cells ON BITAND(t.x+t.o,cells.b)=0 ----- 将t和9个棋位连接,只要该位子还没有棋子就可以走, BITAND为零表示该位置为空
WHERE t.winner IS NULL ----- 胜负未分
)
---- 递归结束,找出所有叶子节点(胜负已分,或者和棋)
--SELECT WINNER,COUNT(*) FROM (
SELECT moves
      ,board
      ,NVL(winner,'D') AS WINNER
FROM T
WHERE WINNER IS NOT NULL OR STEP=9

) GROUP BY WINNER;
----SELECT WINNER,COUNT(*) FROM T WHERE WINNER IS NOT NULL OR STEP=9 GROUP BY WINNER;

以上就是以最直接思路实现的版本,它确实能够找出所有的棋局,但还有优化余地。
有很多的棋局是彼此对称的,你可以把一个棋局进行各种旋转翻转变换得到其他棋局,而不需要真正去“下完”那些棋局。
在递归过程中,越早剪枝,所节省的计算量就越多。观察第一步的下法,总共有9种可能,而其实选择1和选择3,7,9的棋局是对称的,通过把起点为1的棋局进行变换,就可以得到起点分别为3,7,9的棋局;而2和4,6,8也是对称的。所以,实际上所有棋局都可以从1,2,5这三个点开始,我们通过把第一步的位置限定在1,2,5,达到剪枝的目的。
以5为起点的棋局也可以去除重复。因为5是整个棋盘的轴心,第一子下在5之后,第二子其实只需考虑1,2两种下法,其他的也全部是对称的,可以推导出来。所以在第二步也可以有一个剪枝操作。

所以,递归的起点条件调整为:
WHERE cells.pos IN (1,2,5)

递归的WHERE条件调整为:

WHERE t.winner IS NULL ----- 胜负未分
       ---- 通过限制下子位置进行剪枝
       AND (t.moves='5' AND cells.pos IN (1,2) ---- 如果第一子下在5, 则限制第二子只能走在1或2
            OR t.moves<>'5' ----- 如果第一子下的不是5(而是1或2)则第二子没有位置限制
           )

这样得到的棋局其实只有四分之一,效率确实提高了很多。另外四分之三的棋局,可以通过顺时针旋转90度、180度、270得到。
棋谱的旋转其实就是1-9这九个数字的变换,比如顺时针转90度,1会变成3,2会变成6,3会变成9,......
1-9旋转之后的9个对应数字为:369258147
类似的,旋转180度的9个对应数字为:987654321,旋转270度的9对应个数字为:741852963
我们可以使用TRANSLATE来实现这种旋转变换,而上述的数字串则称为旋转模版。
棋局的旋转也是类似,但略有不同。棋局不是由数字构成,而是X,O,-构成的字符串,所以你不能将棋局作为TRANSLATE的第一个参数,而是应该作第三个参数。

比如O-XOXOXX-这个棋局,顺时针旋转90度,那么第一位的'O'应该调整到第3位,第二位的'-'应该调整到第6位,第三位的'X'应该调整到第9位,......
TRANSLATE('123456789','369258147','O-XOXOXX-')
第二个参数和第三个参数的各位之间正是一一对应的,翻译之后则按第一个参数的顺序来排列。所以,'3'对应的'O'翻译后被排到第3位,'6'对应的'-'被排到第6位,......

加入了剪枝和旋转变换之后的SQL如下:

WITH
cells AS (SELECT LEVEL pos,POWER(2,LEVEL-1) b,CEIL(LEVEL/3) r,MOD(LEVEL-1,3)+1 c FROM DUAL CONNECT BY LEVEL<=9)
-- 获胜情况总共才八种(三横三纵,加上两个对角线),可以用枚举的方法写出来。如果想要做得灵活一点,以便扩展到M,N,K的情况,可以用如下递归思路:
-- 选任意一个棋子作为起点;
-- 从当前棋子向四个方向各走一步,新加入的棋子的二进制位也加入到总和;
-- 走三步(得到三个棋子)则停止。
--
-- 用递归WITH实现如下:
,w (win_bits,cnt,r,c,direction) as (
--- win_bits表示三个连续棋子的二进制之和; cnt表示累计几个棋子,满三个即停;r,c为行列坐标,direction表示哪个方向
SELECT b,1,r,c,direction FROM cells,(SELECT LEVEL direction FROM DUAL CONNECT BY LEVEL<=4) ----从棋盘m任选一点开始,和四种方向做笛卡尔积
UNION ALL
SELECT w.win_bits+cells.b,w.cnt+1,cells.r,cells.c ,w.direction
FROM w,cells
WHERE w.cnt<3 ----满三个即停止
      ----- 下面从四个方向来加入棋子。并不是每个起点都能得到连续三个棋子,下面的坐标关系自然会过滤掉不合格的
      AND (direction=1 AND cells.c=w.c AND cells.r=w.r+1 -----如果方向1, 则加入同列、下一行的位子
           OR direction=2 AND cells.r=w.r AND cells.c=w.c+1 -----如果方向2, 则加入同行、下一列的位子
           OR direction=3 AND cells.r=w.r+1 AND cells.c=w.c+1 -----如果方向3, 则加入下一行、下一列的位子(右下方)
           OR direction=4 AND cells.r=w.r+1 AND cells.c=w.c-1 -----如果方向4, 则加入下一行、上一列的位子(左下方)
           )
)
,win as (select win_bits from w where cnt=3) ---- 选出那些走满三步的记录,这里有8个二进制数字,代表了8种获胜布局
--- 下面开始用递归WITH来模拟所有可能的棋局。所需要的数据结构如下:
,t(board  ----- 到目前为止所有X,O的分布
  ,x ------- X下过了哪些位置,用二进制之和表示
  ,o ------- O下过了哪些位置,用二进制之和表示
  ,step ----- 当前走了几步(双方一共下了几子)
  ,winner ----- 如果胜负已分,在这里标出
  ,moves ----- 到目前为止所有下子顺序,即棋谱
  )
AS (
--------- 递归的起点是从X下第一子开始
SELECT CAST(RPAD('-',pos-1,'-')||'X'||RPAD('-',9-pos,'-') AS VARCHAR2(9)) board  ----- 把X的位置拼入空棋盘
     ,b X
     ,0 O
     ,1
     ,CAST(NULL AS VARCHAR2(1))
     ,CAST(pos AS VARCHAR2(10))
FROM cells
WHERE cells.pos IN (1,2,5)
UNION ALL
------- 下面是递归的部分,在这里算出所有的变化
SELECT SUBSTR(t.board,1,cells.pos-1)  ------ 把选中的下一个棋子按照其位置拼到棋盘中去。其位置即m.pos表示的1-9的整数
       ||CASE WHEN MOD(t.step,2)=0 THEN 'X' ELSE 'O' END ----- 根据当前步数算出下一个子应该是X或者O
       ||SUBSTR(t.board,cells.pos+1)
      ,CASE WHEN MOD(t.step,2)=0 THEN t.x+cells.b ELSE t.x END ---- 如果下一子是X, 把其二进制叠加到t.x,否则保持原样
      ,CASE WHEN MOD(t.step,2)=1 THEN t.o+cells.b ELSE t.o END ---- 对O的处理,方法同上
      ,t.step+1
      ,CASE WHEN MOD(t.step,2)=0
            THEN (SELECT 'X' FROM win WHERE BITAND(t.x+cells.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 如果轮到X走子,用BITAND判断走后是否出现胜局
            ELSE (SELECT 'O' FROM win WHERE BITAND(t.o+cells.b,win.win_bits)=win.win_bits AND ROWNUM=1) ---- 判断O是否获胜,方法同X
       END           
      ,moves||cells.pos ---- 把下一个子的落子情况拼到棋谱中
  FROM t JOIN cells ON BITAND(t.x+t.o,cells.b)=0 ----- 将t和9个棋位连接,只要该位子还没有棋子就可以走, BITAND为零表示该位置为空
WHERE t.winner IS NULL ----- 胜负未分
       ---- 通过限制下子位置进行剪枝
       AND (t.moves='5' AND cells.pos IN (1,2) ---- 如果第一子下在5, 则限制第二子只能走在1或2
            OR t.moves<>'5' ----- 如果第一子下的不是5(而是1或2)则第二子没有位置限制
           )
)
----递归结束后,取出胜负已分的棋局以及和棋来进行对称变换
,ttt AS (SELECT * FROM t where winner IS NOT NULL OR step=9)
,TP AS ( ------- 四种旋转模版
SELECT /*+ materialize */ '123456789' AS tpl_org,tpl_str FROM (
     SELECT '123456789' AS tpl_str FROM DUAL -----  原样
     UNION ALL SELECT '369258147' FROM DUAL -----  顺时针90度
     UNION ALL SELECT '987654321' FROM DUAL -----  顺时针180度
     UNION ALL SELECT '741852963' FROM DUAL -----  顺时针270度
    )
)        
--SELECT WINNER,COUNT(*) FROM (
SELECT --------对递归结果进行旋转变换,以得到完整的所有棋局
       TRANSLATE(ttt.moves,tpl_org,tpl_str) moves
      ,TRANSLATE(tpl_org,tpl_str,ttt.board) board
      ,NVL(ttt.winner,'D') AS WINNER
FROM tp,ttt
)
GROUP BY WINNER;

在比赛结束后的某一天,好钻研的OO给我发来一个邮件,就是这个链接里面提到的文章:
/thread-2048856-1-1.html

里面提到了一种判断胜局的巧妙方法,即采用三阶幻方的思路。幻方看起来是这样:
492
357
816

众所周知,幻方在纵横斜向上的和都是相同的,所以我们只需把九个数字重新编排一下,然后在递归过程中判断新加入的数字和已有的任意两个数字之和是否为15,就可以知道胜局是否已经出现。因为井字棋的一方最多下五个子,所以要和前面已下的四个子进行组合,总共有C(4,2)=6种,还是可以接受的。使用这个判断方法后,代码可以少写很多,效率也提高了一倍以上。

我在评审答案的过程中还学习到一个从棋谱(MOVES)倒推棋局(BOARD)的巧妙方法,只需两个TRANSLATE转换就可以完成:
TRANSLATE(TRANSLATE('123456789',moves,'XOXOXOXOX'),'123456789','---------')

MOVES的下子顺序固定为XOXOXOXOX,通过第一个TRANSLATE把X,O安放到该去的位置,最后再把所有不在MOVES中的数字转换成'-',就得到了棋局。

对称棋局的消除和再生成和前一种写法一样。

WITH
cells AS (SELECT LEVEL pos FROM DUAL CONNECT BY LEVEL<=9)
--- 下面开始用递归WITH来模拟所有可能的棋局。所需要的数据结构如下:
,t(step ----- 当前走了几步(双方一共下了几子)
  ,winner ----- 如果胜负已分,在这里标出
  ,moves ----- 到目前为止所有下子顺序,即棋谱, 此处用的是幻方的排列方式492357816,递归结束后再变回来
  )
AS (
--------- 递归的起点是从X下第一子开始
SELECT 1
     ,CAST(NULL AS VARCHAR2(1))
     ,CAST(pos AS VARCHAR2(9))
FROM cells
WHERE cells.pos IN (4,9,5)
UNION ALL
------- 下面是递归的部分,在这里算出所有的变化
SELECT t.step+1
      ,CASE WHEN t.step>=4 AND ----- 第五步开始才需要判断胜负
            15-cells.pos IN (SUBSTR(t.moves,-2,1)+SUBSTR(t.moves,-4,1) --- 当前要新加入的棋子,和前四子的任意两两组合求和,如果为15则出现胜局
                            ,SUBSTR(t.moves,-2,1)+SUBSTR(t.moves,-6,1)
                            ,SUBSTR(t.moves,-2,1)+SUBSTR(t.moves,-8,1)
                            ,SUBSTR(t.moves,-4,1)+SUBSTR(t.moves,-6,1)
                            ,SUBSTR(t.moves,-4,1)+SUBSTR(t.moves,-8,1)
                            ,SUBSTR(t.moves,-6,1)+SUBSTR(t.moves,-8,1)
                            )
            THEN DECODE(MOD(t.step,2),0,'X','O') ---- 如果胜局出现,根据步数的奇偶性判断哪一方获胜
       END           
      ,moves||cells.pos ---- 把下一个子的落子情况拼到棋谱中
  FROM t JOIN cells ON INSTR(t.moves,cells.pos)=0 ----- 将t和9个棋位连接,只要该位子还没有棋子就可以走
WHERE t.winner IS NULL ----- 胜负未分
       ---- 通过限制下子位置进行剪枝
       AND (t.moves='5' AND cells.pos IN (4,9) ---- 如果第一子下在5, 则限制第二子只能走在4或9
            OR t.moves<>'5' ----- 如果第一子下的不是5(而是4或9)则第二子没有位置限制
           )
)
----递归结束后,取出胜负已分的棋局以及和棋,并把幻方的编号转换为原来的编号
,ttt AS (SELECT TRANSLATE(moves,'492357816','123456789') AS moves,winner FROM t where winner IS NOT NULL OR step=9)
,TP AS ( ------- 四种旋转模版
SELECT /*+ materialize */ '123456789' AS tpl_org,tpl_str FROM (
     SELECT '123456789' AS tpl_str FROM DUAL -----  原样
     UNION ALL SELECT '369258147' FROM DUAL -----  顺时针90度
     UNION ALL SELECT '987654321' FROM DUAL -----  顺时针180度
     UNION ALL SELECT '741852963' FROM DUAL -----  顺时针270度
    )
)        
SELECT WINNER,COUNT(*) FROM (
SELECT moves,TRANSLATE(TRANSLATE('123456789',moves,'XOXOXOXOX'),'123456789','---------') board,winner
  FROM (
         SELECT --------对递归结果进行旋转变换,以得到完整的所有棋局
                TRANSLATE(ttt.moves,tpl_org,tpl_str) moves
               ,NVL(ttt.winner,'D') AS WINNER
         FROM tp,ttt
       )
)
GROUP BY WINNER;


下面来介绍一种不用递归WITH的10g版本。
11g的递归WITH允许你在递归过程中判断是否出现胜局,如果出现了就及时停止递归。而10G只能够用CONNECT BY的功能求9个位置的全排列,事后再过滤掉那些无效的棋局,比如在一方获胜之后还继续下子的情况。因为不能在递归过程中判断胜负,所以BITAND的方法就不能用了,改用获胜棋子的出现顺序来判断:
如果X获胜,则X的致胜一子必须是本局的最后落子,而且X的总棋子数比O多1;
如果O获胜,则O的致胜一子必须是本局的最后落子,而且X的总棋子数和O相同。

8种胜局的位置枚举出来如下:123,456,789,147,258,369,159,357

CONNECT BY也有一定的剪枝功能,所以我们还是可以限制起点,然后再用旋转的办法来求出其他对称的棋局。

with
win as (
SELECT substr(wins,1,1) w1,substr(wins,2,1) w2,substr(wins,3,1) w3
       -----每次截取三个字符作为获胜的三子位置,然后用SUBSTR拆成三个列
from (select REGEXP_SUBSTR('123,456,789,147,258,369,159,357','[^,]+',1,LEVEL) wins from dual connect by level<=8)
)
,boards AS (
------ 对9个数字进行全排列,得到所有可能的棋谱,包括未完的、已结束的、无效的
------ X和O所有走位分别求出来,随后会用来判断胜局是否出现
SELECT REPLACE(SYS_CONNECT_BY_PATH(CASE WHEN MOD(LEVEL,2)=1 THEN n END,','),',') X
      ,REPLACE(SYS_CONNECT_BY_PATH(CASE WHEN MOD(LEVEL,2)=0 THEN n END,','),',') O
      ,REPLACE(SYS_CONNECT_BY_PATH(n,','),',') moves
      ,LEVEL step
  FROM (select level n from dual connect by level<=9)
START WITH n IN (1,2,5) ---- 如果是空棋盘,限制第一步走位只能在1,2,5
CONNECT BY NOCYCLE n<>PRIOR n
       AND LEVEL<=9
       AND (LEVEL=2 AND PRIOR n=5 AND n IN (1,2) ---- 如果第一子下在5, 则限制第二子只能走在1或2
            OR LEVEL=2 AND PRIOR n<>5  ----- 如果第一子下的不是5(而是1或2)则第二子没有位置限制
            OR LEVEL>2 ---从第三子开始没有任何限制
           )
)
,b2 AS (
------ 事后对所有棋谱进行加工,把出现胜局的一方的最后致胜位置找出来。例如某一方走出了258的连线, 则看看最后出现的子是2或者5或者8
------ INSTR表示在第几步下了这个子,GREATEST找出最后的落子步数
------ 如果某一方同时出现多个胜局(比如十字架),则用MIN取最先出现的胜局的最后一步。
       SELECT b.*
              -------- 用标量子查询来找出致胜的最后一子
             ,(SELECT MIN(GREATEST(INSTR(b.x,w1),INSTR(b.x,w2),INSTR(b.x,w3)))
                 FROM win
                WHERE INSTR(b.x,w1)>0 AND INSTR(b.x,w2)>0 AND INSTR(b.x,w3)>0 ----- 胜局的三个位置全部有子
               ) AS x_win
             ,(SELECT MIN(GREATEST(INSTR(b.o,w1),INSTR(b.o,w2),INSTR(b.o,w3)))
                 FROM win
                WHERE INSTR(b.o,w1)>0 AND INSTR(b.o,w2)>0 AND INSTR(b.o,w3)>0
               ) AS o_win
         FROM boards b
)
,ttt AS (
----- 利用上面b2的计算结果来过滤掉无效棋局。
SELECT B2.*
      ,CASE WHEN x_win is not null then 'X' when o_win is not null then 'O' ELSE 'D' END AS WINNER
       ----------根据棋谱的下子顺序把棋局拼出来。
      ,TRANSLATE(TRANSLATE('123456789',moves,'XOXOXOXOX'),'123456789','---------') board
FROM b2
WHERE (----- 如果X出现胜局,则O不可有胜局;X的致胜一子必须是最后的一步;X必须比O多一子
       x_win>0 AND o_win IS NULL AND x_win=LENGTH(x) AND LENGTH(x)=LENGTH(o)+1
       ----- 如果O出现胜局,则X不可有胜局;O的致胜一子必须是最后的一步;X必须和O棋子数相同
       OR o_win>0 AND x_win IS NULL AND o_win=LENGTH(o) AND LENGTH(x)=LENGTH(o)
       ----- 如果双方都没有胜局且步数为9,则为和棋
       OR x_win is null and o_win is null and step=9
       )
)
,TP AS ( ------- 四种旋转模版
SELECT /*+ materialize */ '123456789' AS tpl_org,tpl_str FROM (
     SELECT '123456789' AS tpl_str FROM DUAL -----  原样
     UNION ALL SELECT '369258147' FROM DUAL -----  顺时针90度
     UNION ALL SELECT '987654321' FROM DUAL -----  顺时针180度
     UNION ALL SELECT '741852963' FROM DUAL -----  顺时针270度
    )
)        
--SELECT WINNER,COUNT(*) FROM (
SELECT --------对递归结果进行旋转变换,以得到完整的所有棋局
       TRANSLATE(ttt.moves,tpl_org,tpl_str) moves
      ,TRANSLATE(tpl_org,tpl_str,ttt.board) board
      ,NVL(ttt.winner,'D') AS WINNER
FROM tp,ttt;
)
GROUP BY WINNER;

评审过程中还发现一种判断胜局的巧妙思路,写起来代码更少,速度更快,特此介绍一下:

with b as (
select level||'' n, decode(level, 1,111,2,1001,3,10100001,4,10010,5,111100,6,10010000,7,1100010,8,1001000,11000100) v from dual connect by level<=9
),
r(p, xp, op, i, w) as (
select n, v, 0, 0, ''
from b where n in (1,2,5)
union all
select p||n, decode(i, 1, v, 0)+xp, decode(i, 1, 0, v)+op, mod(i+1, 2),
case when instr(decode(i, 1, v, 0)+xp, '3')>0 then 'X' else case when instr(decode(i, 1, 0, v)+op, '3')>0 then 'O' else null end end
from r, b
where instr(r.p, n)=0 and (length(p)>1 or p in (1,2) or n in (1,2))
and w is null
),
ttt as(
select p moves, translate(translate('123456789', p, 'XOXOXOXOX'), '123456789', '---------')board
      ,nvl(w, 'D') winner
from r
where w is not null or length(p)=9
)
select moves,
       translate(translate('123456789', moves, 'XOXOXOXOX'), '123456789', '---------') board,
       winner
  from (select translate(moves,'123456789',decode(n,1,'987654321',2,'369258147',3,'741852963',4,'123456789')) moves,winner
          from ttt,b
          where n<=4
       )
;

上面的去除对称部分在原作中没有出现,是OO加上去的。

作者很巧妙地把9个数字用一种8位十进制的方式进行编码,这种编码的每一位代表8种胜局中的一种,如果某个格子出现在胜局中则为1,否则为0, 以1号格子为例,它出现在纵横斜线三种胜局中,所以编码之后有三个1。那么在递归过程中,只需对这个编码进行累加,然后看看累加和的哪一位是否出现了'3',如果有3则说明已经有一方获胜。


论坛徽章:
8
玉兔
日期:2015-11-16 10:18:00铁扇公主
日期:2015-10-27 21:47:42九尾狐狸
日期:2015-12-11 22:31:15
2#
发表于 2015-12-19 07:26 | 只看该作者
本帖最后由 lugionline 于 2015-12-19 07:51 编辑

没仔细看每一步,但我们的思路是一样的,构造胜利点的方式略显复杂,旋转的技巧不错。

幸好没提前贴M,否则还以为你抄袭了呢, 连你的t表结构都和我的STATE一样

使用道具 举报

回复
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
3#
 楼主| 发表于 2015-12-19 07:58 | 只看该作者
lugionline 发表于 2015-12-19 07:26
没仔细看每一步,但我们的思路是一样的,构造胜利点的方式略显复杂,旋转的技巧不错。

幸好没提前贴M,否 ...

你是说我判断胜负的方法过于复杂?现在我看到的最好方法是在第一贴末尾提到的某人的8位十进制表示法,但是用来对付MNK就有点不够,因为ORACLE一个NUMBER只能表示38位,很快就捉襟见肘了。
你有更好的方法就秀一下呗!

使用道具 举报

回复
论坛徽章:
8
玉兔
日期:2015-11-16 10:18:00铁扇公主
日期:2015-10-27 21:47:42九尾狐狸
日期:2015-12-11 22:31:15
4#
发表于 2015-12-19 08:18 | 只看该作者
本帖最后由 lugionline 于 2015-12-19 08:30 编辑
newkid 发表于 2015-12-19 07:58
你是说我判断胜负的方法过于复杂?现在我看到的最好方法是在第一贴末尾提到的某人的8位十进制表示法,但是 ...

没有,我是说算那个win表,但是好吧,也只能这样,一个SQL里没法共用函数

对了,你的win包括了所有的胜利点,所以每次判断的时候其实要和所有这些bit检查(3*3 是8个,3*3 2子是12个,棋盘大的时候会更多点),但是如果我们已经知道要下在 r,c位置的话,其实只要判断在r,c点的那些(4个),这种情况要少一些,不过要先检索出r,c点的win,用SQL我不清楚,但是不用SQL应当用第二种更好点

使用道具 举报

回复
论坛徽章:
480
榜眼
日期:2015-09-09 10:34:21秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12秀才
日期:2015-11-23 10:03:12状元
日期:2015-11-23 10:04:09举人
日期:2015-11-23 10:04:09
5#
 楼主| 发表于 2015-12-19 11:56 | 只看该作者
lugionline 发表于 2015-12-19 08:18
没有,我是说算那个win表,但是好吧,也只能这样,一个SQL里没法共用函数

对了,你的win包括了所有的胜 ...

你这方法到SQL里面还是得从集合SELECT, 只不过用行列比较代替了BITAND操作,我感觉省不了多少。
我突然觉得38位十进制的表现力也足够了,这两天如果有空就来试试某人的十进制之和出现3这种做法,看看到4,4,3能有多少帮助。

使用道具 举报

回复
论坛徽章:
264
布鲁克
日期:2016-10-08 10:06:50秀才
日期:2016-05-20 15:09:32射手座
日期:2016-05-26 14:02:50双子座
日期:2016-05-25 16:05:44白羊座
日期:2016-05-23 11:49:19双鱼座
日期:2016-04-29 17:13:05秀才
日期:2016-04-29 15:03:39秀才
日期:2016-04-29 15:04:10技术图书徽章
日期:2016-04-29 15:04:10秀才
日期:2016-03-28 10:21:13
6#
发表于 2015-12-19 12:29 | 只看该作者
NEWKID  大神,你的这些解法我等看懂都得花半年!

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
7#
发表于 2015-12-19 12:48 | 只看该作者
solomon_007 发表于 2015-12-19 12:29
NEWKID  大神,你的这些解法我等看懂都得花半年!

第一题还是能看懂的,newkid的10g还有优化余地

with win as (
SELECT substr(wins,1,1) w1,substr(wins,2,1) w2,substr(wins,3,1) w3,wins
from (select substr('123456789147258369159357',level*3-2,3) wins from dual connect by level<=8)
),
b0 AS (
SELECT REPLACE(SYS_CONNECT_BY_PATH(n,','),',') moves
   FROM (select level n from dual connect by level<=9)
START WITH n IN (1,2)
CONNECT BY NOCYCLE n<>PRIOR n AND LEVEL<=9
),
b as(select /*+ materialize */ s moves,substr(s,1,1)||substr(s,3,1)||substr(s,5,1)||substr(s,7,1)||substr(s,9,1)x,
substr(s,2,1)||substr(s,4,1)||substr(s,6,1)||substr(s,8,1)o ,length(s)step
from (select moves s from b0 union all select distinct 5||replace(moves,'5') from b0))
,ttt AS (
SELECT B2.*
       ,CASE WHEN x_win is not null then 'X' when o_win is not null then 'O' ELSE 'D' END AS WINNER
         ,DECODE(mod(INSTR(moves,'1')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'2')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'3')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'4')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'5')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'6')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'7')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'8')-1,2),0,'X',1,'O','-')
        ||DECODE(mod(INSTR(moves,'9')-1,2),0,'X',1,'O','-') AS board
FROM (
        SELECT b.*
              ,(SELECT MIN(GREATEST(INSTR(b.x,w1),INSTR(b.x,w2),INSTR(b.x,w3)))
                  FROM win
                 WHERE INSTR(b.x,w1)>0 AND INSTR(b.x,w2)>0 AND INSTR(b.x,w3)>0
                ) AS x_win
              ,(SELECT MIN(GREATEST(INSTR(b.o,w1),INSTR(b.o,w2),INSTR(b.o,w3)))
                  FROM win
                 WHERE INSTR(b.o,w1)>0 AND INSTR(b.o,w2)>0 AND INSTR(b.o,w3)>0
                ) AS o_win
          FROM b
         --WHERE SUBSTR(MOVES,1,1)<>'5' OR SUBSTR(MOVES,2,1) IN ('1','2')
        ) B2
WHERE (x_win>0 AND o_win IS NULL AND x_win=LENGTH(x) AND LENGTH(x)=LENGTH(o)+1
        OR o_win>0 AND x_win IS NULL AND o_win=LENGTH(o) AND LENGTH(x)=LENGTH(o)
        OR x_win is null and o_win is null and step=9
        )
)
,TP AS (
SELECT /*+ materialize */ '123456789' AS tpl_org,tpl_str FROM (
      SELECT '123456789' AS tpl_str FROM DUAL ----- tpl_id=0: 原样
     UNION ALL SELECT '987654321' FROM DUAL ----- tpl_id=3: 顺时针180度
     UNION ALL SELECT '369258147' FROM DUAL ----- tpl_id=6: 顺时针90度
     UNION ALL SELECT '741852963' FROM DUAL ----- tpl_id=7: 逆时针90度
    )
)
select * from(SELECT TRANSLATE(ttt.moves,tpl_org,tpl_str) moves
       ,TRANSLATE(tpl_org,tpl_str,ttt.board) board
       ,ttt.winner
FROM tp,ttt);

使用道具 举报

回复
论坛徽章:
264
布鲁克
日期:2016-10-08 10:06:50秀才
日期:2016-05-20 15:09:32射手座
日期:2016-05-26 14:02:50双子座
日期:2016-05-25 16:05:44白羊座
日期:2016-05-23 11:49:19双鱼座
日期:2016-04-29 17:13:05秀才
日期:2016-04-29 15:03:39秀才
日期:2016-04-29 15:04:10技术图书徽章
日期:2016-04-29 15:04:10秀才
日期:2016-03-28 10:21:13
8#
发表于 2015-12-19 13:18 | 只看该作者
这种大段的代码有着复杂之美,要慢慢品味

使用道具 举报

回复
论坛徽章:
78
生肖徽章2007版:牛
日期:2012-08-02 22:43:00紫蛋头
日期:2012-12-08 09:43:38鲜花蛋
日期:2012-11-17 12:02:07鲜花蛋
日期:2013-02-05 21:53:34复活蛋
日期:2012-11-17 12:02:07SQL极客
日期:2013-12-09 14:13:35SQL数据库编程大师
日期:2013-12-06 13:59:43SQL大赛参与纪念
日期:2013-12-06 14:10:50ITPUB季度 技术新星
日期:2012-11-27 10:16:10最佳人气徽章
日期:2013-03-19 17:24:25
9#
发表于 2015-12-19 13:32 | 只看该作者
第一题最快的速度是多久?我现在能改出1.98秒,但是写法很2
我觉得你还不如直接说牛蛙,说什么某人嘛

使用道具 举报

回复
论坛徽章:
78
生肖徽章2007版:牛
日期:2012-08-02 22:43:00紫蛋头
日期:2012-12-08 09:43:38鲜花蛋
日期:2012-11-17 12:02:07鲜花蛋
日期:2013-02-05 21:53:34复活蛋
日期:2012-11-17 12:02:07SQL极客
日期:2013-12-09 14:13:35SQL数据库编程大师
日期:2013-12-06 13:59:43SQL大赛参与纪念
日期:2013-12-06 14:10:50ITPUB季度 技术新星
日期:2012-11-27 10:16:10最佳人气徽章
日期:2013-03-19 17:24:25
10#
发表于 2015-12-19 13:35 | 只看该作者
其实,我从一开始就隐约看到了一种编码格式可以方便的表示胜出,但是花费了很久才突破了这一层屏障

使用道具 举报

回复

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

本版积分规则

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