Solving Sudoku In Python With DOcplex On DOcloud
JeanFrancoisPuget 2700028FGP Visits (14914)
Sudoku is a great example to introduce prescriptive analytics: it is well known, and it is not trivial to solve manually. I will use docplex Python api to implement a web application that solves Sudoku problems. The code is available in a notebook on github and nbviewer. More information on docplex can be found here.
DOcplex can be installed via pip as any other Python package:
Once installed, we can use it to create arbitrary math programming models. These models can either be solved using our DOcloud service, or be solved with a local installation of CPLEX. DOcloud solving is accessible to registered users. A free 30 days trial is available to everyone. All you need is to register on this page. Note that if you are an academic, then you can also get a free CPLEX installation, see instructions. You can then use it for solving DOcplex models locally.
In the following, we'll assume that you have registered for DOcloud. Once registered, you should get a url and a key. We'll use these to initiate a DOcloud connection. We print some information to check that our environment is correct, and we initialize an empty model. You will need to provide your own url and api key in order to run that code.
from docplex.mp.model import Model from docplex.mp.context import Context from docp
It prints information about my Python installation. I am using Anaconda on a Windows machine:
* system is: Windows 64bit * Python is present, version is 3.4.3 * docplex is present, version is (1, 0, 455) * CPLEX wrapper is not available
The warning tells us that we are not using a local CPLEX install.
Seems everything is fine. We can now start building our optimization model for Sudoku. Before modeling it, let me remind you of what the Sudoku puzzle is about in case you haven't read a newspaper in the last decade (adapted from wikipedia):
The objective is to fill a 9×9 grid with digits so that the digits in each column, each row, and each of the nine 3×3 sub-grids that compose the grid (also called ""blocks") are pairwise different. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a unique solution.
We will model this in two steps. First we create the generic part of the model, valid for every Sudoku problem, then we'll cope with the partially completed Sudoku grid. DOcplex only covers CPLEX optimizer today, hence we cannot use a constraint programming model here. We will use an integer programming model instead.
We start with a three dimensions matrix of binary variables. Dimensions of the matrix are: rows, columns, and digits. Rows and columns are the rows and columns of the Sudoku grid. There are 9 variables per cell of the grid, representing each possible digit. The binary variable x_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.
rows = range(0,9) columns = range(0,9) digits = range(0,9)
We represent the matrix with Python arrays. Variable in sudoku[i][j][k]is named x_i_j_k.
sudoku = [[
Variable x_i_j_k can be retrieved as sudoku[i][j][k].
Our first constraint is that there is exactly one digit per square. It means that for each pair i,j there is exactly one of the variables x_i_j_k set to 1. Equivalently, the sum of these variables is equal to 1.
for i in rows: for j in columns: mode
Our second constraint is that the digits on each line are different. One way to state it is to say that each digit k can appears exactly once per row i. Again, it is equivalent to saying that the sum of the corresponding variables is 1. Note how the use of Python comprehensions leads to a nice syntax.
for i in rows: for k in digits: mode
Our third constraint is that digits on each columns are different. It is similar to the previous one, with rows and columns swapped.
for j in columns: for k in digits: mode
Our last constraint is that digits in each 3x3 block are different. Expressing this one is a bit trickier. We need to get the list of variables in each 3x3 block, for a given digit.
for block_row in range(0,3): for block_column in range(0,3): block_list = [cel
Let's look at the code step by step. We iterate over all possible 3x3 blocks. For a given block, we first get the relevant rows with:
We then get the relevant three columns for each row with
block_list = [cel
This yields a list (rows) of lists (columns). We can use the overloaded sum operator to flatten these lists.
block = sum (block_list, )
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 1.
for k in digits: mode
Sudoku is a satisfaction problem, we only look for a feasible solution. Therefore there is no objective, and the generic part of our model is complete.
Let us now look at the input. Input will be a string of the entries in the partially completed sudoku grid. If a cell is empty, then we accept either 0 or a dot 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 is our default input corresponding to one of the hard Sudoku grid there is.
input1 = """ . . . |. . 6 |. . . . 5 9 |. . . |. . 8 2 . . |. . 8 |. . . ----
Let's turn this inputs into a 2D array of integers, where dots are replaced by 0. List comprehensions do their magic here.
def sudoku_string2int (input): chars = [0 if c == '.' else int(c) for c in input if c in '.0123456789'] grid = [chars[i*9:(i+1)*9] for i in range(0,9)] return grid
[[0, 0, 0, 0, 0, 6, 0, 0, 0], [0, 5, 9, 0, 0, 0, 0, 0, 8], [2, 0, 0, 0, 0, 8, 0, 0, 0], [0, 4, 5, 0, 0, 0, 0, 0, 0], [0, 0, 3, 0, 0, 0, 0, 0, 0], [0, 0, 6, 0, 0, 3, 0, 5, 4], [0, 0, 0, 3, 2, 5, 0, 0, 6], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
In order to solve that grid, we need to state that the non null entries define the corresponding binary variable: x_i_j_k is 1 if and only if digit k+1 is placed on cell i,j.
for i in rows: for j in columns: if grid[i][j] > 0: k = grid[i][j] - 1 mode
We can now solve the problem. We print information about the model before and after solving it.
Model: sudoku_CPLEX - number of variables: 729 - binary=729, integer=0, continuous=0 - number of constraints: 341 - LE=243, EQ=98, GE=0, RNG=0 - parameters : defaults * No objective to optimize - searching for a feasible solution * model solved with objective: 1
Solving the problem can take few seconds depending on your network latency. Solving with a local CPLEX installation is way faster. The difference becomes negligible for harder problems than Sudoku.
Once the problem is solved we can retrieve its solution as a 3D matrix by collecting all variables values.
raw_solution = [[
We have to map this back to a sudoku grid. Remember that we have 9 binary variable per cell of the grid, each corresponding to the presence or not of a digit. We can get the value of the digit actually present with a dot product. We must not forget to add 1 as we used indices starting at 0 when digits start at 1.
import numpy as npsolution = [
[[3, 8, 1, 7, 5, 6, 4, 2, 9], [4, 5, 9, 2, 3, 1, 7, 6, 8], [2, 6, 7, 9, 4, 8, 1, 3, 5], [7, 4, 5, 6, 9, 2, 3, 8, 1], [8, 2, 3, 5, 1, 4, 6, 9, 7], [9, 1, 6, 8, 7, 3, 2, 5, 4], [1, 7, 8, 3, 2, 5, 9, 4, 6], [5, 3, 4, 1, 6, 9, 8, 7, 2], [6, 9, 2, 4, 8, 7, 5, 1, 3]]
We are done!
We can display the result using matplotlib for instance as, described in Solv
import matplotlib.pyplot as plt %matplotlib inline
We can also wrap our code into a web application as explained in
This web app can be used to solve any Sudoku grid. This web app can be deployed on any IPython notebook server (eg Jupyter). For instance we have shown how to deploy a similar web app on IBM Bluemix cloud using a Docker container in Deploy IPython Notebooks With Docker On Bluemix In Minutes