The New Order Oracle Coding Challenge 4 – Tic Tac Toe

12 08 2011

(Back to the Previous Post in the Series)

Tic Tac Toe, the game of X’s and O’s, was an oddly popular game in elementary school.  When playing the game you quickly learn a couple of rules:

  • Because X always places his mark first (alternating between X and O), there is an unfair advantage for the player placing the X marks.
  • The player placing his mark in the center square typically has an advantage in the game.
  • Once a player scores three marks in a row horizontally, vertically, or diagonally, there is no point in continuing the game.

-

-

-

-

-

-

-

Consider the above game matches.  In the first two matches both X and O score three in a row, but which player won the match – it depends on the order in which the marks were placed.  In the third match, X won with a diagnal three in a row.  The final match resulted in a tie (neither player won).  You can use a SQL statement similar to the following to output all of the roughly 362,000 combinations (note that not all combinations are unique – rotating the board 90 or 180 degrees to generate a unique combination probably is not fair, and the order in which the marks are placed could matter):

WITH
 N AS
  (SELECT
    ROWNUM N
  FROM
    DUAL
  CONNECT BY
    LEVEL<=9),
 C AS
  (SELECT
    'XOX'||'OXO'||'XOX' C
  FROM
    DUAL)
SELECT
  SUBSTR(C.C,N1.N,1) ||
  SUBSTR(C.C,N2.N,1) ||
  SUBSTR(C.C,N3.N,1) || CHR(10) ||
  SUBSTR(C.C,N4.N,1) ||
  SUBSTR(C.C,N5.N,1) ||
  SUBSTR(C.C,N6.N,1) || CHR(10) ||
  SUBSTR(C.C,N7.N,1) ||
  SUBSTR(C.C,N8.N,1) ||
  SUBSTR(C.C,N9.N,1) GAME
FROM
  N N1,
  N N2,
  N N3,
  N N4,
  N N5,
  N N6,
  N N7,
  N N8,
  N N9,
  C
WHERE
  N1.N<>N2.N
  AND N1.N<>N3.N
  AND N1.N<>N4.N
  AND N1.N<>N5.N
  AND N1.N<>N6.N
  AND N1.N<>N7.N
  AND N1.N<>N8.N
  AND N1.N<>N9.N
  AND N2.N<>N3.N
  AND N2.N<>N4.N
  AND N2.N<>N5.N
  AND N2.N<>N6.N
  AND N2.N<>N7.N
  AND N2.N<>N8.N
  AND N2.N<>N9.N
  AND N3.N<>N4.N
  AND N3.N<>N5.N
  AND N3.N<>N6.N
  AND N3.N<>N7.N
  AND N3.N<>N8.N
  AND N3.N<>N9.N
  AND N4.N<>N5.N
  AND N4.N<>N6.N
  AND N4.N<>N7.N
  AND N4.N<>N8.N
  AND N4.N<>N9.N
  AND N5.N<>N6.N
  AND N5.N<>N7.N
  AND N5.N<>N8.N
  AND N5.N<>N9.N
  AND N6.N<>N7.N
  AND N6.N<>N8.N
  AND N6.N<>N9.N
  AND N7.N<>N8.N
  AND N7.N<>N9.N
  AND N8.N<>N9.N; 

The output of the above SQL statement should appear similar to the following:

GAME
----
...

XXX
OOO
OXX

XXX
OOO
OXX

...

XOX
XOO
OXX

OXX
XOO
OXX

XXO
XOO
XOX

XXO
XOO
XOX

XOX
XOO
XOX 

...

The big problem with the above SQL statement is that it is not clear which player won in all cases.  Ideally, the N1.N value would be used to output an X mark in the specified position, the N2.N value would be used to output an O mark in a specified position, the N3.N value would be used to output an X in the specified position, etc. until one of the players places three marks in a row.  For example, if N1.N is 5, an X would be placed in the center square, if N2.N is 9, an O would be placed in the bottom right square.

Now that we know that the order in which the marks are placed is important, how would be know when a player wins?  You could experiment with the following:

Vertical win, with three positions having the same resulting values:

SELECT
  MOD(position - 1, 3) + 1 V
FROM
  DUAL; 

Horizontal win, with three positions having the same resulting values:

SELECT
  TRUNC((position - 1) / 3) + 1 V
FROM
  DUAL;

Diagnal win \ when V=0 in three positions:

SELECT
  (MOD(position - 1, 3) + 1) - (TRUNC((position - 1) / 3) + 1) V
FROM
  DUAL;

Diagnal win / when V=0 (watch out, could end up in a V pattern) or V=2:

SELECT
  ABS((MOD(position - 1, 3) + 1) - (TRUNC((position - 1) / 3) + 1)) V
FROM
  DUAL; 

-----------

OK, now that I have explained the game, given you a couple of SQL statements to possibly help you with the solution... on to the challenge.  With the help of Oracle Database build a tic tac toe solver that will help a player win at tic tac toe.  Provided a current description of the board, for example '_X_'||'O_X'||'OX_', display all board solutions that allows player O (or player X if his turn is next) to win.  (Side note: I have not yet completed the solution to this challenge - it might be possible to accomplish this challenge with just a SQL statement.)


Actions

Information

5 responses

12 08 2011
Gary Colbran

That’s tough. My attempt so far……….

Assuming -1 for X, 0 for unplayed and 1 for O, we could try the following..

Originally 19683 options in the game at any combination.

SQL> select 3*3*3*3*3*3*3*3*3 from dual;

19683

Let’s whittle it down to where the number of moves are 1 ahead of the other in any combination, or equal.

select * from (select * from (
with r1 as (select rownum-2 rn from dual connect by level < 4),
r2 as (select rownum-2 rn from dual connect by level < 4),
r3 as (select rownum-2 rn from dual connect by level < 4),
r4 as (select rownum-2 rn from dual connect by level < 4),
r5 as (select rownum-2 rn from dual connect by level < 4),
r6 as (select rownum-2 rn from dual connect by level < 4),
r7 as (select rownum-2 rn from dual connect by level < 4),
r8 as (select rownum-2 rn from dual connect by level < 4),
r9 as (select rownum-2 rn from dual connect by level < 4)
select decode(r1.rn, 0, '_', -1, 'X', 'O')||
decode(r2.rn, 0, '_', -1, 'X', 'O')||
decode(r3.rn, 0, '_', -1, 'X', 'O') v1,
decode(r4.rn, 0, '_', -1, 'X', 'O')||
decode(r5.rn, 0, '_', -1, 'X', 'O')||
decode(r6.rn, 0, '_', -1, 'X', 'O') v2,
decode(r7.rn, 0, '_', -1, 'X', 'O')||
decode(r8.rn, 0, '_', -1, 'X', 'O')||
decode(r9.rn, 0, '_', -1, 'X', 'O') v3,
r1.rn+r2.rn+r3.rn+r4.rn+r5.rn+r6.rn+r7.rn+r8.rn+r9.rn rnt
from r1, r2, r3, r4, r5, r6, r7, r8, r9
)
where abs(rnt) < 2)
where rownum < 50
/

That leaves us 8953 options.

Now let's find rows where X or O has won.

select v1,v2,v3 from (select * from (
with r1 as (select rownum-2 rn from dual connect by level < 4),
r2 as (select rownum-2 rn from dual connect by level < 4),
r3 as (select rownum-2 rn from dual connect by level < 4),
r4 as (select rownum-2 rn from dual connect by level < 4),
r5 as (select rownum-2 rn from dual connect by level < 4),
r6 as (select rownum-2 rn from dual connect by level < 4),
r7 as (select rownum-2 rn from dual connect by level < 4),
r8 as (select rownum-2 rn from dual connect by level < 4),
r9 as (select rownum-2 rn from dual connect by level < 4)
select r1.rn r1, r2.rn r2, r3.rn r3, r4.rn r4,
r5.rn r5, r6.rn r6, r7.rn r7, r8.rn r8, r9.rn r9,
decode(r1.rn, 0, '_', -1, 'X', 'O')||
decode(r2.rn, 0, '_', -1, 'X', 'O')||
decode(r3.rn, 0, '_', -1, 'X', 'O') v1,
decode(r4.rn, 0, '_', -1, 'X', 'O')||
decode(r5.rn, 0, '_', -1, 'X', 'O')||
decode(r6.rn, 0, '_', -1, 'X', 'O') v2,
decode(r7.rn, 0, '_', -1, 'X', 'O')||
decode(r8.rn, 0, '_', -1, 'X', 'O')||
decode(r9.rn, 0, '_', -1, 'X', 'O') v3,
r1.rn+r2.rn+r3.rn+r4.rn+r5.rn+r6.rn+r7.rn+r8.rn+r9.rn rnt
from r1, r2, r3, r4, r5, r6, r7, r8, r9
)
where abs(rnt) < 2
and (
(abs(r1+r2+r3) = 3)
or
(abs(r4+r5+r6) = 3)
or
(abs(r7+r8+r9) = 3)
or
(abs(r1+r4+r7) = 3)
or
(abs(r2+r5+r8) = 3)
or
(abs(r3+r6+r9) = 3)
or
(abs(r1+r5+r9) = 3)
or
(abs(r3+r5+r7) = 3)
)
)
--where rownum < 50
/

2304 options. Now we assume X goes first, hence the total values will be -1 or 0.

select v1,v2,v3 from (select * from (
with r1 as (select rownum-2 rn from dual connect by level < 4),
r2 as (select rownum-2 rn from dual connect by level < 4),
r3 as (select rownum-2 rn from dual connect by level < 4),
r4 as (select rownum-2 rn from dual connect by level < 4),
r5 as (select rownum-2 rn from dual connect by level < 4),
r6 as (select rownum-2 rn from dual connect by level < 4),
r7 as (select rownum-2 rn from dual connect by level < 4),
r8 as (select rownum-2 rn from dual connect by level < 4),
r9 as (select rownum-2 rn from dual connect by level < 4)
select r1.rn r1, r2.rn r2, r3.rn r3, r4.rn r4,
r5.rn r5, r6.rn r6, r7.rn r7, r8.rn r8, r9.rn r9,
decode(r1.rn, 0, '_', -1, 'X', 'O')||
decode(r2.rn, 0, '_', -1, 'X', 'O')||
decode(r3.rn, 0, '_', -1, 'X', 'O') v1,
decode(r4.rn, 0, '_', -1, 'X', 'O')||
decode(r5.rn, 0, '_', -1, 'X', 'O')||
decode(r6.rn, 0, '_', -1, 'X', 'O') v2,
decode(r7.rn, 0, '_', -1, 'X', 'O')||
decode(r8.rn, 0, '_', -1, 'X', 'O')||
decode(r9.rn, 0, '_', -1, 'X', 'O') v3,
r1.rn+r2.rn+r3.rn+r4.rn+r5.rn+r6.rn+r7.rn+r8.rn+r9.rn rnt
from r1, r2, r3, r4, r5, r6, r7, r8, r9
)
where rnt in (0,-1)
and (
(abs(r1+r2+r3) = 3)
or
(abs(r4+r5+r6) = 3)
or
(abs(r7+r8+r9) = 3)
or
(abs(r1+r4+r7) = 3)
or
(abs(r2+r5+r8) = 3)
or
(abs(r3+r6+r9) = 3)
or
(abs(r1+r5+r9) = 3)
or
(abs(r3+r5+r7) = 3)
)
)
--where rownum < 50
/

1510 rows returned.

Ok, let's get the formatting out and identify the winning games.

select row1, h1, h2, h3, v1, v2, v3, d1, d2 from (select a.*,
r1+r2+r3 h1, r4+r5+r6 h2, r7+r8+r9 h3,
r1+r4+r7 v1, r2+r5+r8 v2, r3+r6+r9 v3,
r1+r5+r9 d1, r3+r5+r7 d2 from (
with r1 as (select rownum-2 rn from dual connect by level < 4),
r2 as (select rownum-2 rn from dual connect by level < 4),
r3 as (select rownum-2 rn from dual connect by level < 4),
r4 as (select rownum-2 rn from dual connect by level < 4),
r5 as (select rownum-2 rn from dual connect by level < 4),
r6 as (select rownum-2 rn from dual connect by level < 4),
r7 as (select rownum-2 rn from dual connect by level < 4),
r8 as (select rownum-2 rn from dual connect by level < 4),
r9 as (select rownum-2 rn from dual connect by level < 4)
select r1.rn r1, r2.rn r2, r3.rn r3, r4.rn r4,
r5.rn r5, r6.rn r6, r7.rn r7, r8.rn r8, r9.rn r9,
decode(r1.rn, 0, '_', -1, 'X', 'O')||
decode(r2.rn, 0, '_', -1, 'X', 'O')||
decode(r3.rn, 0, '_', -1, 'X', 'O')||chr(13)||chr(10)||
decode(r4.rn, 0, '_', -1, 'X', 'O')||
decode(r5.rn, 0, '_', -1, 'X', 'O')||
decode(r6.rn, 0, '_', -1, 'X', 'O')||chr(13)||chr(10)||
decode(r7.rn, 0, '_', -1, 'X', 'O')||
decode(r8.rn, 0, '_', -1, 'X', 'O')||
decode(r9.rn, 0, '_', -1, 'X', 'O') row1,
r1.rn+r2.rn+r3.rn+r4.rn+r5.rn+r6.rn+r7.rn+r8.rn+r9.rn rnt
from r1, r2, r3, r4, r5, r6, r7, r8, r9
) a
where rnt in (0,-1)
and (
(abs(r1+r2+r3) = 3)
or
(abs(r4+r5+r6) = 3)
or
(abs(r7+r8+r9) = 3)
or
(abs(r1+r4+r7) = 3)
or
(abs(r2+r5+r8) = 3)
or
(abs(r3+r6+r9) = 3)
or
(abs(r1+r5+r9) = 3)
or
(abs(r3+r5+r7) = 3)
)
)
--where rownum < 50
/

1510 rows returned.

And take out rows where both sides win, which is impossible.

SELECT row1, h1, h2, h3, v1, v2, v3, d1, d2, rnt
  FROM (SELECT a.*,
               r1 + r2 + r3 h1,
               r4 + r5 + r6 h2,
               r7 + r8 + r9 h3,
               r1 + r4 + r7 v1,
               r2 + r5 + r8 v2,
               r3 + r6 + r9 v3,
               r1 + r5 + r9 d1,
               r3 + r5 + r7 d2,
a.rnt
          FROM (WITH r1 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r2 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r3 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r4 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r5 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r6 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r7 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r8 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r9 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4)
                SELECT r1.rn r1,
                       r2.rn r2,
                       r3.rn r3,
                       r4.rn r4,
                       r5.rn r5,
                       r6.rn r6,
                       r7.rn r7,
                       r8.rn r8,
                       r9.rn r9,
                          DECODE (r1.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r2.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r3.rn,  0, '_',  -1, 'X',  'O')
                       || CHR (13)
                       || CHR (10)
                       || DECODE (r4.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r5.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r6.rn,  0, '_',  -1, 'X',  'O')
                       || CHR (13)
                       || CHR (10)
                       || DECODE (r7.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r8.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r9.rn,  0, '_',  -1, 'X',  'O')
                          row1,
                         r1.rn
                       + r2.rn
                       + r3.rn
                       + r4.rn
                       + r5.rn
                       + r6.rn
                       + r7.rn
                       + r8.rn
                       + r9.rn
                          rnt
                  FROM r1, r2, r3, r4, r5, r6, r7, r8, r9) a
         WHERE rnt IN (0, -1)
               AND (   (ABS (r1 + r2 + r3) = 3)
                    OR (ABS (r4 + r5 + r6) = 3)
                    OR (ABS (r7 + r8 + r9) = 3)
                    OR (ABS (r1 + r4 + r7) = 3)
                    OR (ABS (r2 + r5 + r8) = 3)
                    OR (ABS (r3 + r6 + r9) = 3)
                    OR (ABS (r1 + r5 + r9) = 3)
                    OR (ABS (r3 + r5 + r7) = 3)))
 WHERE   DECODE (ABS (h1), 3, 1, 0)
       + DECODE (ABS (h2), 3, 1, 0)
       + DECODE (ABS (h3), 3, 1, 0)
       + DECODE (ABS (v1), 3, 1, 0)
       + DECODE (ABS (v2), 3, 1, 0)
       + DECODE (ABS (v3), 3, 1, 0)
       + DECODE (ABS (d1), 3, 1, 0)
       + DECODE (ABS (d2), 3, 1, 0) = 1
--where rownum < 50
/

Now we need to find if X or O win, which is a -3 (X) or 3 (O).

SELECT row1, h1, h2, h3, v1, v2, v3, d1, d2, rnt
  FROM (SELECT a.*,
               r1 + r2 + r3 h1,
               r4 + r5 + r6 h2,
               r7 + r8 + r9 h3,
               r1 + r4 + r7 v1,
               r2 + r5 + r8 v2,
               r3 + r6 + r9 v3,
               r1 + r5 + r9 d1,
               r3 + r5 + r7 d2,
a.rnt
          FROM (WITH r1 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r2 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r3 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r4 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r5 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r6 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r7 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r8 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r9 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4)
                SELECT r1.rn r1,
                       r2.rn r2,
                       r3.rn r3,
                       r4.rn r4,
                       r5.rn r5,
                       r6.rn r6,
                       r7.rn r7,
                       r8.rn r8,
                       r9.rn r9,
                          DECODE (r1.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r2.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r3.rn,  0, '_',  -1, 'X',  'O')
                       || CHR (13)
                       || CHR (10)
                       || DECODE (r4.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r5.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r6.rn,  0, '_',  -1, 'X',  'O')
                       || CHR (13)
                       || CHR (10)
                       || DECODE (r7.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r8.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r9.rn,  0, '_',  -1, 'X',  'O')
                          row1,
                         r1.rn
                       + r2.rn
                       + r3.rn
                       + r4.rn
                       + r5.rn
                       + r6.rn
                       + r7.rn
                       + r8.rn
                       + r9.rn
                          rnt,
                  FROM r1, r2, r3, r4, r5, r6, r7, r8, r9) a
         WHERE rnt IN (0, -1)
               AND (   (ABS (r1 + r2 + r3) = 3)
                    OR (ABS (r4 + r5 + r6) = 3)
                    OR (ABS (r7 + r8 + r9) = 3)
                    OR (ABS (r1 + r4 + r7) = 3)
                    OR (ABS (r2 + r5 + r8) = 3)
                    OR (ABS (r3 + r6 + r9) = 3)
                    OR (ABS (r1 + r5 + r9) = 3)
                    OR (ABS (r3 + r5 + r7) = 3)))
 WHERE   DECODE (ABS (h1), 3, 1, 0)
       + DECODE (ABS (h2), 3, 1, 0)
       + DECODE (ABS (h3), 3, 1, 0)
       + DECODE (ABS (v1), 3, 1, 0)
       + DECODE (ABS (v2), 3, 1, 0)
       + DECODE (ABS (v3), 3, 1, 0)
       + DECODE (ABS (d1), 3, 1, 0)
       + DECODE (ABS (d2), 3, 1, 0) = 1
--where rownum < 50
/

So I can add the winner of the game in there too.

SELECT row1,
       h1,
       h2,
       h3,
       v1,
       v2,
       v3,
       d1,
       d2,
       rnt,
       DECODE (LEAST (h1, h2, h3, v1, v2, v3, d1, d2), -3, 'X', 'O')
          winner
  FROM (SELECT a.row1,
               r1 + r2 + r3 h1,
               r4 + r5 + r6 h2,
               r7 + r8 + r9 h3,
               r1 + r4 + r7 v1,
               r2 + r5 + r8 v2,
               r3 + r6 + r9 v3,
               r1 + r5 + r9 d1,
               r3 + r5 + r7 d2,
               rnt
          FROM (WITH r1 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r2 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r3 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r4 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r5 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r6 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r7 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r8 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4),
                     r9 AS (SELECT ROWNUM - 2 rn
                              FROM DUAL
                            CONNECT BY LEVEL < 4)
                SELECT r1.rn r1,
                       r2.rn r2,
                       r3.rn r3,
                       r4.rn r4,
                       r5.rn r5,
                       r6.rn r6,
                       r7.rn r7,
                       r8.rn r8,
                       r9.rn r9,
                          DECODE (r1.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r2.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r3.rn,  0, '_',  -1, 'X',  'O')
                       || CHR (13)
                       || CHR (10)
                       || DECODE (r4.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r5.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r6.rn,  0, '_',  -1, 'X',  'O')
                       || CHR (13)
                       || CHR (10)
                       || DECODE (r7.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r8.rn,  0, '_',  -1, 'X',  'O')
                       || DECODE (r9.rn,  0, '_',  -1, 'X',  'O')
                          row1,
                         r1.rn
                       + r2.rn
                       + r3.rn
                       + r4.rn
                       + r5.rn
                       + r6.rn
                       + r7.rn
                       + r8.rn
                       + r9.rn
                          rnt
                  FROM r1, r2, r3, r4, r5, r6, r7, r8, r9) a
         WHERE rnt IN (0, -1)
               AND (   (ABS (r1 + r2 + r3) = 3)
                    OR (ABS (r4 + r5 + r6) = 3)
                    OR (ABS (r7 + r8 + r9) = 3)
                    OR (ABS (r1 + r4 + r7) = 3)
                    OR (ABS (r2 + r5 + r8) = 3)
                    OR (ABS (r3 + r6 + r9) = 3)
                    OR (ABS (r1 + r5 + r9) = 3)
                    OR (ABS (r3 + r5 + r7) = 3)))
 WHERE   DECODE (ABS (h1), 3, 1, 0)
       + DECODE (ABS (h2), 3, 1, 0)
       + DECODE (ABS (h3), 3, 1, 0)
       + DECODE (ABS (v1), 3, 1, 0)
       + DECODE (ABS (v2), 3, 1, 0)
       + DECODE (ABS (v3), 3, 1, 0)
       + DECODE (ABS (d1), 3, 1, 0)
       + DECODE (ABS (d2), 3, 1, 0) = 1
--where rownum < 50
/

That gives the 1332 options where X can win.

So, given a position in the game we would have to return the rows from there, still assuming that X went first.

CREATE OR REPLACE TYPE CONTROL.oxotype AS OBJECT
(
  oxo VARCHAR2(13),
  winner CHAR(1)
);

create or replace type rettab as table of oxotype;
/

CREATE OR REPLACE FUNCTION control.whowins (board IN VARCHAR2, nextmove CHAR)
   RETURN rettab
AS
   retval   rettab;
   rec      NUMBER := 0;
BEGIN
   FOR c1
      IN (SELECT row1,
                 h1,
                 h2,
                 h3,
                 v1,
                 v2,
                 v3,
                 d1,
                 d2,
                 rnt,
                 DECODE (
                    LEAST (h1, h2, h3, v1, v2, v3, d1, d2),
                    -3, 'X',
                    'O')
                    winner
            FROM (SELECT a.row1,
                         r1 + r2 + r3 h1,
                         r4 + r5 + r6 h2,
                         r7 + r8 + r9 h3,
                         r1 + r4 + r7 v1,
                         r2 + r5 + r8 v2,
                         r3 + r6 + r9 v3,
                         r1 + r5 + r9 d1,
                         r3 + r5 + r7 d2,
                         rnt
                    FROM (WITH r1 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r2 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r3 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r4 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r5 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r6 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r7 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r8 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r9 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4)
                          SELECT r1.rn r1,
                                 r2.rn r2,
                                 r3.rn r3,
                                 r4.rn r4,
                                 r5.rn r5,
                                 r6.rn r6,
                                 r7.rn r7,
                                 r8.rn r8,
                                 r9.rn r9,
                                    DECODE (r1.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r2.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r3.rn,  0, '_',  -1, 'X',  'O')
                                 || CHR (13)
                                 || CHR (10)
                                 || DECODE (r4.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r5.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r6.rn,  0, '_',  -1, 'X',  'O')
                                 || CHR (13)
                                 || CHR (10)
                                 || DECODE (r7.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r8.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r9.rn,  0, '_',  -1, 'X',  'O')
                                    row1,
                                   r1.rn
                                 + r2.rn
                                 + r3.rn
                                 + r4.rn
                                 + r5.rn
                                 + r6.rn
                                 + r7.rn
                                 + r8.rn
                                 + r9.rn
                                    rnt
                            FROM r1, r2, r3, r4, r5, r6, r7, r8, r9) a
                   WHERE rnt IN (0, -1)
                         AND (   (ABS (r1 + r2 + r3) = 3)
                              OR (ABS (r4 + r5 + r6) = 3)
                              OR (ABS (r7 + r8 + r9) = 3)
                              OR (ABS (r1 + r4 + r7) = 3)
                              OR (ABS (r2 + r5 + r8) = 3)
                              OR (ABS (r3 + r6 + r9) = 3)
                              OR (ABS (r1 + r5 + r9) = 3)
                              OR (ABS (r3 + r5 + r7) = 3)))
           WHERE   DECODE (ABS (h1), 3, 1, 0)
                 + DECODE (ABS (h2), 3, 1, 0)
                 + DECODE (ABS (h3), 3, 1, 0)
                 + DECODE (ABS (v1), 3, 1, 0)
                 + DECODE (ABS (v2), 3, 1, 0)
                 + DECODE (ABS (v3), 3, 1, 0)
                 + DECODE (ABS (d1), 3, 1, 0)
                 + DECODE (ABS (d2), 3, 1, 0) = 1
                 AND ROWNUM < 5)
   LOOP
      rec                     := rec + 1;
      retval.EXTEND;
      retval (retval.COUNT)   := oxotype (c1.row1, c1.winner);
   END LOOP;

   RETURN retval;
END;
/

Which is fine for all results, let's whittle it down a bit. This was difficult and I borrow some other code from elsewhere.

create or replace FUNCTION bin2dec (binval IN CHAR) RETURN NUMBER IS
  i                 NUMBER;
  digits            NUMBER;
  result            NUMBER := 0;
  current_digit     CHAR(1);
  current_digit_dec NUMBER;
BEGIN
  digits := LENGTH(binval);
  FOR i IN 1..digits LOOP
     current_digit := SUBSTR(binval, i, 1);
     current_digit_dec := TO_NUMBER(current_digit);
     result := (result * 2) + current_digit_dec;
  END LOOP;
  RETURN result;
END bin2dec;
/

CREATE OR REPLACE FUNCTION control.whowins (board IN VARCHAR2)
   RETURN rettab
AS
   retval   rettab;
   rec      NUMBER := 0;
   m        BOOLEAN := FALSE;
BEGIN
   retval   := rettab ();

   FOR c1
      IN (SELECT distinct row1,
                 DECODE (
                    LEAST (h1, h2, h3, v1, v2, v3, d1, d2),
                    -3, 'X',
                    'O')
                    winner,
                 match
            FROM (SELECT a.row1,
                         r1 + r2 + r3 h1,
                         r4 + r5 + r6 h2,
                         r7 + r8 + r9 h3,
                         r1 + r4 + r7 v1,
                         r2 + r5 + r8 v2,
                         r3 + r6 + r9 v3,
                         r1 + r5 + r9 d1,
                         r3 + r5 + r7 d2,
                         rnt,
                         match
                    FROM (WITH r1 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r2 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r3 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r4 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r5 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r6 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r7 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r8 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r9 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL  
select distinct * from table(whowins('XX_OO__X_'));
 
OXO           W
------------- -
XXO           O
OOO
XX_

XXX           X
OO_
_XO

XXX           X
OO_
OX_

XX_           O
OOO
XXO

XXO           O
OOX
OX_

XX_           O
OOO
_X_

XX_           O
OOO
_XX

XX_           O
OOO
OXX

XXX           X
OOX
OXO

XXX           X
OO_
OXO

XX_           O
OOO
XX_

XXO           O
OOX
OXX

XXO           O
OOO
_XX

XXO           O
OO_
OXX


14 rows selected.

SQL>

Don't know why I need the select distinct as yet.

Cheers, Gary.

14 08 2011
Charles Hooper

Gary,

Wow! Great explanations as you stepped through the development of the final solution. As a bonus, you did not use my partial solution, which I tried to use as the basis for a solution without much success for the better part of a couple of hours.

Posting that much detail as quickly as you did, a couple of minor problems are to be expected – see his followup post for the un-Wordpress mangled version of the WHOWINS function. Most people will also have to drop the “control.” characters in front of the TYPE definition name as well as the function name. Some of the intermediate SQL statements result in errors (when tested on 11.2.0.2) – focus on Gary’s description and the transformation to the SQL statement rather than whether or not an error is produced.

So that people do not get hung up on the minor glitches, what I encountered:

And take out rows where both sides win, which is impossible.

SELECT row1, h1, h2, h3, v1, v2, v3, d1, d2, rnt
                                            *
ERROR at line 1:
ORA-00918: column ambiguously defined

Now we need to find if X or O win, which is a -3 (X) or 3 (O).

                  FROM r1, r2, r3, r4, r5, r6, r7, r8, r9) a
                  *
ERROR at line 72:
ORA-00936: missing expression

So I can add the winner of the game in there too. (actually shows wins by O rather than X)

Well done.

12 08 2011
Gary Colbran

Final function did not go in……

CREATE OR REPLACE FUNCTION control.whowins (board IN VARCHAR2)
   RETURN rettab
AS
   retval   rettab;
   rec      NUMBER := 0;
   m        BOOLEAN := FALSE;
BEGIN
   retval   := rettab ();

   FOR c1
      IN (SELECT distinct row1,
                 DECODE (
                    LEAST (h1, h2, h3, v1, v2, v3, d1, d2),
                    -3, 'X',
                    'O')
                    winner,
                 match
            FROM (SELECT a.row1,
                         r1 + r2 + r3 h1,
                         r4 + r5 + r6 h2,
                         r7 + r8 + r9 h3,
                         r1 + r4 + r7 v1,
                         r2 + r5 + r8 v2,
                         r3 + r6 + r9 v3,
                         r1 + r5 + r9 d1,
                         r3 + r5 + r7 d2,
                         rnt,
                         match
                    FROM (WITH r1 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r2 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r3 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r4 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r5 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r6 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r7 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r8 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4),
                               r9 AS (SELECT ROWNUM - 2 rn
                                        FROM DUAL
                                      CONNECT BY LEVEL < 4)
                          SELECT r1.rn r1,
                                 r2.rn r2,
                                 r3.rn r3,
                                 r4.rn r4,
                                 r5.rn r5,
                                 r6.rn r6,
                                 r7.rn r7,
                                 r8.rn r8,
                                 r9.rn r9,
                                    DECODE (r1.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r2.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r3.rn,  0, '_',  -1, 'X',  'O')
                                 || CHR (13)
                                 || CHR (10)
                                 || DECODE (r4.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r5.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r6.rn,  0, '_',  -1, 'X',  'O')
                                 || CHR (13)
                                 || CHR (10)
                                 || DECODE (r7.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r8.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r9.rn,  0, '_',  -1, 'X',  'O')
                                    row1,
                                    DECODE (r1.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r2.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r3.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r4.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r5.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r6.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r7.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r8.rn,  0, '_',  -1, 'X',  'O')
                                 || DECODE (r9.rn,  0, '_',  -1, 'X',  'O')
                                    match,
                                   r1.rn
                                 + r2.rn
                                 + r3.rn
                                 + r4.rn
                                 + r5.rn
                                 + r6.rn
                                 + r7.rn
                                 + r8.rn
                                 + r9.rn
                                    rnt
                            FROM r1, r2, r3, r4, r5, r6, r7, r8, r9) a
                   WHERE rnt IN (0, -1)
                         AND (   (ABS (r1 + r2 + r3) = 3)
                              OR (ABS (r4 + r5 + r6) = 3)
                              OR (ABS (r7 + r8 + r9) = 3)
                              OR (ABS (r1 + r4 + r7) = 3)
                              OR (ABS (r2 + r5 + r8) = 3)
                              OR (ABS (r3 + r6 + r9) = 3)
                              OR (ABS (r1 + r5 + r9) = 3)
                              OR (ABS (r3 + r5 + r7) = 3)))
           WHERE   DECODE (ABS (h1), 3, 1, 0)
                 + DECODE (ABS (h2), 3, 1, 0)
                 + DECODE (ABS (h3), 3, 1, 0)
                 + DECODE (ABS (v1), 3, 1, 0)
                 + DECODE (ABS (v2), 3, 1, 0)
                 + DECODE (ABS (v3), 3, 1, 0)
                 + DECODE (ABS (d1), 3, 1, 0)
                 + DECODE (ABS (d2), 3, 1, 0) = 1)
   LOOP
      m   := FALSE;

      FOR i IN 0 .. LENGTH (board) - 1
      LOOP
         IF (BITAND (
                bin2dec (TRANSLATE (c1.match, '_OX', '001')),
                bin2dec (TRANSLATE (board, '_OX', '001'))) =
                bin2dec (TRANSLATE (board, '_OX', '001'))
             AND BITAND (
                    bin2dec (TRANSLATE (c1.match, '_OX', '010')),
                    bin2dec (TRANSLATE (board, '_OX', '010'))) =
                    bin2dec (TRANSLATE (board, '_OX', '010')))
         THEN
            rec                     := rec + 1;
            retval.EXTEND;
            retval (retval.COUNT)   := oxotype (c1.row1, c1.winner);
         END IF;
      END LOOP;
   END LOOP;

   RETURN retval;
END;
/

Cheers, Gary.

12 08 2011
Radoslav Golian

Not the best solution, but seem to be working :)

works in 11.2+

with all_combinations(board, next_player, lev, path, win) as (
 select '_X_'||'O_X'||'OX_' board,
        'O' next_player,
        1 lev,
        '1' path,
        0 win
 from dual
 union all  
 select regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv) board,                
        decode(ac.next_player, 'O', 'X', 'O') next_move,
        --case when ac.next_move = 'O' then 'X' else 'O' end next_move, -- I prefer case but it gives ora-600        
        lev + 1 lev,
        path ||'/' || x.lv path,
        case when 
         (
           mod(regexp_instr(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^([X]{3}|O{3}$)'), 3) = 1 -- horizontal
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^((X..){3}|(O..){3})$') --vertical
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^((.X.){3}|(.O.){3})$')
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^((..X){3}|(..O){3})$')
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^(X...X...X|O...O...O)$') --diagonal
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^(..X.X.X..|..O.O.O..)$')
         ) then 1 else 0 end win
 from all_combinations ac, (select level lv from dual connect by level <= 9) x
 where x.lv <= regexp_count(ac.board, '_') -- genereate new cases for all empty positions
 and ac.win = 0 -- stop solving, when it is solved..
)
select * from all_combinations
--where win = 1 

14 08 2011
Charles Hooper

Radoslav,

Wow, a recursive SQL statement with regular expressions type solution for the problem. I thought that regular expressions might be part of the solution, but I did not have any idea how to get started with such a solution. I worked with regular expressions way back when I was learning Turbo Pascal, but there have not been enough occasions for me to revisit the logic of regular expressions since that time.

I made a slight adjustment at the end of your SQL statement to add line breaks so that it was easier to confirm that your solution worked:

COLUMN BOARD FORMAT A5
COLUMN WIN FORMAT 9
 
with all_combinations(board, next_player, lev, path, win) as (
 select '_X_'||'O_X'||'OX_' board,
        'O' next_player,
        1 lev,
        '1' path,
        0 win
 from dual
 union all
 select regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv) board,
        decode(ac.next_player, 'O', 'X', 'O') next_move,
        --case when ac.next_move = 'O' then 'X' else 'O' end next_move, -- I prefer case but it gives ora-600
        lev + 1 lev,
        path ||'/' || x.lv path,
        case when
         (
           mod(regexp_instr(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^([X]{3}|O{3}$)'), 3) = 1 -- horizontal
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^((X..){3}|(O..){3})$') --vertical
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^((.X.){3}|(.O.){3})$')
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^((..X){3}|(..O){3})$')
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^(X...X...X|O...O...O)$') --diagonal
           or regexp_like(regexp_replace(ac.board, '_' , ac.next_player, 1, x.lv), '^(..X.X.X..|..O.O.O..)$')
         ) then 1 else 0 end win
 from all_combinations ac, (select level lv from dual connect by level <= 9) x
 where x.lv <= regexp_count(ac.board, '_') -- genereate new cases for all empty positions
 and ac.win = 0 -- stop solving, when it is solved..
)
select
  SUBSTR(BOARD,1,3)||CHR(10)||SUBSTR(BOARD,4,3)||CHR(10)||SUBSTR(BOARD,7,3) BOARD,
  WIN,
  NEXT_PLAYER
from
  all_combinations
--where win = 1 ;
BOARD WIN N
----- --- -
_X_     0 O
O_X
OX_

OX_     1 X
O_X
OX_

_XO     0 X
O_X
OX_

_X_     0 X
OOX
OX_

_X_     0 X
O_X
OXO

XXO     0 O
O_X
OX_

_XO     1 O
OXX
OX_

_XO     0 O
O_X
OXX

XX_     0 O
OOX
OX_

_XX     0 O
OOX
OX_

_X_     0 O
OOX
OXX

XX_     0 O
O_X
OXO

_XX     0 O
O_X
OXO

_X_     1 O
OXX
OXO

XXO     1 X
OOX
OX_

XXO     0 X
O_X
OXO

OXO     1 X
O_X
OXX

_XO     1 X
OOX
OXX

XXO     1 X
OOX
OX_

XX_     0 X
OOX
OXO

OXX     1 X
OOX
OX_

_XX     0 X
OOX
OXO

OX_     1 X
OOX
OXX

_XO     1 X
OOX
OXX

XXO     0 X
O_X
OXO

XX_     0 X
OOX
OXO

OXX     1 X
O_X
OXO

_XX     0 X
OOX
OXO

XXO     1 O
OXX
OXO

XXX     1 O
OOX
OXO

XXX     1 O
OOX
OXO

XXO     1 O
OXX
OXO

XXX     1 O
OOX
OXO

XXX     1 O
OOX
OXO


34 rows selected.

Very well done, and efficient because it does not waste time generating 362,000 combinations (like my initial starting point) of which only a small number of combinations are useful.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Follow

Get every new post delivered to your Inbox.

Join 139 other followers

%d bloggers like this: