3d_tic_tac_toe/3d_tic_tac_toe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3D Tic-Tac-Toe\n",
    "\n",
    "## Objective and Prerequisites\n",
    "\n",
    "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.\n",
    "\n",
    "This is example 17 from the fifth edition of Model Building in Mathematical Programming by H. Paul Williams on pages 272 and 327 – 328.\n",
    "\n",
    "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.\n",
    "\n",
    "**Download the Repository** <br /> \n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). \n",
    "\n",
    "---\n",
    "## Problem Description\n",
    "\n",
    "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.\n",
    "\n",
    "---\n",
    "## Model Formulation\n",
    "\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$\\text{isX}_{ijk} \\in [0,1]$: Does cell $(i,j,k)$ contain an $X$ ($isX=1$) or an $O$ ($isX=0$)?\n",
    "\n",
    "$\\text{isLine}_{l} \\in [0,1]$: Does line/diagonal $l$ contain 3 of the same symbol?\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "- **Lines**: Minimize the number of completed lines or diagonals\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Minimize} \\quad Z = \\sum_{l \\in \\text{Lines}}\\text{isLine}_l\n",
    "\\end{equation}\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Take turns**: The board must contain 14 $X$'s and 13 $O$'s ($X$ goes first).\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{ijk} \\text{isX}_{ijk} = 14\n",
    "\\end{equation}\n",
    "\n",
    "- **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.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{isLine}_l == 0 \\implies isX[l_0] + isX[l_1] + isX[l_2] >= 1 \\quad \\forall l \\in \\text{Lines}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{isLine}_l == 0 \\implies isX[l_0] + isX[l_1] + isX[l_2] <= 2 \\quad \\forall l \\in \\text{Lines}\n",
    "\\end{equation}\n",
    "\n",
    "---\n",
    "## Python Implementation\n",
    "\n",
    "We import the Gurobi Python Module."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Python 3.11 & Gurobi 11.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Deployment\n",
    "\n",
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = []\n",
    "size = 3\n",
    "\n",
    "for i in range(size):\n",
    "    for j in range(size):\n",
    "        for k in range(size):\n",
    "            if i == 0:\n",
    "                lines.append(((0,j,k), (1,j,k), (2,j,k)))\n",
    "            if j == 0:\n",
    "                lines.append(((i,0,k), (i,1,k), (i,2,k)))\n",
    "            if k == 0:\n",
    "                lines.append(((i,j,0), (i,j,1), (i,j,2)))\n",
    "            if i == 0 and j == 0:\n",
    "                lines.append(((0,0,k), (1,1,k), (2,2,k)))\n",
    "            if i == 0 and j == 2:\n",
    "                lines.append(((0,2,k), (1,1,k), (2,0,k)))\n",
    "            if i == 0 and k == 0:\n",
    "                lines.append(((0,j,0), (1,j,1), (2,j,2)))\n",
    "            if i == 0 and k == 2:\n",
    "                lines.append(((0,j,2), (1,j,1), (2,j,0)))\n",
    "            if j == 0 and k == 0:\n",
    "                lines.append(((i,0,0), (i,1,1), (i,2,2)))\n",
    "            if j == 0 and k == 2:\n",
    "                lines.append(((i,0,2), (i,1,1), (i,2,0)))\n",
    "lines.append(((0,0,0), (1,1,1), (2,2,2)))\n",
    "lines.append(((2,0,0), (1,1,1), (0,2,2)))\n",
    "lines.append(((0,2,0), (1,1,1), (2,0,2)))\n",
    "lines.append(((0,0,2), (1,1,1), (2,2,0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we create our model and our decision variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n"
     ]
    }
   ],
   "source": [
    "model = gp.Model('Tic_Tac_Toe')\n",
    "isX = model.addVars(size, size, size, vtype=GRB.BINARY, name=\"isX\")\n",
    "isLine = model.addVars(lines, vtype=GRB.BINARY, name=\"isLine\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we create the constraints.  The first states the board will contain 14 X's (and 13 O's):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "x14 = model.addConstr(isX.sum() == 14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "for line in lines:\n",
    "    model.addGenConstrIndicator(isLine[line], False, isX[line[0]] + isX[line[1]] + isX[line[2]] >= 1)\n",
    "    model.addGenConstrIndicator(isLine[line], False, isX[line[0]] + isX[line[1]] + isX[line[2]] <= 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we set the optimization objective, which is to minimize the number of completed lines."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.setObjective(isLine.sum())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we perform the optimization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 1 rows, 76 columns and 27 nonzeros\n",
      "Model fingerprint: 0xcbf7569f\n",
      "Model has 98 general constraints\n",
      "Variable types: 0 continuous, 76 integer (76 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+01, 1e+01]\n",
      "Presolve added 98 rows and 0 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 99 rows, 76 columns, 419 nonzeros\n",
      "Variable types: 0 continuous, 76 integer (76 binary)\n",
      "Found heuristic solution: objective 7.0000000\n",
      "\n",
      "Root relaxation: objective 0.000000e+00, 46 iterations, 0.00 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0    0.00000    0    8    7.00000    0.00000   100%     -    0s\n",
      "H    0     0                       5.0000000    0.00000   100%     -    0s\n",
      "     0     0    0.00000    0   18    5.00000    0.00000   100%     -    0s\n",
      "H    0     0                       4.0000000    0.00000   100%     -    0s\n",
      "     0     0    0.00000    0   19    4.00000    0.00000   100%     -    0s\n",
      "     0     0    0.00000    0    8    4.00000    0.00000   100%     -    0s\n",
      "     0     0    0.00000    0   21    4.00000    0.00000   100%     -    0s\n",
      "     0     0    0.50000    0    8    4.00000    0.50000  87.5%     -    0s\n",
      "     0     0    0.66667    0   18    4.00000    0.66667  83.3%     -    0s\n",
      "     0     0    1.00000    0    8    4.00000    1.00000  75.0%     -    0s\n",
      "     0     0    1.00000    0    8    4.00000    1.00000  75.0%     -    0s\n",
      "     0     2    1.00000    0    8    4.00000    1.00000  75.0%     -    0s\n",
      "\n",
      "Cutting planes:\n",
      "  MIR: 4\n",
      "  Inf proof: 9\n",
      "  Zero half: 14\n",
      "\n",
      "Explored 2139 nodes (14255 simplex iterations) in 0.26 seconds\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 3: 4 5 7 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 4.000000000000e+00, best bound 4.000000000000e+00, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "model.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Result\n",
    "\n",
    "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)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkMAAAElCAYAAADnfOZBAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAB6FJREFUeJzt3bFqHekZgOFvbENsTNjGwp1hlwU1UZW9AKVzketQmcZXsYUrd6rcuEnnOzgXkFROY0MIId2yLCy4i+JJkRROE8kso2PP+zydYMz5vuP5Na84Ai3rug4AQNWdYw8AAHBMYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIu3fdBcuyXMzMxczM/fv3f/vkyZPNh7ptHz58mDt39tmFe97t3bt3P67renLbr1s4E/+8+tdc7fQv9dxbZre7/eNvf3UmNrLnM/Gru0v+ObF8yt8mOz09Xd++ffuLBvscHQ6HOT8/P/YYm9jzbsuy/Hld1++OOcNez8SLV6/n+Ztrf1b6Ij07u9rtbn///vfOxEb2fCZePn2Yf07sMwUBAG5IDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKTdu+6CZVkuZuZiZubk5GQOh8PWM926H376eV68en3sMTbx+MHsdrdj+fhMPHp0ssv39/GDmWdnV8ceYxNff3V3Xj59eOwxNvG774/zuoXnxJ7vmz0/A2/q2hha1/VyZi5nZk5PT9fz8/OtZ7p1L169nudvrn0rvkjPzq52u9uxfHwmnnzz7brH93fP983Lpw9nj9/HjqnwnDgcDru9b/b8DLwpH5MBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBp9667YFmWi5m5mJl59OhkXrx6vflQt+3rr+7Oy6cPjz3GJn746ed5dnZ17DE28Ycjve7HZ+Lk5GT+uMN75/3797s+E3v8PnZMhefE4wezy71m/rNb/TlxbQyt63o5M5czM0+++XZ9/ubaf/LFefn04Zyfnx97jE28ePV69vh/dkwfn4nT09N1j/fO4XBwJrixwnPi2dnVbu+bPe92Uz4mAwDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAECaGAIA0sQQAJAmhgCANDEEAKSJIQAgTQwBAGliCABIE0MAQJoYAgDSxBAAkCaGAIA0MQQApIkhACBNDAEAaWIIAEgTQwBAmhgCANLEEACQJoYAgDQxBACkiSEAIE0MAQBpYggASBNDAEDasq7r/79gWS5m5uK/X/5mZv6y9VBH8Ghmfjz2EBvZ826n67r++rZf1Jn44u15N2diO3u+b/a8243OxLUx9D8XL8uf1nX97heN9Rna614zdivMsIW97jVjt8IMW9jrXjN2m/ExGQAQJ4YAgLRPjaHLTaY4vr3uNWO3rX0OM2xhr3vN2G1rn8MMW9jrXjN2+7TfGQIA2BsfkwEAaWIIAEgTQwBAmhgCANLEEACQ9m/gsTGrK+czQwAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 720x360 with 3 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "fig, ax = plt.subplots(1, 3, figsize=(10,5))\n",
    "for i in range(3):\n",
    "    ax[i].grid()\n",
    "    ax[i].set_xticks(range(4))\n",
    "    ax[i].set_yticks(range(4))\n",
    "    ax[i].tick_params(labelleft=False, labelbottom=False)\n",
    "    \n",
    "for cell in isX.keys():\n",
    "    if isX[cell].x > 0.5:\n",
    "        ax[cell[0]].add_patch(plt.Rectangle((cell[1],cell[2]), 1, 1))\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## References\n",
    "\n",
    "H. Paul Williams, Model Building in Mathematical Programming, fifth edition.\n",
    "\n",
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}