Skip to content

Instantly share code, notes, and snippets.

@jfpuget

jfpuget/docplex_sudoku.ipynb

Created March 3, 2016 15:04
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jfpuget/23a58b26214bd8ced655 to your computer and use it in GitHub Desktop.
Save jfpuget/23a58b26214bd8ced655 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
docplex_sudoku.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# A Sudoku Web App Using CPLEX Python Modeling API\n",
"\n",
"## Author: [Jean-François Puget](https://www.ibm.com/developerworks/community/blogs/jfp?lang=en)\n",
"\n",
"We will be solving sudoku problems using docplex and the model from a [post](https://www.ibm.com/developerworks/community/blogs/jfp/entry/solving_sudoku_in_python_with_docplex) of mine.\n",
"\n",
"We will use the Python client for the DOcloud service. It can be installed with pip."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Initialization\n",
"\n",
"First, let's group all imports at the beginning"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from docplex.mp.model import Model\n",
"from docplex.mp.context import Context\n",
"from docplex.mp.environment import Environment\n",
"\n",
"import numpy as np\n",
"\n",
"import matplotlib.pyplot as plt\n",
"%matplotlib inline\n",
"\n",
"import os\n",
"import json\n",
"import jinja2\n",
"from flask import Flask, request, jsonify\n",
"\n",
"import tornado.httpserver\n",
"from tornado.wsgi import WSGIContainer"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Then let us initialize the Docloud connections. We print information to check the status.\n",
"You will need to enter your credentials."
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"* system is: Windows 64bit\n",
"* Python is present, version is 3.4.3\n",
"* docplex is present, version is (1, 0, 455)\n",
"* CPLEX wrapper is not available\n"
]
}
],
"source": [
"\n",
"docloud_context = Context.make_default_context(url=url, key=api_key)\n",
"\n",
"env = Environment()\n",
"env.print_information()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Seems everything is fine. \n",
"\n",
"# Model creation\n",
"\n",
"Let us model the sudoku problem. We will first describe the generic part of the model, i.e. the decision variables, the constraints, and the objective function that are independant from the input grid. We will then process the input grid to augment the model.\n",
"\n",
"We start with the creation of an empty model. "
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Warning: CPLEX DLL not found, will solve on DOcloud\n"
]
}
],
"source": [
"model = Model('sudoku_CPLEX', context=docloud_context)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The warning tells us that we are not using a local CPLEX install."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The variables\n",
"\n",
"The logic of the model is rather simple. we create a three dimension matrix of binary variables. \n",
"\n",
"Dimensions of the matrix are: rows, columns, and digits. \n",
" \n",
"Rows and columns are the rows and columns of the Sudoku grid. \n",
"There are 9 variables per cell of the grid, representing each possible digit.\n",
"\n",
"Binary variable ```sudoku[i][j][k]``` is 1 if and only if digit k+1 is placed on cell i,j. We use k+1 because indexing in Python starts at 0, while the digits start at 1."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"rows = range(0,9)\n",
"columns = range(0,9)\n",
"digits = range(0,9)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We represent the matrix with Python arrays. Variable ```sudoku[i][j][k]``` is named ```x_i_j_k```"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"sudoku = [[[model.binary_var(\"x_%d_%d_%d\" % (i,j,k)) for k in digits] for j in columns] for i in rows]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The constraints\n",
"\n",
"Our first constraint is that there is exactly one digit per square"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for i in rows:\n",
" for j in columns:\n",
" model.add_constraint(model.sum(sudoku[i][j]) == 1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our second constraint is that the digits on each line are different."
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for i in rows:\n",
" for k in digits:\n",
" model.add_constraint(model.sum(sudoku[i][j][k] for j in columns) == 1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our third constraint is that digits on each columns are different."
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"for j in columns:\n",
" for k in digits:\n",
" model.add_constraint(model.sum(sudoku[i][j][k] for i in rows) == 1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Our last constraint is that digits in 3x3 blocks are different. \n",
"\n",
"Expressing this one is a bit trickier. We need to get the list of variables in each 3x3 block, for a given digit.\n",
"\n",
"Let's look at the first 3x3 block.\n",
"\n",
"We can get the first 3 rows with ```sudoku[0:3]```\n",
"We then get the first three columns for each row with ```[c[0:3] for c in sudoku[0:3]]```\n",
"\n",
"This yields a list (rows) of lists (columns). We can use the overloaded sum operator to flatten the lists:\n",
"```sum([c[0:3] for c in sudoku[0:3]],[])```\n",
"\n",
"All digits in that block must be different. We collect the variables for a fixed digit k in this list, and we express that their sum is less than 1. \n",
"\n",
"```block_list = [c[0:3] for c in sudoku[0:3]]\n",
"block = sum(block_list,[])\n",
"for k in digits:\n",
" model.add_constraint(sum(c[k] for c in block) == 1)```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We repeat the above for each 3x3 block, iterating on block rows and bloc columns"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for block_row in range(0,3):\n",
" for block_column in range(0,3):\n",
" block_list = [cell[3*block_column:3*(block_column+1)] \\\n",
" for cell in sudoku[3*block_row:3*(block_row+1)]]\n",
" block = sum (block_list, [])\n",
" for k in digits:\n",
" model.add_constraint(sum(c[k] for c in block) == 1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## The objective\n",
"\n",
"Sudoku is a satisfaction problem, we only look for a feasible solution. There is no objective, hence the generic part of our model is complete. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Problem input\n",
"\n",
"Let us now look at the input of our web app. Input will be a string of the entries in the sudoku grid. If a cell is empty we accept either 0 or . as input. if a key is provided, then we accept the key itself. We can also have formatting characters, these will be stripped during processing. Here are two possible inputs, for one of the hard sudoku grid there is. Both input define the same problem to solve."
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"input1 = \"\"\"\n",
". . . |. . 6 |. . . \n",
". 5 9 |. . . |. . 8 \n",
"2 . . |. . 8 |. . . \n",
"------+------+------\n",
". 4 5 |. . . |. . . \n",
". . 3 |. . . |. . . \n",
". . 6 |. . 3 |. 5 4 \n",
"------+------+------\n",
". . . |3 2 5 |. . 6 \n",
". . . |. . . |. . . \n",
". . . |. . . |. . . \n",
"\"\"\"\n",
"\n",
"input2 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"List comprehensions can be used to remove all non numerical characters, and replace dots by 0."
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def sudoku_trim(input):\n",
" chars = ['0' if c == '.' else c for c in input if c in '.0123456789']\n",
" return ''.join(chars) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We also need to move back and forth between the string input and a 2D matric of integers like the following.\n",
"\n",
"```\n",
"[[0,0,0,0,0,6,0,0,0],\n",
"[0,5,9,0,0,0,0,0,8],\n",
"[2,0,0,0,0,8,0,0,0],\n",
"[0,4,5,0,0,0,0,0,0],\n",
"[0,0,3,0,0,0,0,0,0],\n",
"[0,0,6,0,0,3,0,5,4],\n",
"[0,0,0,3,2,5,0,0,6],\n",
"[0,0,0,0,0,0,0,0,0],\n",
"[0,0,0,0,0,0,0,0,0]]\n",
"```\n",
"\n",
"List comprehensions do a nice job here too."
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"def sudoku_string2int (input):\n",
" chars = [0 if c == '.' else int(c) for c in input if c in '.0123456789']\n",
" grid = [chars[i*9:(i+1)*9] for i in range(0,9)]\n",
" return grid\n",
"\n",
"def sudoku_int2string (solution):\n",
" flat_solution = sum(solution, [])\n",
" values = [str(cell) for cell in flat_solution]\n",
" return ''.join(values)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's try them"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'000006000059000008200008000045000000003000000006003054000325006000000000000000000'"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sudoku_trim(input1)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'000006000059000008200008000045000000003000000006003054000325006000000000000000000'"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sudoku_trim(input2)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"'000006000059000008200008000045000000003000000006003054000325006000000000000000000'"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sudoku_int2string(sudoku_string2int(input1))"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 0, 0, 0, 0, 6, 0, 0, 0],\n",
" [0, 5, 9, 0, 0, 0, 0, 0, 8],\n",
" [2, 0, 0, 0, 0, 8, 0, 0, 0],\n",
" [0, 4, 5, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 3, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 6, 0, 0, 3, 0, 5, 4],\n",
" [0, 0, 0, 3, 2, 5, 0, 0, 6],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0]]"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grid = sudoku_string2int(input1)\n",
"grid"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
"In order to solve that grid, we need to state that the non null entries define the corresponding binary variable:\n",
"```sudoku[i][j][k]``` is 1 if and only if digit k+1 is placed on cell i,j. "
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"for i in rows:\n",
" for j in columns:\n",
" if grid[i][j] > 0:\n",
" k = grid[i][j] - 1\n",
" model.add_constraint(sudoku[i][j][k] == 1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solving the input problem\n",
"We can now solve the problem. We print information about the model before and after solving it"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Model: sudoku_CPLEX\n",
" - number of variables: 729\n",
" - binary=729, integer=0, continuous=0\n",
" - number of constraints: 341\n",
" - LE=0, EQ=341, 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.export_as_lp()\n",
"model.solve()\n",
"model.report()\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The problem is solved. We can now retrieve the solution as a 3D matrix. "
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"raw_solution = [[[sudoku[i][j][k].solution_value for k in digits] for j in columns] for i in rows]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Digit in the first cell:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[0, 0, 0, 1, 0, 0, 0, 0, 0]"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"raw_solution[0][0]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is not very readable unfortunately. We need to map this to a digit. More generally, we need to map the raw solution to a 2D Sudoku grid. For that we need to replace the innermost arrays of 9 binary variables by the digit it represents. We do this by a numpy dot product"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"[[4, 8, 1, 9, 3, 6, 5, 2, 7],\n",
" [3, 5, 9, 2, 7, 1, 6, 4, 8],\n",
" [2, 6, 7, 4, 5, 8, 1, 9, 3],\n",
" [7, 4, 5, 6, 9, 2, 3, 8, 1],\n",
" [8, 1, 3, 5, 4, 7, 2, 6, 9],\n",
" [9, 2, 6, 8, 1, 3, 7, 5, 4],\n",
" [1, 9, 4, 3, 2, 5, 8, 7, 6],\n",
" [5, 3, 8, 7, 6, 9, 4, 1, 2],\n",
" [6, 7, 2, 1, 8, 4, 9, 3, 5]]"
]
},
"execution_count": 21,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solution = [[1+np.dot(raw_solution[i][j],digits) for j in columns] for i in rows]\n",
"\n",
"solution"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Seems our code is working!\n",
"Let us pretty print the result using matplotlib."
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAPcAAAD7CAYAAAC2TgIoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztnXtwVVXa5p83gH6NiLQT7iQIPYUhOYecHSBpL6jQoA6f\njaKhFZBLUPlDvgEz1qe2VaPQZaFTlkoosauwG21mUCmtRmkBL9CkJ2CB8CVpu5WGmYZwEQQEEknC\nLeSdP3JOmknnkLXWXmvnnM37q9qV7LDP++ydw5uz195rPw8xMwRBCB8Znb0DgiC4QZpbEEKKNLcg\nhBRpbkEIKdLcghBSpLkFIaR0tVWIiOSemiB0EsxMbX9m9ZObmZ0tzz//vNP6opFaGmE4hqA0kpE2\np+U1NTWicQVphOEYgtJIRto0tyAIeqRNc8+ePVs0riCNMBxDUBrJoMuds2sVImJbtQRBUIeIwK4v\nqLmkvLxcNK4gjTAcQ1AayUib5hYEQROLl+NZlYsXL7Lnefzzn/9c+TU6vPrqq5yXl8fRaJSnTZvG\n586ds64xZ84c7tOnD0ejUeu1EyxZsoQjkQhHIhEuKyuzXv/s2bNcWFjIsViMI5EIL1y40LoGM3Nt\nbS0XFxdzTk4O5+bm8rZt26zWHzx4MI8YMYJjsRiPHj3aam1m5oMHD/LYsWM5NzfX2Xuxe/dujsVi\n7Hkex2Ix7tmzp7JOvPf+uSfb+6HJotPcr776Kk+fPt1Jc3/77bc8ZMiQ1ob+xS9+wb/73e+s61RU\nVHBVVZWz5v7rX//K0WiUz549y01NTTxhwgT++9//bl2noaGBmZmbmpq4qKiIt2/fbl1j1qxZvGLF\nCmZmvnDhAtfV1VmtP2TIED558qTVmpdy5MgRrqqqYmbm06dP87Bhw3jXrl3O9C5evMj9+/fnAwcO\nKG2frLkDPy0/dOgQ1q9fj0cffVTrdTpjl4sXL6KhoQFNTU1obGzEgAEDrGvceuut+PGPf6y8va7G\nrl27UFRUhKuvvhpdunTBbbfdht///vdWNQCge/fuAIBz586hqakJRP90XcaXxg8//ICKigqUlJQA\nALp27YqePXtaqw+0fEA1Nzcrb6+r0a9fP8RiMQBAjx49MHz4cHz77bdWNS5l48aN+MlPfoKsrCzt\n115K4M1dWlqKl19+Wfk/kS4DBgzAk08+iezsbAwcOBC9evXC+PHjnWi5JBKJoKKiAqdOnUJjYyPW\nr1+PgwcPWtdpbm6G53no168fJkyYgNGjR1utv2/fPmRmZqKkpAQFBQWYO3cuzpw5Y1WDiFr3/c03\n37Rauy01NTWorq5GUVGRM43Vq1dj6tSp/gu193FuskDhtPzjjz/mefPmMTPz5s2b+Z577lE67dDh\n1KlTPG7cOD5x4gQ3NTXxfffdx6tWrbKuw8xcU1PjdMy9YsUKHjlyJN9+++38+OOPc2lpqTOturo6\nHjt2LH/99ddW6+7cuZO7du3KO3bsYGbmBQsW8HPPPWdV4/Dhw8zMfOzYMc7Pz+eKigqr9ROcPn2a\nR44cyR9++KGT+szM58+f58zMTD527Jjya5AKp+Vbt27F2rVrMXToUEydOhWbN2/GzJkzrWps3LgR\nQ4cOxfXXX48uXbrg/vvvxxdffGFVIyhKSkqwc+dOlJeXo1evXhg2bJgzrZ49e2Ls2LH45JNPrNYd\nNGgQsrKyMGrUKABAcXExKisrrWr0798fANC7d29MnjwZX375pdX6ANDU1ITi4mLMmDED9957r/X6\nCTZs2ICRI0eid+/evmsF2tyLFy/GgQMHsHfvXrz33nsYN24cVq5cqfRa1bFLdnY2tm3bhrNnz4KZ\nsWnTJgwfPtyqRgL+x1mLMjoax48fBwAcOHAAa9aswbRp06xqfP/996irqwMAnDlzBp9//jlycnKs\navTt2xdZWVnYs2cPAGDTpk3Izc21Vr+xsRH19fUAgIaGBnz22WeIRCJKr9V5L+bMmYPc3FwsWLBA\n+TW6GgDw7rvv2jklh8VHPlOFwsJCFBcXw/M8dOvWDZ7nYe7cudZ1pk2bhvLycpw4cQLZ2dlYtGhR\n60UjWzzwwAM4efIkunXrhjfeeEPpQpQOR44cwaxZs9Dc3Izm5mY8+OCDmDhxolUNAFi6dCmmT5+O\nCxcuYOjQoXjrrbes1T569CgmT54MIkJTUxOmT5+OO++801p9oOWMc9WqVYhGo/A8D0SExYsX4+67\n77aq09jYiI0bN2L58uVW6sn0U0FIc9J++qkgCHqkTXOHZR6waKRG/TBpJCNtmlsQBD2UxtxEVArg\nEQDNAP4CoISZz7fZRsbcgtAJGI+5iWgAgP8KoICZR6DlCvtD9ndREASbqJ6WdwFwDRF1BdAdwGF3\nu9Q+YRkfiUZq1A+TRjI6bG5mPgzgFQAHAHwLoJaZN7reMUEQ/NHhJBYi6gXgXgCDAdQB+ICIpjHz\nO223nT17Nm644QYAQK9evRCLxXDHHXcA+MdfMNP1xM9s1Uu2fqmWi/pBrN9xxx3O9RI/S9f66fx+\nl5eX4+233waA1n5rjw4vqBFRMYC7mPmx+PoMAEXM/G9ttpMLaoLQCfiZxHIAwE+J6F+o5TnNnwHY\nZXsHOyIs4yPRSI36YdJIhsqY+0sAHwCoAvBnAATAzuRXQRCcIXPLBSHNkbnlgnCFkTbNHZbxkWik\nRv0waSQjbZpbEARN2vNeMlmgaG0chFe2ax9rZvee4qnula1KEP7urn3RE6Sq3z5SybfctVe2ax/r\nIDzFU90rWxXX/u7M7n3RE6Sq336y5u6U03ITr2ydsQs79rEOwlM81b2yVTVc+7ub+qLraACp7bef\njE5pbtde2a59rIPyFE+QVl7ZAROELzqQpn777X2cmyzQOC1P4MorOwgf66A8xVPVK1sHl/7uQfii\np7rfPlLptDyBK6/sIHysg/AUT0ev7KAJwhc9Xf32A29uU69s1bFLUD7Wrj3FgdT2yta9BsKO/N1N\nfdF1NFLdbz8ZgfuWu/bKDsLHGnDvKZ6uXtltCcLf3aUvelC48NuXueWCkObI3HJBuMJIm+YOyzxg\n0UiN+mHSSEbaNLcgCHrImFsQ0hw/vuXDiKiKiCrjX+uIaL6b3RQEwRYqNkt7mNlj5gIAIwE0AFjj\nfM/aEJbxkWikRv0waSRDd8w9HsDfmdndRGpBEKygNeYmot8C+A9mfqOdf5MxtyB0AsnG3Moz1Iio\nG4BJAJ5Jto3LUAJZl3VZ1wsl0HnqaxKATy7z70ZPw6iyefNmp/VFI7U0wnAMQWnAwlNhUwG8q7G9\nIAidiGo+d3cA+wEMZebTSbZhlVqCINgl2ZhbJrEIQpqT9g+OhOWepGikRv0waSQjbZpbEAQ95LRc\nENKclDktP3ToEMaNG4e8vDxEo1EsXbrUukZdXR2mTJmC4cOHIy8vD9u3b7daf8+ePfA8DwUFBfA8\nD9ddd52T4wBanGILCgowadIkJ/VvuOEG5Ofnw/M8FBYWWq//2muvIRKJYMSIEZg+fTrOnz9vXeOR\nRx5B3759MWLECOu1E5SVlSEajTr7P3vu3DkUFRXB8zxEo1EsWrTIf9H27o+ZLFC8z21qtq9zv9DU\npN7knqSumb+uhokRvo6GaYCDioYfo32dYzANPlDV8BNCoXMcpmEdSBX3Uz9m+yr4Mak3QdfMXwdT\nI3wd2DDAQRXbRvvtYRp8oIqfEAodTMI6Lkt7HW+ywGCG2r59+3jw4MF8+vRp7dcmo7q6mgsLC3n2\n7NnseR4/9thj3NjYaK1+W+bMmcPLli1zUru4uJirqqq4vLzcWT7VkCFD2PM8HjVqFC9fvtx6/bKy\nMu7Rowf36dOHH374Yev1E7j0Rt+1axffeOONfPLkSW5oaOCbbrqJ58+fb13n4sWLHIvF+Nprr+Vn\nnnlG+XVIlU/uBPX19SguLkZZWRl69OhhrW5TUxMqKysxb948VFZWonv37njppZes1b+UCxcuYO3a\ntZgyZYr12uvWrUPfvn0Ri8WMrIFV2bp1KyorK7F+/XosW7YMW7ZssVa7trYWH330Efbv34/Dhw+j\nvr4e77zzjrX6QZGTk4Onn34aEyZMwMSJE+F5Hrp06WJdJyMjA1VVVTh06BC2b9+Ob775xl89S/ul\nhYnZvur9Qj8m9br3JE3M/FU1/Bjh6xyHaYCDioYfo/1UuwdtGkJhchy2wjo6pblNzfZV8GNSr4uJ\nmb8qfozwVfET4KCCC6P9ZLg8uwHMQyhUMQ3ruCztnaubLFAcc2/ZsoUzMjI4Pz+/NRt6w4YNyuML\nFaqrq3nUqFGcn5/PkydP5traWqv1mVuubGZmZvIPP/xgvXZbXI259+7d2/o+RCIRfvHFF61rLFy4\nkHNycjgajfLMmTP5/Pnz1jWmTp3K/fv356uuuoqzsrJa75TYZMyYMZyXl8exWMzJk15fffUVe57H\n+fn5HI1G+YUXXlB+LZKMuWUSiyCkOSkzicWUVBuDiYZbjTAcQ1AayUib5hYEQQ85LReENCftT8sF\nQdBDqbmJ6Doiep+IdhHR10RU5HrH2hKW8ZFopEb9MGkkQ9X9tAzAemaeQkRdAXR3uE+CIFigwzE3\nEfUEUMXMP+lgOxlzC0In4GfMPQTA90T0VjwvbDkR/cj+LgqCYBOV0/KuAAoAzGPmnUS0BC3BBM+3\n3dBlKMGSJUuchxxUV1fjiSeecFY/QcJY3kX9S2u7qg+4fz/k/U6+Xm4rlABAXwB7L1m/FcAf2tnO\ndOadEmExkBeN1KgfJg34mX5KRH8C8Bgz7yGi5wF0Z+an22zDKrUEQbCLL99yIsoH8BsA3QDsBVDC\nzHVttpHmFoROwNckFmb+MzOPZuYYM9/ftrGDICz3JEUjNeqHSSMZMkNNEEKKzC0XhDRH5pYLwhVG\n4M1tauivO3YxMfPX0TA189fRMA1X0NEwNdtX1TANoVCt78fMX+f3ZBquoKrhJFihvftjJgsM7nPr\nGPpfSWb+CVyHKwRhth9ECIWpmb+qRhDhCqbBCswpaG0M6Bn6J2bqqGBq5q+jwYZm/qoafsIVVDX8\nmO2rapiGUOi8F6Zm/joapuEKqhoughU6tblXr17txD20tLQUL7/8sv/EhstARJgwYQJGjx6NN998\n03r9ffv2ITMzEyUlJSgoKMDcuXNx5swZqxqRSAQVFRU4deoUGhsbsX79ehw8eNCqxqXU1NSguroa\nRUV2nxhubm6G53no169f63tikwEDBuDJJ59EdnY2Bg4ciF69emH8+PFWNVzQac2ta+ivOnbxY+av\nMwYzNfNX1fATrqCq4cdsX/caiG4IhU59UzN/VQ0/4QpX5H1uE0N/FfyY+etgauavip9wBR1MzfZ1\nMAmhMMGWmX9b/IQrdCrtDcRNFmheUHvooYf47bff1r54oEO5I7/vhoaG1nyz+vp6vvnmm/nTTz+1\nrnPbbbfx7t27mbnF//upp56yrnHs2DFmZt6/fz8PHz5c+aKdDjNmzODS0lLrdZmZjx8/3upL39jY\nyGPGjOF169ZZ1di+fTtHIhE+c+YMNzc386xZs/j111+3qsHckp0XiUS0X4ckF9Q6pbmDMvR31dxB\nmPkzBxOu4Nps33UIhR8zfx1chyv4CVZIqeY2ISyP54lGatQPk0ay5pYZaoIQUmRuuSCkOTK3XBCu\nMFR9y2uI6M9EVEVEdu/5KBKWZ29FIzXqh0kjGaq+5c0A7mDmUy53RhAEe6jaLO0DMIqZT1xmGxlz\nC0In4HfMzQA+J6IdRPSY3V0TBMEFqs19CzMXAJgIYB4R3epwn9olLOMj0UiN+mHSSIbSmJuZj8S/\nHieiNQAKAfzTkxIuQwmqq6t9vV7VpN5l/UtxVT+oddfvh7zfydfLFUMJVLLCugPIYOZ6IroGwGcA\nFjHzZ222kzG3IHQCycbcKp/cfQGsISKOb7+qbWMLgpB6dDjmZuZ93OJX7jFzlJnVHiq2TFjGR6KR\nGvXDpJEMmaEmCCFF5pYLQpojc8sF4QojbZo7LOMj0UiN+mHSSEbgzW1q7q6DE4P3S/BjhK+DafCB\nDibhDTqYhlCoYhp6oItpQIQOpgERSWnPwcFkgYITix9zdx38GLyrYmqEr4Np8IEOJuENpuiEUKhi\nGnqgi2lAhCp+AiKQKk4spubuOrgweG+LqRG+DmwYfKCKaXiDKTohFKqYhh7o4CcgQhU/ARHJCLS5\n/Zi7p9r4yNQIX0fDNPhAVcNPeIPJ+6ETQmFSXzf0QFXDT0CEqoaLgIhAm9uPuXuqYWqEr4Np8IEK\nfsIbTNANodBFN/RABz8BEar4CYhISnvn6iYLFMbc77//Pj/66KOt6ytXruR58+YpjSt0qampcTrm\nvpRf/epX/MorrzjVWLhwoVWNX/7yl5yVlcVDhgzhfv368TXXXMMzZsywVr8tH330Ed91111Oal+4\ncIHvuusuXrJkiZP63333HQ8ZMqR1vaKigu+55x4nWgmeffZZ/vWvf620LVJhzJ2dnY1t27bh7Nmz\nYGZs2rQJw4cPd6LFDj+Nvv/+e9TV1QEAzpw5g88//xw5OTlWNRobG1FfXw8AaGhowGeffYZIJGKt\n/uLFi3HgwAHs3bsX7733HsaNG4eVK1daq9+Wd99910kuHADMmTMHubm5WLBggZP6ffv2RVZWFvbs\n2QMA2LRpE3Jzc63rHD9+HABw4MABrFmzBtOmTfNXsL2ON1mg6Ftuau6u4/9savCuquHHCF9Vw0/w\nga5XdrlBeINuxK5uCIVqfT+hBzrHYBoQoaNhGhABCSUQjXTSCMMxBKWRrLllbrkgpDkyt1wQrjDS\nprlT7T63aLjVCMMxBKWRDOXmJqIMIqokorUud0gQBDsoj7mJqBTASAA9mfmfnjKQMbcgdA6+xtxE\nNAgttsa/sb1jgiC4QfW0/DUA/46WcIJOISzjI9FIjfph0khGh81NRP8K4CgzVwOg+CIIQoqjYm18\nC4BJRDQRwI8AXEtEK5l5ZtsNXYYSJH6WjibyQa8njOtd6iV+lq710/n9LrcVSvD/bUx0O4An5YKa\nIKQOaT+JJSzjI9FIjfph0kiGaj43AICZ/wTgT472RRAEi8jcckFIc9L+tFwQBD3SprnDMj4SjdSo\nHyaNZKRNcwuCoEl7D3mbLFA0a1iyZAlHIhGORCJcVlam/2R6Bxw8eJDHjh3Lubm5zjSYmWtra7m4\nuJhzcnI4NzeXt23bZl3j1Vdf5by8PI5Gozxt2rRWv3dbzJkzh/v06ePUa+7s2bNcWFjY6iizcOFC\nq/V3797d6sASi8W4Z8+eTt7zwYMH84gRIzgWi/Ho0aOt109w8eJF9jxPyxkHqeDE4sd4XZWwmNQH\nEeAQRHgDczABDsxuQg8SBBEQwWwWEpGsuQM9LfdjvK46dvFjUq+q4cekXmcMZhrgoKrhJ7xB5zhM\nAhxMxqq6oQc6GsxmARE6GrZDIgJtbhfG65dD16ReFT8m9ar4CXBINUwDHHTRCT3QxTQgQgc/IRHt\n0t7HuckCxTH3ihUreOTIkXz77bfz448/zqWlpcqnHzqcPn2aR44cyR9++KH12jt37uSuXbvyjh07\nmJl5wYIF/Nxzz1nVOHXqFI8bN45PnDjBTU1NfN999/GqVausajAH6+9eV1fHY8eO5a+//tp67fPn\nz3NmZiYfO3bMem1m5sOHDzMz87Fjxzg/P58rKiqs1v/4449bPfw3b96s5YuOVDgtB4CSkhLs3LkT\n5eXl6NWrF4YNG2Zdo6mpCcXFxZgxYwbuvfde6/UHDRqErKwsjBo1CgBQXFyMyspKqxobN27E0KFD\ncf3116NLly64//778cUXX1jVCJqePXti7Nix+OSTT6zX3rBhA0aOHInevXtbrw0A/fv3BwD07t0b\nkydPxpdffmm1/tatW7F27VoMHToUU6dOxebNmzFz5j89m6VF4M1taryuM3YxNalX1fBjUq+q4SfA\nQXcsyQYzC1U1TAMcdMfcJqEHqhp+AiJUNVyERGjNLbfBAw88gJMnT6Jbt2544403rKclbt26FatW\nrUI0GoXneSAiLF68GHfffbdVnaVLl2L69Om4cOEChg4dirfeestq/cLCQhQXF8PzPHTr1g2e52Hu\n3LlWNaZNm4by8nKcOHEC2dnZWLRoUetFQlscOXIEs2bNQnNzM5qbm/Hggw9i4sSJVjUaGxuxceNG\nLF++3GrdBEePHsXkyZNBRGhqasL06dNx5513OtGyicwtF4Q0R+aWC8IVRto0d1jmAYtGatQPk0Yy\n0qa5BUHQo8MxNxFdDeB/A7gKLRfgPmDmRe1sJ2NuQegEko25lS6oEVF3Zm4koi4AtgKYz8xfttlG\nmlsQOgFfF9SYuTH+7dVo+fQOvIvDMj4SjdSoHyaNZKgmjmQQURWA7wB8zsw73O6WIAh+UZrEwszN\nADwi6gngQyLKZeZv2m4nvuWpsS6+5eF+v8td+JYDABH9dwANzPxqm5/LmFsQOgHjMTcRZRLRdfHv\nfwRgAoC/2d/FyxOW8ZFopEb9MGkkQ+W0vD+A3xFRBlr+GKxm5vVud0sQBL/I3HJBSHNkbrkgXGGk\nTXOHZXwkGqlRP0wayUib5hYEQZP2vJdMFih6qAXhle3aGz2Bice0Kq79vpmD83h37fnt2t89KG90\nUy98pIJvObN7r+wgvNETmHhM6+Da7zsoj3eXnt9B+LtfiktvdFMv/GTNHfhpualXturYJQhvdMDc\nY1pHw8TvW0cjCI93wMzzW6e+a3/3S3Hlje7HCz8ZoRtzB+WNbt1juh2C8vsG3Hm8A249v4P2d3fl\nje7EC7+9j3OTBYqn5czuvbJde6P78Zg2waXfN7Nbj3dmt57fQfm7M7v1RvfjhY9UOS0PAtfe6C48\npi+HS79v1x7vgFvP7yD93V16o7vwwu+U5uZ/fNorozM+cu2N7sdjWlXD1O9bRwNw7/Fu6vmtWj8o\nf3fArTe6Hy/8ZATuWx6EV7Zrb/QgCMLvOwiPd9ee30H4uwPuvdEB+174MrdcENIcmVsuCFcYadPc\nYZkHLBqpUT9MGslIm+YWBEEPGXMLQprjx2ZpEBH9kYi+JqK/ENF8N7soCIJNVE7LmwD8N2bOA3AT\ngHlEpHbD1SJhGR+JRmrUD5NGMjpsbmb+jpmr49/XA9gFYKDrHRMEwR9aY24iugFAOYBIvNEv/TcZ\ncwtCJ5BszK08Q42IegD4AMCCto2dwGUogazLuqzrhRKoPvHVFcAnaGls30+FmbB582an9UUjtTTC\ncAxBacDnU2ErAHzDzGWK2wuC0Mmo5HPfgpZ87r+gJd2TATzLzJ+02Y47qiUIgn185XMrCkhzC0In\nkPYPjoTlnqRopEb9MGkkI22aWxAEPeS0XBDSnJQ6Lb/hhhuQn58Pz/NQWFhotfa5c+dQVFQEz/MQ\njUaxaNEiq/UTvPbaa4hEIhgxYgSmT5+O8+fPW62/Z88eeJ6HgoICeJ6H6667DkuXLrWqAQB1dXWY\nMmUKhg8fjry8PGzfvt1q/bKyMkSjUUSjUSf7n6C5uRkFBQWYNGmSk/qPPPII+vbtixEjRjipf+jQ\nIYwbNw55eXn2flft3R8zWaBxn9vEpF7nfqGpmb+qhh8jfJP7nrpG+Doapkb4Khp+AiJ0f08mARE6\nGqZhGqoafgIikErup2xgUq+DqZm/DqZG+CboGuGr4sII/1L8BEToYBoQoYNpmIYqfgIiktJex5ss\n0Pzk9jyPR40axcuXL1d+nSoXL17kWCzG1157LT/zzDPW6zMzl5WVcY8ePbhPnz788MMPO9FIMGfO\nHF62bJn1utXV1VxYWMizZ89mz/P4scce48bGRmv1d+3axTfeeCOfPHmSGxoa+KabbuL58+dbq5+g\nuLiYq6qquLy83Fm0E7N7v/0E+/bt48GDB/Pp06eVtkcqfXJv3boVlZWVWL9+PZYtW4YtW7ZYrZ+R\nkYGqqiocOnQI27dvxzfffGO1fm1tLT766CPs378fhw8fRn19Pd555x2rGgkuXLiAtWvXYsqUKdZr\nNzU1obKyEvPmzUNlZSW6d++Ol156yVr9nJwcPP3005gwYQImTpwIz/PQpUsXa/UBYN26dejbty9i\nsZiRZXaqUV9fj+LiYpSVlaFHjx6+anVKc5uY1JvcL9Q181fV8GOEr3scJkb4qhp+jPBVNUwDIlTr\n+wmISLX73LYDIgJvblOTelX8mPmr4scIXxcTI3xVXBjht8U0IEIVPwERurg+MzANiEhKe+fqJgsU\nx9x79+7l/Pz81tzpF198Uel1qnz11VfseR7n5+dzNBrlF154wWr9BAsXLuScnByORqM8c+ZMPn/+\nvHWNhoYGzszM5B9++MF67QTV1dU8atQozs/P58mTJ3Ntba3V+mPGjOG8vDyOxWLOn5ByOeaeOnUq\n9+/fn6+66irOyspqvcNgiy1btnBGRkZrb3iexxs2bFB6LZKMuWUSiyCkOSk1icWEVBsfiYZbjTAc\nQ1AayUib5hYEQQ85LReENCftT8sFQdBDJZTgt0R0lIi+CmKHkhGW8ZFopEb9MGkkQ+WT+y0Ad7ne\nEUEQ7KI05iaiwQD+wMxJn3eTMbcgdA4y5haEKwzlUAIVXIYSLFmyxHnIQXV1NZ544gln9RMkjOVd\n1L+0tqv6gPv3Q97v5OvllkMJBgP4qoNt/My+65CwGMiLRmrUD5MG/Ew/jWeE/YGZo5fZhlVqCYJg\nFz/53O8A+ALAMCI6QEQlLnZQEAS7qET4TmPmAcx8NTNnM/NbQexYW8JyT1I0UqN+mDSSIVfLBSGk\nyNxyQUhz5D63IFxhdEpzmxjhq45d/Jj5q2r4MZBX1fBjgq8zzjMNV9DRMAkM0KlvGnygquEn6ELn\nOKyHdbR3f8xkgcZ9bhMj/FQy8/djIK+qYWqCr6MRVLiCy8CAoIIPXAddMJuFdTCnkLWxqRF+YqaO\nDrpm/qoafgzkVTX8mODr/K5MwxVUNUwDA1Tr+wk+0Pk9mQZd6Giw5bCOwJt73759yMzMRElJCQoK\nCjB37lycOXPGidbq1audOYcmqKmpQXV1NYqKipzquGDAgAF48sknkZ2djYEDB6JXr14YP368VY3S\n0lK8/PI4QdLQAAAFqElEQVTLTlJfACASiaCiogKnTp1CY2Mj1q9fj4MHD1rXaW5uhud56NevHyZM\nmIDRo0db1yCi1tpvvvmm73qBN7epEb7u/UITM39dDRMD+VS6t+onXEFFw09ggOox+Ak+0HkvTIMu\ndDRsh3UE3tx+jPB1MDHz18G2gXxn4CdcQQU/gQE6mAYfmKAbdKGDSVjHZWlvIG6yQOOC2m233ca7\nd+9m5hb/76eeekr7IkJHPPTQQ/z2229br5tgxowZXFpa6qw+c0tmVCQScVZ/+/btHIlE+MyZM9zc\n3MyzZs3i119/3YlWuUNP8WPHjjEz8/79+3n48OHKSaWqHD9+vNXPvbGxkceMGcPr1q2zqtHQ0NCa\nDVZfX88333wzf/rpp0qvRZILap3S3K6N8F2b+fsxkFfFtQl+giDCFZjdNrfr4IMggi78hHWkVHOb\nEJbH80QjNeqHSSNZc8sMNUEIKTK3XBDSHJlbLghXGErNTUR3E9HfiGgPET3teqfaI5XuD4uGPM+d\nShrJUHFiyQDwOlq8y/MATCUiu4HXClRXV4vGFaQRhmMISiMZKp/chQD+DzPvZ+YLAN4DEPisjdra\nWtG4gjTCcAxBaSRDpbkHArh0su6h+M8EQUhh0uaCWk1NjWhcQRphOIagNJLR4a0wIvopgIXMfHd8\n/Rm03DT/H222k/tggtBJtHcrTKW5uwDYDeBnAI4A+BLAVGbe5WInBUGwQ4dxQsx8kYj+DcBnaDmN\n/600tiCkPtZmqAmCkFr4vqDmeoILEf2WiI4S0Ve2a1+iMYiI/khEXxPRX4hovgONq4loOxFVxTWe\nt60R18kgokoiWuuofg0R/Tl+HD4fOE6qcR0RvU9Eu+LviVWbGyIaFt//yvjXOtvvORGVEtFfiegr\nIlpFRFfZrK9Ee0+TqC5o+ePwf9ESFNgNQDWAHD8129G4FUAMHQQR+tToByAW/74HWq4xWD2OeO3u\n8a9dAGwDUOhAoxTA/wKw1tHvai+AH7t6L+IabwMoiX/fFUBPh1oZAA4DyLJYc0D893RVfH01gJku\nf2ftLX4/uZ1PcGHmLQBO2azZjsZ3zFwd/74ewC44uJfPzI3xb69Gy39aq2MiIhoEYCKA39is21YG\nDm+hElFPAGM4HlvFzE3M/IMrPQDjAfydmW0br3UBcA0RdQXQHS1/QALF75sUugku8UTTGICOzdT1\na2cQURWA7wB8zsw7LEu8BuDfYfmPRhsYwOdEtIOIHnNQfwiA74norfhp83Ii+pEDnQQPAnjXZkFm\nPgzgFQAHAHwLoJaZN9rUUCFtJrEEARH1APABgAXxT3CrMHMzM3sABgEoIqJcW7WJ6F8BHI2fgVB8\nccEtzFyAljOEeUR0q+X6XQEUAFgW12kE8IxlDQAAEXUDMAnA+5br9kLLGexgtJyi9yCiaTY1VPDb\n3N8CyL5kfVD8Z2lH/PTpAwD/k5k/cqkVP83cDOBui2VvATCJiPai5ZNoLBGttFgfAMDMR+JfjwNY\ng5ahmU0OATjIzDvj6x+gpdld8F8A/Ef8WGwyHsBeZj7JzBcB/B7AzZY1OsRvc+8A8J+JaHD8auBD\nAFxcpXX5SZRgBYBvmLnMRXEiyiSi6+Lf/wjABAB/s1WfmZ/llojloWh5H/7IzFatRomoe/zsBkR0\nDYA7AfzVpgYzHwVwkIgSFqY/A6DmI6zPVFg+JY9zAMBPiehfqMWw/WdouY4TKB1OYrkcHMAEFyJ6\nB8AdAP4TER0A8DxbzggnolsATAfwl/iYmAE8y8w2/Wv7A/hd/BHaDACrmXm9xfpB0BfAmvhU464A\nVjHzZw505gNYFT9t3gugxLYAEXVHyyfsXNu1mflLIvoAQBWAC/Gvy23rdIRMYhGEkCIX1AQhpEhz\nC0JIkeYWhJAizS0IIUWaWxBCijS3IIQUaW5BCCnS3IIQUv4feQzHN1vW45AAAAAASUVORK5CYII=\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x8caa320>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fig, ax = plt.subplots(figsize =(4,4))\n",
"\n",
"for i in rows:\n",
" for j in columns:\n",
" ax.text(i+0.5,8.5-j, str(solution[j][i]), va='center', ha='center')\n",
"\n",
"ax.set_xlim(0, 9)\n",
"ax.set_ylim(0, 9)\n",
"ax.set_xticks(rows)\n",
"ax.set_yticks(columns)\n",
"ax.grid()\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
"\n",
"# Wrapping up\n",
"\n",
"Let's wrap everything into an easy to reuse function"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def sudoku_solve(docloud_context, input):\n",
" model = Model('sudoku_CPLEX', context=docloud_context)\n",
" \n",
" rows = range(0,9)\n",
" columns = range(0,9)\n",
" digits = range(0,9)\n",
" \n",
" sudoku = [[[model.binary_var(\"x_%d_%d_%d\" % (i,j,k)) for k in digits] for j in columns] for i in rows]\n",
" \n",
" for i in rows:\n",
" for j in columns:\n",
" model.add_constraint(model.sum(sudoku[i][j]) == 1)\n",
" \n",
" for i in rows:\n",
" for k in digits:\n",
" model.add_constraint(model.sum(sudoku[i][j][k] for j in columns) == 1)\n",
" \n",
" for j in columns:\n",
" for k in digits:\n",
" model.add_constraint(model.sum(sudoku[i][j][k] for i in rows) == 1)\n",
" \n",
" for block_row in range(0,3):\n",
" for block_column in range(0,3):\n",
" block_list = [cell[3*block_column:3*(block_column+1)] for cell in sudoku[3*block_row:3*(block_row+1)]]\n",
" block = sum (block_list, [])\n",
" for k in digits:\n",
" model.add_constraint(sum(c[k] for c in block) == 1)\n",
" \n",
" grid = sudoku_string2int(input)\n",
" \n",
" for i in rows:\n",
" for j in columns:\n",
" if grid[i][j] > 0:\n",
" k = grid[i][j] - 1\n",
" model.add_constraint(sudoku[i][j][k] == 1)\n",
" \n",
" model.export_as_lp()\n",
" if not model.solve():\n",
" #Problem has no solution\n",
" return []\n",
" \n",
" raw_solution = [[[sudoku[i][j][k].solution_value for k in digits] for j in columns] for i in rows]\n",
" solution = [[1+np.dot(raw_solution[i][j], digits) for j in columns] for i in rows]\n",
" return solution\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Let us test our function."
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Warning: CPLEX DLL not found, will solve on DOcloud\n",
"* No objective to optimize - searching for a feasible solution\n"
]
},
{
"data": {
"text/plain": [
"[[3, 8, 7, 4, 5, 6, 9, 2, 1],\n",
" [4, 5, 9, 2, 7, 1, 6, 3, 8],\n",
" [2, 6, 1, 9, 3, 8, 4, 7, 5],\n",
" [9, 4, 5, 8, 1, 2, 7, 6, 3],\n",
" [7, 1, 3, 5, 6, 4, 2, 8, 9],\n",
" [8, 2, 6, 7, 9, 3, 1, 5, 4],\n",
" [1, 7, 4, 3, 2, 5, 8, 9, 6],\n",
" [5, 9, 8, 6, 4, 7, 3, 1, 2],\n",
" [6, 3, 2, 1, 8, 9, 5, 4, 7]]"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"input = \"\"\"\n",
". . . |. . 6 |. . . \n",
". 5 9 |. . . |. . 8 \n",
"2 . . |. . 8 |. . . \n",
"------+------+------\n",
". 4 5 |. . . |. . . \n",
". . 3 |. . . |. . . \n",
". . 6 |. . 3 |. 5 4 \n",
"------+------+------\n",
". . . |3 2 5 |. . 6 \n",
". . . |. . . |. . . \n",
". . . |. . . |. . . \n",
"\"\"\"\n",
"\n",
"solution = sudoku_solve(docloud_context, input)\n",
"\n",
"solution"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": false
},
"source": [
"# A web app\n",
"\n",
"We now turn this into a web app reusing the code from [A Sudoku Web App Based On DOcloud And Python](https://www.ibm.com/developerworks/community/blogs/jfp/entry/a_sudoku_web_app_based_on_docloud?lang=en)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"We define the input web page as a template because we do not want to hard code the service url in it. We will pass it as argument to the template. "
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"page = jinja2.Template(r\"\"\"\n",
"<html>\n",
"<head>\n",
"<title>A Sudoku Solver</title>\n",
"<script src=\"//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js\"></script>\n",
"\n",
"<script type=text/javascript>\n",
" $SCRIPT_ROOT = \"{{url}}\";\n",
"</script>\n",
"\n",
"<script language=\"javascript\"><!--\n",
"\n",
"function set_grid(str) { // set the grid given a sudoku string\n",
" if (str != null && str.length >= 81) {\n",
" for (var i = 0; i < 81; ++i) document.getElementById('C'+i).value = ''\n",
" for (var i = 0; i < 81; ++i)\n",
" if (str.substr(i, 1) >= 1 && str.substr(i, 1) <= 9)\n",
" document.getElementById('C'+i).value = str.substr(i, 1)\n",
" }\n",
"}\n",
"function solve_grid() {\n",
" if ($('#solve').val() == 'Solving') {\n",
" $('#grid_info').html('Wait for result please');\n",
" return;\n",
" };\n",
" var n_hints = 0;\n",
" s = '';\n",
" for (var i = 0; i < 81; ++i) { // get the sudoku string\n",
" var y = document.getElementById('C'+i).value\n",
" if (y >= 1 && y <= 9) {\n",
" s += ''+y;\n",
" ++n_hints;\n",
" } else s += '.'\n",
" }\n",
" if (n_hints >= 15) { // enough hints\n",
" $('#solve').val('Solving')\n",
" $.getJSON($SCRIPT_ROOT + '/solve', \n",
" {grid: s}, \n",
" function(data) {\n",
" $('#solve').val('Solve')\n",
" var x = data.result;\n",
" if (x.length == 0) {\n",
" $('#grid_info').html('No solution')\n",
" } else if (x.length == 81) {\n",
" set_grid(x);\n",
" $('#grid_info').html('First solution')\n",
" }\n",
" }); \n",
" } else $('#grid_info').html('No less than 15 hints are required')\n",
"}\n",
"\n",
"function draw_grid() { // generate the grid and fill it (called \"onLoad\")\n",
" // generate the grid\n",
" var s = '<table class=\"table\">\\n'\n",
" for (var i = 0; i < 9; ++i) {\n",
" s += '<tr>'\n",
" for (var j = 0; j < 9; ++j) {\n",
" var c = 'cell'\n",
" if ((i+1)%3 == 0 && j%3 == 0) c = 'cell3'\n",
" else if ((i+1)%3 == 0) c = 'cell1'\n",
" else if (j%3 == 0) c = 'cell2'\n",
" s += '<td class=\"' + c + '\"><input class=\"input\" type=\"text\" size=\"1\" maxlength=\"1\" id=\"C' + (i*9+j) + '\"></td>';\n",
" }\n",
" s += '</tr>\\n'\n",
" }\n",
" s += '</table>'\n",
" $('#grid').html(s)\n",
" // set the grid with input\n",
" input = '{{ input }}'\n",
" set_grid(input)\n",
" $('#grid_info').html('Fill the grid with at least 15 hints')\n",
" \n",
"}\n",
"\n",
"function clear_grid() {\n",
" if ($('#solve').val() == 'Solving') {\n",
" $('#grid_info').html('Wait for result please');\n",
" return;\n",
" };\n",
" $('#grid_info').html('Fill the grid with at least 15 hints')\n",
" for (var i = 0; i < 81; ++i)\n",
" document.getElementById('C'+i).value = ''\n",
"}\n",
"--></script>\n",
"<style type=\"text/css\"><!--\n",
" table { margin: 0 auto; }\n",
" body, td, p, span { font: 12px \"Lucida Grande\", \"Lucida Sans Unicode\", Arial, sans-serif; text-align: center;}\n",
" .input { border: 0px; width: 2em; height: 2em; text-align:center; }\n",
" .cell { width: 1em; height: 1em; border-bottom:1px solid; border-left:1px solid; padding: 0.3em}\n",
" .cell1 { width: 1em; height: 1em; border-bottom:2px solid; border-left:1px solid; padding: 0.3em}\n",
" .cell2 { width: 1em; height: 1em; border-bottom:1px solid; border-left:2px solid; padding: 0.3em}\n",
" .cell3 { width: 1em; height: 1em; border-bottom:2px solid; border-left:2px solid; padding: 0.3em}\n",
" .table { border-top:2px solid; border-right:2px solid; border-collapse:collapse }\n",
"--></style>\n",
"</head>\n",
"<body onLoad='draw_grid();'>\n",
"<h1>A Sudoku Solver</h1>\n",
"<span id=\"grid\"></span>\n",
"<p><span id=\"grid_info\" style=\"color: gray;\">Fill the grid with at least 15 hints</span></p>\n",
"<input type=\"button\" id=\"solve\" value=\"Solve\" onClick=\"solve_grid();\">&nbsp;<input type=\"button\" id=\"clear\" value=\"Clear\" onClick=\"clear_grid();\">\n",
"\n",
"</body>\n",
"</html>\n",
"\n",
"\"\"\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The base url of the service is queried as we do not want to assume anything about where this web app will be deployed. We will use one port on that base url. We selected port 9000 but any other one is useable provided it is exposed."
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"PORT = 9000\n",
"\n",
"host = os.getenv('HOST_PUBLIC_IP')\n",
"\n",
"if host == None: host = 'localhost' \n",
" \n",
"url = 'http://%s:%d' % (host , PORT)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's see what we get."
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"http://localhost:9000\n"
]
}
],
"source": [
"print(url)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So far so good, we will click on the above url to launch our web app. Before we do that, we need to run a server for it. Easiest way is to use Flask."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can now create the web service with Flask."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"flask_app = Flask('sudoku_demo')\n",
"\n",
"@flask_app.route('/')\n",
"def index():\n",
" '''Renders the template with the service url and an initial grid on HTTP GET.'''\n",
" return page.render(url=url, input=sudoku_trim(input))\n",
"\n",
"@flask_app.route('/solve/')\n",
"def solve():\n",
" '''Solves the input Sudoku and returns it on HTTP GET.'''\n",
" input = request.args.get('grid', '')\n",
" solution = sudoku_solve(docloud_context, input)\n",
" result = sudoku_int2string(solution)\n",
" return jsonify(result=result)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"#flask_app.run(host='0.0.0.0', port=PORT)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The run command above blocks the notebook kernel from returning for as long as the web server is running. To stop the server, we need to interrupt the kernel (*Kernel* &rarr; *Interrupt*). \n",
"\n",
"We can run the Flask application in a Tornado WSGIContainer if we want a non blocking web server."
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Warning: CPLEX DLL not found, will solve on DOcloud\n",
"* No objective to optimize - searching for a feasible solution"
]
}
],
"source": [
"server = tornado.httpserver.HTTPServer(WSGIContainer(flask_app))\n",
"server.listen(PORT, '0.0.0.0')"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"This concludes our web ap development. To run the web app, simply click on the url above. \n",
"\n",
"This web app can be deployed on any iPython notebook server. For instance we have shown how to deploy a similar web app on bluemix using a Docker container in [Deploy IPython Notebooks With Docker On Bluemix In Minutes](https://www.ibm.com/developerworks/community/blogs/jfp/entry/using_ipython_notebooks_in_docker_containers_on_bluemix_using_ibm_containers?lang=en)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"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.4.3"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment