# 3D Tic-Tac-Toe

## Objective and Prerequisites

Try this logic programming example to learn how to solve the problem of arranging X’s and O’s on a three-dimensional Tic-Tac-Toe board so as to minimize the number of completed lines or diagonals. This example will show you how a binary programming model can be used to capture simple logical constraints.

This is example 17 from the fifth edition of Model Building in Mathematical Programming by H. Paul Williams on pages 272 and 327 – 328.

This modeling example is at the beginning level. We assume that you have some familiarity with Python and the Gurobi Python API, but you can hopefully pick up any missing concepts from the example.

**Download the Repository** <br /> 
You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). 


**Gurobi License** <br /> 
In order to run this Jupyter Notebook properly, you must have a Gurobi license. If you do not have one, you can request an 
[evaluation license](https://www.gurobi.com/downloads/request-an-evaluation-license/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-EDU-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_3D-Tic-Tac-Toe_COM_EVAL_GITHUB_&utm_term=logic-programing&utm_content=C_JPM)
as a *commercial user*, or download a 
[free license](https://www.gurobi.com/academia/academic-program-and-licenses/?utm_source=3PW&utm_medium=OT&utm_campaign=WW-MU-EDU-OR-O_LEA-PR_NO-Q3_FY20_WW_JPME_3D-Tic-Tac-Toe_ACADEMIC_EVAL_GITHUB_&utm_term=logic-programing&utm_content=C_JPM)
as an *academic user*.

---
## Problem Description

Given a 3-D tic-tac-toe board, where players take turns placing $X$'s and $O$'s, the game typically ends when one player completes a line or diagonal; that is, when they manage to place their symbols in three cells that form a line or diagonal in the grid.  The twist that is tackled here is that the game continues until every cell contains a symbol, and the goal is to arrange the symbols to minimize the number of completed lines or diagonals.

---
## Model Formulation


### Decision Variables

$\text{isX}_{ijk} \in [0,1]$: Does cell $(i,j,k)$ contain an $X$ ($isX=1$) or an $O$ ($isX=0$)?

$\text{isLine}_{l} \in [0,1]$: Does line/diagonal $l$ contain 3 of the same symbol?

### Objective Function

- **Lines**: Minimize the number of completed lines or diagonals

\begin{equation}
\text{Minimize} \quad Z = \sum_{l \in \text{Lines}}\text{isLine}_l
\end{equation}

### Constraints

- **Take turns**: The board must contain 14 $X$'s and 13 $O$'s ($X$ goes first).

\begin{equation}
\sum_{ijk} \text{isX}_{ijk} = 14
\end{equation}

- **Lines**: For a line to not be complete, one cell must have a different value.  The simple observation here is that the sum of the corresponding 3 binary variables would be 3 if they are all $X$ and 0 if they were all $O$.   We need to forbid those outcomes whenever $isLine_l == 0$.  Note that $l_0$ is the first cell in line $l$, $l_1$ is the second, and $l_2$ is the third.

\begin{equation}
\text{isLine}_l == 0 \implies isX[l_0] + isX[l_1] + isX[l_2] >= 1 \quad \forall l \in \text{Lines}
\end{equation}

\begin{equation}
\text{isLine}_l == 0 \implies isX[l_0] + isX[l_1] + isX[l_2] <= 2 \quad \forall l \in \text{Lines}
\end{equation}

---
## Python Implementation

We import the Gurobi Python Module.


```python
import gurobipy as gp
from gurobipy import GRB

# tested with Python 3.7.0 & Gurobi 9.0
```

## Model Deployment

We first create a list of all possible lines and diagonals in a 3-D tic-tac-toe board.  Each is represented as a Python tuple with 3 entries, where each entry gives the (i,j,k) position of the corresponding cell.  There are 49 in total.


```python
lines = []
size = 3

for i in range(size):
    for j in range(size):
        for k in range(size):
            if i == 0:
                lines.append(((0,j,k), (1,j,k), (2,j,k)))
            if j == 0:
                lines.append(((i,0,k), (i,1,k), (i,2,k)))
            if k == 0:
                lines.append(((i,j,0), (i,j,1), (i,j,2)))
            if i == 0 and j == 0:
                lines.append(((0,0,k), (1,1,k), (2,2,k)))
            if i == 0 and j == 2:
                lines.append(((0,2,k), (1,1,k), (2,0,k)))
            if i == 0 and k == 0:
                lines.append(((0,j,0), (1,j,1), (2,j,2)))
            if i == 0 and k == 2:
                lines.append(((0,j,2), (1,j,1), (2,j,0)))
            if j == 0 and k == 0:
                lines.append(((i,0,0), (i,1,1), (i,2,2)))
            if j == 0 and k == 2:
                lines.append(((i,0,2), (i,1,1), (i,2,0)))
lines.append(((0,0,0), (1,1,1), (2,2,2)))
lines.append(((2,0,0), (1,1,1), (0,2,2)))
lines.append(((0,2,0), (1,1,1), (2,0,2)))
lines.append(((0,0,2), (1,1,1), (2,2,0)))
```

Next we create our model and our decision variables.


```python
model = gp.Model('Tic_Tac_Toe')
isX = model.addVars(size, size, size, vtype=GRB.BINARY, name="isX")
isLine = model.addVars(lines, vtype=GRB.BINARY, name="isLine")
```

    Using license file c:\gurobi\gurobi.lic


Now we create the constraints.  The first states the board will contain 14 X's (and 13 O's):


```python
x14 = model.addConstr(isX.sum() == 14)
```

The remaining constraints establish the relationship between the $isLine[]$ and $isX[]$ variables.  A line is complete if all three cells contain the same symbol.  In our model, this would correspond to three associated $isX[]$ variables summing to either 3 (all $X$) or 0 (all $O$).  For our purposes, it is enough to enforce the condition that if $isLine[] = 0$, the sum must be strictly between these two values.


```python
for line in lines:
    model.addGenConstrIndicator(isLine[line], False, isX[line[0]] + isX[line[1]] + isX[line[2]] >= 1)
    model.addGenConstrIndicator(isLine[line], False, isX[line[0]] + isX[line[1]] + isX[line[2]] <= 2)
```

Finally, we set the optimization objective, which is to minimize the number of completed lines.


```python
model.setObjective(isLine.sum())
```

Now we perform the optimization.


```python
model.optimize()
```

    Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
    Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
    Optimize a model with 1 rows, 76 columns and 27 nonzeros
    Model fingerprint: 0xcbf7569f
    Model has 98 general constraints
    Variable types: 0 continuous, 76 integer (76 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+00]
      Objective range  [1e+00, 1e+00]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+01, 1e+01]
    Presolve added 98 rows and 0 columns
    Presolve time: 0.00s
    Presolved: 99 rows, 76 columns, 419 nonzeros
    Variable types: 0 continuous, 76 integer (76 binary)
    Found heuristic solution: objective 7.0000000
    
    Root relaxation: objective 0.000000e+00, 46 iterations, 0.00 seconds
    
        Nodes    |    Current Node    |     Objective Bounds      |     Work
     Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time
    
         0     0    0.00000    0    8    7.00000    0.00000   100%     -    0s
    H    0     0                       5.0000000    0.00000   100%     -    0s
         0     0    0.00000    0   18    5.00000    0.00000   100%     -    0s
    H    0     0                       4.0000000    0.00000   100%     -    0s
         0     0    0.00000    0   19    4.00000    0.00000   100%     -    0s
         0     0    0.00000    0    8    4.00000    0.00000   100%     -    0s
         0     0    0.00000    0   21    4.00000    0.00000   100%     -    0s
         0     0    0.50000    0    8    4.00000    0.50000  87.5%     -    0s
         0     0    0.66667    0   18    4.00000    0.66667  83.3%     -    0s
         0     0    1.00000    0    8    4.00000    1.00000  75.0%     -    0s
         0     0    1.00000    0    8    4.00000    1.00000  75.0%     -    0s
         0     2    1.00000    0    8    4.00000    1.00000  75.0%     -    0s
    
    Cutting planes:
      MIR: 4
      Inf proof: 9
      Zero half: 14
    
    Explored 2139 nodes (14255 simplex iterations) in 0.26 seconds
    Thread count was 8 (of 8 available processors)
    
    Solution count 3: 4 5 7 
    
    Optimal solution found (tolerance 1.00e-04)
    Best objective 4.000000000000e+00, best bound 4.000000000000e+00, gap 0.0000%


---
## Result

The optimal solution completes only 4 lines or diagonals.  We can visualize the result using matplotlib (we've peeled off the third dimension of the 3-D tic-tac-toe board).


```python
import matplotlib.pyplot as plt
%matplotlib inline

fig, ax = plt.subplots(1, 3, figsize=(10,5))
for i in range(3):
    ax[i].grid()
    ax[i].set_xticks(range(4))
    ax[i].set_yticks(range(4))
    ax[i].tick_params(labelleft=False, labelbottom=False)
    
for cell in isX.keys():
    if isX[cell].x > 0.5:
        ax[cell[0]].add_patch(plt.Rectangle((cell[1],cell[2]), 1, 1))

plt.show()
```

---
## References

H. Paul Williams, Model Building in Mathematical Programming, fifth edition.

Copyright © 2020 Gurobi Optimization, LLC


```python

```

0003cf5b62e07f7d1355368f0d31846af515cadb
ipynb
Jupyter Notebook
3d_tic_tac_toe/3d_tic_tac_toe.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2019-07-11T15:08:37.000Z
2022-03-25T10:12:54.000Z
3d_tic_tac_toe/3d_tic_tac_toe.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2020-10-29T12:34:13.000Z
2022-02-28T14:16:43.000Z
3d_tic_tac_toe/3d_tic_tac_toe.ipynb
anupamsharmaberkeley/Gurobi_Optimization
701200b5bfd9bf46036675f5b157b3d8e3728ff9
Apache-2.0
2019-11-11T17:04:54.000Z
2022-03-30T21:34:20.000Z
Qwen/Qwen-72B
1. YES
2. YES