Solving the GCHQ puzzle with Python and CPLEX Cloud

GCHQ.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# GCHQ Christmas Puzzle\n",
    "\n",
    "## Author [Jean-François Puget](https://www.ibm.com/developerworks/community/blogs/jfp/)\n",
    "\n",
    "Solving the [GCHQ Christmas Puzzle](http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx) with DOcloud and Python.\n",
    "\n",
    "The code in this notebook is described at length in this [post](https://www.ibm.com/developerworks/community/blogs/jfp/entry/solving_the_gchq_christmas_puzzle_as_a_mip_with_python)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the description of the problem to solve.  \n",
    "\n",
    "*In this type of grid-shading puzzle, each square is either black or white. Some of the black squares have already been filled in for you.\n",
    "Each row or column is labelled with a string of numbers. The numbers indicate the length of all consecutive runs of black squares, and are displayed in the order that the runs appear in that line. For example, a label \"2 1 6\" indicates sets of two, one and six black squares, each of which will have at least one white square separating them.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src =\"https://www.ibm.com/developerworks/community/blogs/jfp/resource/BLOGS_UPLOADED_IMAGES/grid-shading-puzzle.jpg\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first import useful packages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "import sys\n",
    "\n",
    "if sys.version_info < (3,):\n",
    "    range = xrange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data\n",
    "Adapted from (https://github.com/matthewearl/gchq-xmas/blob/master/gchq-xmas.py)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "nrows = 25\n",
    "ncols = 25\n",
    "\n",
    "row_clues = [\n",
    "    [7, 3, 1, 1, 7,],\n",
    "    [1, 1, 2, 2, 1, 1,],\n",
    "    [1, 3, 1, 3, 1, 1, 3, 1,],\n",
    "    [1, 3, 1, 1, 6, 1, 3, 1,],\n",
    "    [1, 3, 1, 5, 2, 1, 3, 1,],\n",
    "    [1, 1, 2, 1, 1,],\n",
    "    [7, 1, 1, 1, 1, 1, 7,],\n",
    "    [3, 3,],\n",
    "    [1, 2, 3, 1, 1, 3, 1, 1, 2,],\n",
    "    [1, 1, 3, 2, 1, 1,],\n",
    "    [4, 1, 4, 2, 1, 2,],\n",
    "    [1, 1, 1, 1, 1, 4, 1, 3,],\n",
    "    [2, 1, 1, 1, 2, 5,],\n",
    "    [3, 2, 2, 6, 3, 1,],\n",
    "    [1, 9, 1, 1, 2, 1,],\n",
    "    [2, 1, 2, 2, 3, 1,],\n",
    "    [3, 1, 1, 1, 1, 5, 1,],\n",
    "    [1, 2, 2, 5,],\n",
    "    [7, 1, 2, 1, 1, 1, 3,],\n",
    "    [1, 1, 2, 1, 2, 2, 1,],\n",
    "    [1, 3, 1, 4, 5, 1,],\n",
    "    [1, 3, 1, 3, 10, 2,],\n",
    "    [1, 3, 1, 1, 6, 6,],\n",
    "    [1, 1, 2, 1, 1, 2,],\n",
    "    [7, 2, 1, 2, 5,],\n",
    "]\n",
    "\n",
    "col_clues = [\n",
    "    [7, 2, 1, 1, 7,],\n",
    "    [1, 1, 2, 2, 1, 1,],\n",
    "    [1, 3, 1, 3, 1, 3, 1, 3, 1,],\n",
    "    [1, 3, 1, 1, 5, 1, 3, 1,],\n",
    "    [1, 3, 1, 1, 4, 1, 3, 1,],\n",
    "    [1, 1, 1, 2, 1, 1,],\n",
    "    [7, 1, 1, 1, 1, 1, 7,],\n",
    "    [1, 1, 3,],\n",
    "    [2, 1, 2, 1, 8, 2, 1,],\n",
    "    [2, 2, 1, 2, 1, 1, 1, 2,],\n",
    "    [1, 7, 3, 2, 1,],\n",
    "    [1, 2, 3, 1, 1, 1, 1, 1,],\n",
    "    [4, 1, 1, 2, 6,],\n",
    "    [3, 3, 1, 1, 1, 3, 1,],\n",
    "    [1, 2, 5, 2, 2,],\n",
    "    [2, 2, 1, 1, 1, 1, 1, 2, 1,],\n",
    "    [1, 3, 3, 2, 1, 8, 1,],\n",
    "    [6, 2, 1,],\n",
    "    [7, 1, 4, 1, 1, 3,],\n",
    "    [1, 1, 1, 1, 4,],\n",
    "    [1, 3, 1, 3, 7, 1,],\n",
    "    [1, 3, 1, 1, 1, 2, 1, 1, 4,],\n",
    "    [1, 3, 1, 4, 3, 3,],\n",
    "    [1, 1, 2, 2, 2, 6, 1,],\n",
    "    [7, 1, 3, 2, 1, 1,],\n",
    "]\n",
    "\n",
    "grid_clues = [\n",
    "  (3, 3), (3, 4), (3, 12), (3, 13), (3, 21),\n",
    "  (8, 6), (8, 7), (8, 10), (8, 14), (8, 15), (8, 18),\n",
    "  (16, 6), (16, 11), (16, 16), (16, 20),\n",
    "  (21, 3), (21, 4), (21, 9), (21, 10), (21, 15), (21, 20), (21, 21),\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Docloud init\n",
    "\n",
    "You have to cut and past your own url and key here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "key = 'api_4a46f594-c48b-45cd-a78d-b1632fbf2400'\n",
    "url = 'https://api-oaas.docloud.ibmcloud.com/job_manager/rest/v1/'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's initialize and test our configuration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "* system is: Windows 64bit\n",
      "* CPLEX wrapper is not available\n",
      "* Numpy is present, version is 1.9.2\n",
      "* Matplotlib is present, version is 1.4.3\n",
      "Warning: CPLEX DLL not found, will solve on DOcloud\n"
     ]
    }
   ],
   "source": [
    "from docplex.mp.context import DOcloudContext\n",
    "from docplex.mp.environment import Environment\n",
    "from docplex.mp.model import Model\n",
    "\n",
    "docloud_context = DOcloudContext(url, key)\n",
    "\n",
    "env = Environment()\n",
    "env.print_information()\n",
    "\n",
    "model = Model('GCHQ', docloud_context=docloud_context)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Seems we're in business."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We must represent the grid solution.  The simplest way is to create one binary variable for each cell of the grid.  A binary variable can only be set to 0 or to 1.  We'll say that the binary variable grid[i][j] is set to 1 if the cell i,j in the grid is black, and 0 otherwise.  The goal of solving the problem will be to set these decision variables to 0 or 1 so that the resulting grid is a solution of the GCHQ puzzle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "rows = range(nrows)\n",
    "cols = range(ncols)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We pass a string as argument to the variable constructor.  It becomes the variable's name.  It can be useful for debugging when printing arrays of variables."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "grid = [[model.binary_var(\"x_%d_%d\" % (i,j)) for j in cols] for i in rows]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "grid_t = [[grid[i][j] for i in rows] for j in cols]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also need to represent where we put the blocs of black cells corresponding to the clues provided for each row and for each column of the puzzle.   Let's represent these decisions with binary variables again.\n",
    "\n",
    "row_vars[i][c][j] is set to:\n",
    "1 if the bloc corresponding to the c-th clue in the i-th row starts at the j-th column,\n",
    "0 otherwise.\n",
    "\n",
    "col_vars[j][c][i] is set to:\n",
    "1 if the bloc corresponding to the c-th clue in the j-th column starts at the i-th row,\n",
    "0 otherwise."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "row_vars = [[[model.binary_var(\"%s_%d_%d_%d_%d\" %('r',i,c,j,length)) \\\n",
    "              for j in cols]\\\n",
    "             for c,length in enumerate(clues)] \\\n",
    "            for i,clues in enumerate(row_clues)]\n",
    "\n",
    "col_vars = [[[model.binary_var(\"%s_%d_%d_%d_%d\" %('c',j,c,i,length)) \\\n",
    "              for i in rows] \\\n",
    "             for c,length in enumerate(clues)] \\\n",
    "            for j,clues in enumerate(col_clues)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Grid clues:the grid variables corresponding to the black cells should be set to 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for (i,j) in grid_clues:\n",
    "    model.add_constraint(grid[i][j] == 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each clue, a bloc must be set.  The bloc must start at least length cells before the right edge.  The corresponding grid cell must be set to 1. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i,row_clue in enumerate(row_clues):\n",
    "    row_var = row_vars[i]\n",
    "    for c,length in enumerate(row_clue):\n",
    "        vars = row_var[c]\n",
    "        model.add_constraint(model.sum(vars) == 1)\n",
    "    \n",
    "        for j in range(ncols-length+1, ncols):\n",
    "            model.add_constraint(vars[j] == 0)\n",
    "\n",
    "        for j in range(ncols-length+1):\n",
    "            for k in range(length):\n",
    "                model.add_constraint(vars[j] <= grid[i][j+k])\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar constraints for columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for j,col_clue in enumerate(col_clues):\n",
    "    col_var = col_vars[j]\n",
    "    for c,length in enumerate(col_clue):\n",
    "        vars = col_var[c]\n",
    "        model.add_constraint(model.sum(vars) == 1)\n",
    "    \n",
    "        for i in range(nrows-length+1, nrows):\n",
    "            model.add_constraint(vars[i] == 0)\n",
    "\n",
    "        for i in range(nrows-length+1):\n",
    "            for k in range(length):\n",
    "                model.add_constraint(vars[i] <= grid[i+k][j])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A cell is black if and only if one row block covers it"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for i,row_clue in enumerate(row_clues):\n",
    "    row_var = row_vars[i]\n",
    "    for j in cols:\n",
    "        row_clue_l = range(len(row_clue))\n",
    "        block_vars = [row_var[k][l] for k in row_clue_l \\\n",
    "                      for l in cols if l <= j and j < l + row_clue[k]]\n",
    "        model.add_constraint(model.sum(block_vars) == grid[i][j])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for j,col_clue in enumerate(col_clues):\n",
    "    col_var = col_vars[j]\n",
    "    for i in rows:\n",
    "        col_clue_l = range(len(col_clue))\n",
    "        block_vars = [col_var[k][l] for k in col_clue_l \\\n",
    "                      for l in rows if l <= i and i < l + col_clue[k]]\n",
    "        model.add_constraint(model.sum(block_vars) == grid[i][j])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If a bloc in row i of length length starts at column j, then the next bloc cannot start before column j+length+1. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "for i,row_clue in enumerate(row_clues):\n",
    "    row_var = row_vars[i]\n",
    "    for c,length in enumerate(row_clue[:-1]):\n",
    "        for j in cols:\n",
    "            for k in cols:\n",
    "                if j + length >= k:\n",
    "                    model.add_constraint(row_var[c][j] + row_var[c+1][k] <= 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Idem for column blocs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "for j,col_clue in enumerate(col_clues):\n",
    "    col_var = col_vars[j]\n",
    "    for c,length in enumerate(col_clue[:-1]):\n",
    "        for i in rows:\n",
    "            for k in rows:\n",
    "                if i + length >= k:\n",
    "                    model.add_constraint(col_var[c][i] + col_var[c+1][k] <= 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Model: GCHQ\n",
      " - number of variables: 8550\n",
      "   - binary=8550, integer=0, continuous=0\n",
      " - number of constraints: 116631\n",
      " -   LE=114681, EQ=1950, GE=0, RNG=0\n",
      " - parameters: defaults\n",
      "* No objective to optimize - searching for a feasible solution\n",
      "* model solved with objective: 1\n"
     ]
    }
   ],
   "source": [
    "model.print_information()\n",
    "model.solve()\n",
    "model.report()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Display"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "solution = np.zeros((nrows,ncols))\n",
    "\n",
    "for i in rows:\n",
    "    for j in cols:\n",
    "        solution[i,j] = grid[i][j].solution_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x29d08908>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAAFsCAYAAABvrmq/AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAACj9JREFUeJzt3D2IpVcdx/H/f40RFV8ggWAkKFhZaSFqTBNEUTshKjZC\nQBBTWIgvlRY2vmCjINoEC1NYKIpNbCKxEJNUQkoFG40hkGBAE/Etx2LuusMyOzdz5u5vzr3z+cDC\n7tzZ+zz3PM/9cri78+8xRgGQceWiTwDgMhFdgCDRBQgSXYAg0QUIEl2AINEFCBJdgCDR5cJ09ye7\n+4nu/nt3P9Pdj3f3A8cef3d3P9zdf+3u5zbfe//msXu7+08nPOevu/vTx/78xu7+QXc/3d0vdPeT\nV58DLoLociG6+wtV9Z2q+lZV3THGuKOqPltV93T3rd19d1X9qqoeraq3jTFuq6oHqurDW556bH5V\nd99aVY9U1V1V9d6qen1Vfamqvtndn9/9q4Lt2o8Bk9bdb6iqp6rqU2OMn9/ge35TVb8bY3zuBo/f\nW1UPjTHuuu7rj26+/sPNjvfrVfXWMcY/jn3PJ6rqwap68xjjb7t4TfBy2elyEe6uqldV1S9OerC7\nX1NHO9OfTjx3H/v9B6vq4ePB3fhZVb26qt4z8fxwLqLLRbi9qp4dY7x09Qvd/dvNZ7cvVtW76uje\nfHrL89y5+Tv//1VV9xx7/LaTnmOM8Z+qenZzHhB1y0WfAJfSc1V1e3dfuRreMcb7qqo2/zj22qp6\nqareVFW/P+V5/nKDjxeueraq7rz+L3X3LXUU3GfO8yJghp0uF+GxqvpnVX30Bo+/uPmej53zOI9U\n1Uc2H1ccd19VvVBVj5/z+eHMRJe4McbzVfW1qvp+d9/X3a/r7ivd/c462uWOqvpyVd3f3V/s7tuq\nqrr7Hd3945dxiKuf6z5UVX+uqp9091u6+5Xd/aGq+m5VffWEz3rhpvPxAhdijPHt7n6qjuL6ozra\nef5x8+fHxhj/7u7311Gcv9Ld/62qP1TV944/zY2efnOMf3X3B6rqG1X1RB19xvuKqvrMGOPBm/Cy\nYCv/ZYxLY/NZ7i+r6vkxxscv+ny4nHy8wKWx+V8L91XVk9399os+Hy4nO12AIDtdgKBT/yGtu22D\nASaMMfqkr/vfCwua+cin+8Tru5TVP8qaXcPU9Zpdv324Ny4THy8ABIkuQJDoAgSJLkCQ6AIEiS5A\nkOgCBIkuQJDoAgSJLkDQzn8MePUf9Uw7xB/B3IcfR505x+S9u/r7ZPXzS9vlvWunCxAkugBBogsQ\nJLoAQaILECS6AEGiCxAkugBBogsQJLoAQaILECS6AEGiCxC08yljs1afxrX61KXVz69q7hxn74vV\nJ5rNnN8+XGPv4+3sdAGCRBcgSHQBgkQXIEh0AYJEFyBIdAGCRBcgSHQBgkQXIEh0AYJEFyBomYE3\nnM/soJHkAJDVh6HMOtTXxc1hpwsQJLoAQaILECS6AEGiCxAkugBBogsQJLoAQaILECS6AEGiCxAk\nugBBogsQZMrYgZidFmZC1jXWkAQ7XYAg0QUIEl2AINEFCBJdgCDRBQgSXYAg0QUIEl2AINEFCBJd\ngCDRBQhaZuDN7LAR9sehXuNDfV0zrMV2droAQaILECS6AEGiCxAkugBBogsQJLoAQaILECS6AEGi\nCxAkugBBogsQJLoAQTufMtbdu35KXobZdZ+ZCpW8xvvwulLHSk7w8j6+eex0AYJEFyBIdAGCRBcg\nSHQBgkQXIEh0AYJEFyBIdAGCRBcgSHQBgkQXIGjrwJvkkA3yVh9ssg/3nzXkeqfdE3a6AEGiCxAk\nugBBogsQJLoAQaILECS6AEGiCxAkugBBogsQJLoAQaILECS6AEFbp4yddYLS7ESj5KSmmXM0Seqa\n5FrMHstkrWtm1nAf7qd9fR/b6QIEiS5AkOgCBIkuQJDoAgSJLkCQ6AIEiS5AkOgCBIkuQJDoAgSJ\nLkDQ1oE3K0sO5TjUASqrD6851AFKScnBMDPHWn39qs5+jqetn50uQJDoAgSJLkCQ6AIEiS5AkOgC\nBIkuQJDoAgSJLkCQ6AIEiS5AkOgCBG0deLPLQQ+7tg9DTVJDXpJrwfklh//MSB5rH97Hu2SnCxAk\nugBBogsQJLoAQaILECS6AEGiCxAkugBBogsQJLoAQaILECS6AEGiCxC0dcpYSnKy1urTmlafQDVr\n9UloyUlyKx+nav2perPHWuEetNMFCBJdgCDRBQgSXYAg0QUIEl2AINEFCBJdgCDRBQgSXYAg0QUI\nEl2AoJ0PvFl9aEhaagBIcvjPoQ4aWv1Y3iOHwU4XIEh0AYJEFyBIdAGCRBcgSHQBgkQXIEh0AYJE\nFyBIdAGCRBcgSHQBgkQXIGjnU8ZmJaddJacaJV/X6lIT12aPxeFb4X6y0wUIEl2AINEFCBJdgCDR\nBQgSXYAg0QUIEl2AINEFCBJdgCDRBQgSXYCgrQNvzjroYYWBEitZ/XUd6vCf1Y81Y/V7qSq3FrNS\n1/i049jpAgSJLkCQ6AIEiS5AkOgCBIkuQJDoAgSJLkCQ6AIEiS5AkOgCBIkuQJDoAgRtnTK2y+k6\nu5acaJacnrQPa7i65DVeffrXoV7jfWWnCxAkugBBogsQJLoAQaILECS6AEGiCxAkugBBogsQJLoA\nQaILECS6AEFbB96sPsxjdanBK/twnVYfNDRr9eu1+r1xqIOrbsROFyBIdAGCRBcgSHQBgkQXIEh0\nAYJEFyBIdAGCRBcgSHQBgkQXIEh0AYJEFyBo65SxFaby7FryNR3i+s1afRpXctrVjH24l2bW4rJN\nXLPTBQgSXYAg0QUIEl2AINEFCBJdgCDRBQgSXYAg0QUIEl2AINEFCBJdgKCtA29WGBBx2ezDYJMZ\n+zC8JnWs1Ye8rL5+VfvbJjtdgCDRBQgSXYAg0QUIEl2AINEFCBJdgCDRBQgSXYAg0QUIEl2AINEF\nCNo68OasDnVYy6zVh3Ikh6GsPhhm1urnuPp7cnb9kvfTWY912nHsdAGCRBcgSHQBgkQXIEh0AYJE\nFyBIdAGCRBcgSHQBgkQXIEh0AYJEFyBIdAGCdj5lbJZJTeeTPL/Vr1XVYU5P24d1n7H6e2vX7HQB\ngkQXIEh0AYJEFyBIdAGCRBcgSHQBgkQXIEh0AYJEFyBIdAGCRBcgaJmBN5zPPgxDSQ2GmbUPa3iI\nZtd9X4c82ekCBIkuQJDoAgSJLkCQ6AIEiS5AkOgCBIkuQJDoAgSJLkCQ6AIEiS5AkOgCBJkydsnt\n66Smy2j2Wh3quidf11nX/rRzs9MFCBJdgCDRBQgSXYAg0QUIEl2AINEFCBJdgCDRBQgSXYAg0QUI\nEl2AoGUG3iQHrxyifRiG4hqfz+y1mln3fTjWjBXuQTtdgCDRBQgSXYAg0QUIEl2AINEFCBJdgCDR\nBQgSXYAg0QUIEl2AINEFCBJdgKCdTxlLTgzimss2qWmbmfVYfVJbct1XX4tZK5yfnS5AkOgCBIku\nQJDoAgSJLkCQ6AIEiS5AkOgCBIkuQJDoAgSJLkCQ6AIE9WmDLbp7/ckmAAsaY5w4XefU6AKwWz5e\nAAgSXYAg0QUIEl2AINEFCPofkwAtpzsfs80AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x29a19198>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "dpi = 4\n",
    "width = nrows/dpi\n",
    "height = ncols/dpi\n",
    "fig, ax = plt.subplots(figsize=(width, height),dpi=dpi)\n",
    "ax.set_title('GCHQ')\n",
    "ax.set_xticks([])\n",
    "ax.set_yticks([])\n",
    "ax.set_xticklabels([])\n",
    "ax.set_yticklabels([])\n",
    "ax.imshow(solution,cmap='Greys',origin='upper',interpolation='nearest')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "fig.savefig('gchq_solution.png')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "That's it!"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}