题目：井字棋

两个玩家，一个打圈(O)，一个打叉(X)，轮流在3乘3的井字格上打自己的符号，最先以任意一行、一列或对角线连成一线则为胜。规定X先手。

一个终局棋谱（MOVES）指的是从开始下子到一方获胜或者下完9个子出现平局，从头到尾的下子情况。一方获胜后，本局即终止。不得提前认输。

格子从上到下，从左到右，依次编号1-9

MOVES的第一位表示第一子位置，第二位表示第二子位置，......如果一方获胜，MOVES的长度有可能<9。

局面（BOARD）表示棋盘上呈现的局面，也是按照从上到下，从左到右排列。用X和0填入相应的格子。减号“-” 表示空位。

这里有个棋局：

表示出来是:

MOVES=3175968,

BOARD=XOXOXOX,

WINNER=X

我觉得这个首先把先手,后手所有的排列组合列出来,然后设定胜利条件,最后过滤.

因为先后手交替落子,假设我有三个格子,落手的排列组合如下.

with nums as (
select level id from dual connect by level<=3
),
MOVES as(
select n1.id||n2.id||n3.id moves,
n1.id||n3.id X,
n2.id O
from
nums n1,
nums n2,
nums n3
where
(n1.id!=n2.id and n1.id!=n3.id ) and
(n2.id!=n1.id and n2.id!=n3.id ) and
(n3.id!=n2.id and n3.id!=n1.id)
)
select * from moves;

结果如下:

那么井字棋所有的排列组合如下:

with nums as (
select level id from dual connect by level<=9
),
MOVES as(
select n1.id||n2.id||n3.id||n4.id||n5.id||n6.id||n7.id||n8.id||n9.id moves,
n1.id||n3.id||n5.id||n7.id||n9.id X,
n2.id||n4.id||n6.id||n8.id||n9.id O
from
nums n1,
nums n2,
nums n3,
nums n4,
nums n5,
nums n6,
nums n7,
nums n8,
nums n9
where
(n1.id!=n2.id and n1.id!=n3.id and n1.id!=n4.id and n1.id!=n5.id and n1.id!=n6.id and n1.id!=n7.id and n1.id!=n8.id and n1.id!=n9.id) and
(n2.id!=n1.id and n2.id!=n3.id and n2.id!=n4.id and n2.id!=n5.id and n2.id!=n6.id and n2.id!=n7.id and n2.id!=n8.id and n2.id!=n9.id) and
(n3.id!=n2.id and n3.id!=n1.id and n3.id!=n4.id and n3.id!=n5.id and n3.id!=n6.id and n3.id!=n7.id and n3.id!=n8.id and n3.id!=n9.id) and
(n4.id!=n2.id and n4.id!=n3.id and n4.id!=n1.id and n4.id!=n5.id and n4.id!=n6.id and n4.id!=n7.id and n4.id!=n8.id and n4.id!=n9.id) and
(n5.id!=n2.id and n5.id!=n3.id and n5.id!=n4.id and n5.id!=n1.id and n5.id!=n6.id and n5.id!=n7.id and n5.id!=n8.id and n5.id!=n9.id) and
(n6.id!=n2.id and n6.id!=n3.id and n6.id!=n4.id and n6.id!=n5.id and n6.id!=n1.id and n6.id!=n7.id and n6.id!=n8.id and n6.id!=n9.id) and
(n7.id!=n2.id and n7.id!=n3.id and n7.id!=n4.id and n7.id!=n5.id and n7.id!=n6.id and n7.id!=n1.id and n7.id!=n8.id and n7.id!=n9.id) and
(n8.id!=n1.id and n8.id!=n3.id and n8.id!=n4.id and n8.id!=n5.id and n8.id!=n6.id and n8.id!=n7.id and n8.id!=n2.id and n8.id!=n9.id) and
(n9.id!=n2.id and n9.id!=n3.id and n9.id!=n4.id and n9.id!=n5.id and n9.id!=n6.id and n9.id!=n7.id and n9.id!=n8.id and n9.id!=n1.id)
)
select * from moves;

部分结果如下:

moves表示先后手顺序的落子顺序,X表示先手的落子,O表示后手的落子.

题目中示范图的落子顺序,在这个SQL中的结果如下
317596842 37982 15642
317596824 37984 15624

棋盘:
123
456
789
胜利条件,任何一方先包括下面所有的数字,则为胜利
横向:[123][456][789]
竖向:[147][258][369]
斜向:[159][357]
数字先后顺序不重要,只要某一方落子包括了上述数字组合,则应该认为可能胜利.
如果先后手,都满足了条件,则应该看谁先满足.

整个SQL如下:

create table t1 as
with nums as (
select level id from dual connect by level<=9
),
MOVES as(
select n1.id||n2.id||n3.id||n4.id||n5.id||n6.id||n7.id||n8.id||n9.id moves,
n1.id||n3.id||n5.id||n7.id||n9.id X,
n2.id||n4.id||n6.id||n8.id||n9.id O,
'XOXOXOXOX' BOARD
from
nums n1,
nums n2,
nums n3,
nums n4,
nums n5,
nums n6,
nums n7,
nums n8,
nums n9
where
(n1.id!=n2.id and n1.id!=n3.id and n1.id!=n4.id and n1.id!=n5.id and n1.id!=n6.id and n1.id!=n7.id and n1.id!=n8.id and n1.id!=n9.id) and
(n2.id!=n1.id and n2.id!=n3.id and n2.id!=n4.id and n2.id!=n5.id and n2.id!=n6.id and n2.id!=n7.id and n2.id!=n8.id and n2.id!=n9.id) and
(n3.id!=n2.id and n3.id!=n1.id and n3.id!=n4.id and n3.id!=n5.id and n3.id!=n6.id and n3.id!=n7.id and n3.id!=n8.id and n3.id!=n9.id) and
(n4.id!=n2.id and n4.id!=n3.id and n4.id!=n1.id and n4.id!=n5.id and n4.id!=n6.id and n4.id!=n7.id and n4.id!=n8.id and n4.id!=n9.id) and
(n5.id!=n2.id and n5.id!=n3.id and n5.id!=n4.id and n5.id!=n1.id and n5.id!=n6.id and n5.id!=n7.id and n5.id!=n8.id and n5.id!=n9.id) and
(n6.id!=n2.id and n6.id!=n3.id and n6.id!=n4.id and n6.id!=n5.id and n6.id!=n1.id and n6.id!=n7.id and n6.id!=n8.id and n6.id!=n9.id) and
(n7.id!=n2.id and n7.id!=n3.id and n7.id!=n4.id and n7.id!=n5.id and n7.id!=n6.id and n7.id!=n1.id and n7.id!=n8.id and n7.id!=n9.id) and
(n8.id!=n1.id and n8.id!=n3.id and n8.id!=n4.id and n8.id!=n5.id and n8.id!=n6.id and n8.id!=n7.id and n8.id!=n2.id and n8.id!=n9.id) and
(n9.id!=n2.id and n9.id!=n3.id and n9.id!=n4.id and n9.id!=n5.id and n9.id!=n6.id and n9.id!=n7.id and n9.id!=n8.id and n9.id!=n1.id)
),
v1 as (
select m.*,
translate(m.X,'123456789','1__4__7__') xc1,
translate(m.X,'123456789','_2__5__8_') xc2,
translate(m.X,'123456789','__3__6__9') xc3,
translate(m.X,'123456789','1___5___9') xc4,
translate(m.X,'123456789','__3_5_7__') xc5,
translate(m.X,'123456789','123______') xc6,
translate(m.X,'123456789','___456___') xc7,
translate(m.X,'123456789','______789') xc8,
translate(m.O,'123456789','1__4__7__') oc1,
translate(m.O,'123456789','_2__5__8_') oc2,
translate(m.O,'123456789','__3__6__9') oc3,
translate(m.O,'123456789','1___5___9') oc4,
translate(m.O,'123456789','__3_5_7__') oc5,
translate(m.O,'123456789','123______') oc6,
translate(m.O,'123456789','___456___') oc7,
translate(m.O,'123456789','______789') oc8
from moves m
),
score as (
select
v1.*,
least(
decode(regexp_instr(xc1,'[1-9]',1,3) ,0,999,regexp_instr(xc1,'[1-9]',1,3)),
decode(regexp_instr(xc2,'[1-9]',1,3) ,0,999,regexp_instr(xc2,'[1-9]',1,3)),
decode(regexp_instr(xc3,'[1-9]',1,3) ,0,999,regexp_instr(xc3,'[1-9]',1,3)),
decode(regexp_instr(xc4,'[1-9]',1,3) ,0,999,regexp_instr(xc4,'[1-9]',1,3)),
decode(regexp_instr(xc5,'[1-9]',1,3) ,0,999,regexp_instr(xc5,'[1-9]',1,3)),
decode(regexp_instr(xc6,'[1-9]',1,3) ,0,999,regexp_instr(xc6,'[1-9]',1,3)),
decode(regexp_instr(xc7,'[1-9]',1,3) ,0,999,regexp_instr(xc7,'[1-9]',1,3)),
decode(regexp_instr(xc8,'[1-9]',1,3) ,0,999,regexp_instr(xc8,'[1-9]',1,3))
) xscore,
least(
decode(regexp_instr(oc1,'[1-9]',1,3) ,0,999,regexp_instr(oc1,'[1-9]',1,3)),
decode(regexp_instr(oc2,'[1-9]',1,3) ,0,999,regexp_instr(oc2,'[1-9]',1,3)),
decode(regexp_instr(oc3,'[1-9]',1,3) ,0,999,regexp_instr(oc3,'[1-9]',1,3)),
decode(regexp_instr(oc4,'[1-9]',1,3) ,0,999,regexp_instr(oc4,'[1-9]',1,3)),
decode(regexp_instr(oc5,'[1-9]',1,3) ,0,999,regexp_instr(oc5,'[1-9]',1,3)),
decode(regexp_instr(oc6,'[1-9]',1,3) ,0,999,regexp_instr(oc6,'[1-9]',1,3)),
decode(regexp_instr(oc7,'[1-9]',1,3) ,0,999,regexp_instr(oc7,'[1-9]',1,3)),
decode(regexp_instr(oc8,'[1-9]',1,3) ,0,999,regexp_instr(oc8,'[1-9]',1,3))
) oscore
from v1
where
regexp_instr(xc1,'[1-9]',1,3) !=0 or
regexp_instr(xc2,'[1-9]',1,3) !=0 or
regexp_instr(xc3,'[1-9]',1,3) !=0 or
regexp_instr(xc4,'[1-9]',1,3) !=0 or
regexp_instr(xc5,'[1-9]',1,3) !=0 or
regexp_instr(xc6,'[1-9]',1,3) !=0 or
regexp_instr(xc7,'[1-9]',1,3) !=0 or
regexp_instr(xc8,'[1-9]',1,3) !=0 or
regexp_instr(oc1,'[1-9]',1,3) !=0 or
regexp_instr(oc2,'[1-9]',1,3) !=0 or
regexp_instr(oc3,'[1-9]',1,3) !=0 or
regexp_instr(oc4,'[1-9]',1,3) !=0 or
regexp_instr(oc5,'[1-9]',1,3) !=0 or
regexp_instr(oc6,'[1-9]',1,3) !=0 or
regexp_instr(oc7,'[1-9]',1,3) !=0 or
regexp_instr(oc8,'[1-9]',1,3) !=0
)
select distinct
case when xscore<=oscore then substr(score.moves,0,xscore*2-1) else substr(score.moves,0,2*oscore) end moves,
case when xscore<=oscore then substr(x,0,xscore) else substr(x,0,oscore) end x,
case when xscore<=oscore then substr(o,0,xscore-1) else substr(o,0,oscore) end o,
case when xscore<=oscore then 'X' else 'O' end winer
from score;
select count(*) from t1;

所有可能的组合为:232128
部分结果如下:

性能比较差,也不知道结果对不对.
moves视图生成所有落子组合
v1视图辅助生成胜利条件
score视图计算先后手,最先达到胜利条件的位置
最后整理,
如果先手赢,后手落子数量少一个.
如果后手赢,先后后手落子数量相等.

ITPub博客

井字棋解法

最新文章