答案出来了.其中细节还需要仔细回味.

http://www.itpub.net/thread-2048956-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;

ITPub博客

井字棋解法(参考答案一解)

最新文章