A Sudoku Web App Using CPLEX Python Modeling API¶

Author: Jean-François Puget¶

We will be solving sudoku problems using docplex and the model from a post of mine.

We will use the Python client for the DOcloud service. It can be installed with pip.

Initialization¶

First, let's group all imports at the beginning

In :
from docplex.mp.model import Model
from docplex.mp.context import Context
from docplex.mp.environment import Environment

import numpy as np

import matplotlib.pyplot as plt
%matplotlib inline

import os
import json
import jinja2

from tornado.wsgi import WSGIContainer

Then let us initialize the Docloud connections. We print information to check the status. You will need to enter your credentials.

In :
docloud_context = Context.make_default_context(url=url, key=api_key)

env = Environment()
env.print_information()
* 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

Seems everything is fine.

Model creation¶

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.

We start with the creation of an empty model.

In :
model = Model('sudoku_CPLEX', context=docloud_context)
Warning: CPLEX DLL not found, will solve on DOcloud

The warning tells us that we are not using a local CPLEX install.

The variables¶

The logic of the model is rather simple. we create a three dimension 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.

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.

In :
rows    = range(0,9)
columns = range(0,9)
digits  = range(0,9)

We represent the matrix with Python arrays. Variable sudoku[i][j][k] is named x_i_j_k

In :
sudoku = [[[model.binary_var("x_%d_%d_%d" % (i,j,k)) for k in digits] for j in columns] for i in rows]

The constraints¶

Our first constraint is that there is exactly one digit per square

In :
for i in rows:
for j in columns:

Our second constraint is that the digits on each line are different.

In :
for i in rows:
for k in digits:
model.add_constraint(model.sum(sudoku[i][j][k] for j in columns)  == 1)

Our third constraint is that digits on each columns are different.

In :
for j in columns:
for k in digits:
model.add_constraint(model.sum(sudoku[i][j][k] for i in rows) == 1)

Our last constraint is that digits in 3x3 blocks 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.

Let's look at the first 3x3 block.

We can get the first 3 rows with sudoku[0:3] We then get the first three columns for each row with [c[0:3] for c in sudoku[0:3]]

This yields a list (rows) of lists (columns). We can use the overloaded sum operator to flatten the lists: sum([c[0:3] for c in sudoku[0:3]],[])

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.

block_list = [c[0:3] for c in sudoku[0:3]] block = sum(block_list,[]) for k in digits: model.add_constraint(sum(c[k] for c in block) == 1)

We repeat the above for each 3x3 block, iterating on block rows and bloc columns

In :
for block_row in range(0,3):
for block_column in range(0,3):
block_list = [cell[3*block_column:3*(block_column+1)] \
for cell in sudoku[3*block_row:3*(block_row+1)]]
block = sum (block_list, [])
for k in digits:
model.add_constraint(sum(c[k] for c in block) == 1)

The objective¶

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.

Problem input¶

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.

In :
input1 = """
. . . |. . 6 |. . .
. 5 9 |. . . |. . 8
2 . . |. . 8 |. . .
------+------+------
. 4 5 |. . . |. . .
. . 3 |. . . |. . .
. . 6 |. . 3 |. 5 4
------+------+------
. . . |3 2 5 |. . 6
. . . |. . . |. . .
. . . |. . . |. . .
"""

input2 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'

List comprehensions can be used to remove all non numerical characters, and replace dots by 0.

In :
def sudoku_trim(input):
chars = ['0' if c == '.' else c for c in input if c in '.0123456789']
return ''.join(chars)

We also need to move back and forth between the string input and a 2D matric of integers like the following.

[[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]]

List comprehensions do a nice job here too.

In :
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

def sudoku_int2string (solution):
flat_solution = sum(solution, [])
values = [str(cell) for cell in flat_solution]
return ''.join(values)

Let's try them

In :
sudoku_trim(input1)
Out:
'000006000059000008200008000045000000003000000006003054000325006000000000000000000'
In :
sudoku_trim(input2)
Out:
'000006000059000008200008000045000000003000000006003054000325006000000000000000000'
In :
sudoku_int2string(sudoku_string2int(input1))
Out:
'000006000059000008200008000045000000003000000006003054000325006000000000000000000'
In :
grid = sudoku_string2int(input1)
grid
Out:
[[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: sudoku[i][j][k] is 1 if and only if digit k+1 is placed on cell i,j.

In :
for i in rows:
for j in columns:
if grid[i][j] > 0:
k = grid[i][j] - 1

Solving the input problem¶

We can now solve the problem. We print information about the model before and after solving it

In :
model.print_information()
model.export_as_lp()
model.solve()
model.report()

Model: sudoku_CPLEX
- number of variables: 729
- binary=729, integer=0, continuous=0
- number of constraints: 341
-   LE=0, EQ=341, GE=0, RNG=0
- parameters: defaults
* No objective to optimize - searching for a feasible solution
* model solved with objective: 1

The problem is solved. We can now retrieve the solution as a 3D matrix.

In :
raw_solution = [[[sudoku[i][j][k].solution_value for k in digits] for j in columns] for i in rows]

Digit in the first cell:

In :
raw_solution
Out:
[0, 0, 0, 1, 0, 0, 0, 0, 0]

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

In :
solution = [[1+np.dot(raw_solution[i][j],digits) for j in columns] for i in rows]

solution
Out:
[[4, 8, 1, 9, 3, 6, 5, 2, 7],
[3, 5, 9, 2, 7, 1, 6, 4, 8],
[2, 6, 7, 4, 5, 8, 1, 9, 3],
[7, 4, 5, 6, 9, 2, 3, 8, 1],
[8, 1, 3, 5, 4, 7, 2, 6, 9],
[9, 2, 6, 8, 1, 3, 7, 5, 4],
[1, 9, 4, 3, 2, 5, 8, 7, 6],
[5, 3, 8, 7, 6, 9, 4, 1, 2],
[6, 7, 2, 1, 8, 4, 9, 3, 5]]

Seems our code is working! Let us pretty print the result using matplotlib.

In :
fig, ax = plt.subplots(figsize =(4,4))

for i in rows:
for j in columns:
ax.text(i+0.5,8.5-j, str(solution[j][i]), va='center', ha='center')

ax.set_xlim(0, 9)
ax.set_ylim(0, 9)
ax.set_xticks(rows)
ax.set_yticks(columns)
ax.grid()
plt.show() Wrapping up¶

Let's wrap everything into an easy to reuse function

In :
def sudoku_solve(docloud_context, input):
model = Model('sudoku_CPLEX', context=docloud_context)

rows    = range(0,9)
columns = range(0,9)
digits  = range(0,9)

sudoku = [[[model.binary_var("x_%d_%d_%d" % (i,j,k)) for k in digits] for j in columns] for i in rows]

for i in rows:
for j in columns:

for i in rows:
for k in digits:
model.add_constraint(model.sum(sudoku[i][j][k] for j in columns)  == 1)

for j in columns:
for k in digits:
model.add_constraint(model.sum(sudoku[i][j][k] for i in rows) == 1)

for block_row in range(0,3):
for block_column in range(0,3):
block_list = [cell[3*block_column:3*(block_column+1)] for cell in sudoku[3*block_row:3*(block_row+1)]]
block = sum (block_list, [])
for k in digits:
model.add_constraint(sum(c[k] for c in block) == 1)

grid = sudoku_string2int(input)

for i in rows:
for j in columns:
if grid[i][j] > 0:
k = grid[i][j] - 1

model.export_as_lp()
if not model.solve():
#Problem has no solution
return []

raw_solution = [[[sudoku[i][j][k].solution_value for k in digits] for j in columns] for i in rows]
solution = [[1+np.dot(raw_solution[i][j], digits) for j in columns] for i in rows]
return solution

Let us test our function.

In :
input = """
. . . |. . 6 |. . .
. 5 9 |. . . |. . 8
2 . . |. . 8 |. . .
------+------+------
. 4 5 |. . . |. . .
. . 3 |. . . |. . .
. . 6 |. . 3 |. 5 4
------+------+------
. . . |3 2 5 |. . 6
. . . |. . . |. . .
. . . |. . . |. . .
"""

solution = sudoku_solve(docloud_context, input)

solution
Warning: CPLEX DLL not found, will solve on DOcloud
* No objective to optimize - searching for a feasible solution
Out:
[[3, 8, 7, 4, 5, 6, 9, 2, 1],
[4, 5, 9, 2, 7, 1, 6, 3, 8],
[2, 6, 1, 9, 3, 8, 4, 7, 5],
[9, 4, 5, 8, 1, 2, 7, 6, 3],
[7, 1, 3, 5, 6, 4, 2, 8, 9],
[8, 2, 6, 7, 9, 3, 1, 5, 4],
[1, 7, 4, 3, 2, 5, 8, 9, 6],
[5, 9, 8, 6, 4, 7, 3, 1, 2],
[6, 3, 2, 1, 8, 9, 5, 4, 7]]

A web app¶

We now turn this into a web app reusing the code from A Sudoku Web App Based On DOcloud And Python

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.

In :
page = jinja2.Template(r"""
<html>
<title>A Sudoku Solver</title>

<script type=text/javascript>
$SCRIPT_ROOT = "{{url}}"; </script> <script language="javascript"><!-- function set_grid(str) { // set the grid given a sudoku string if (str != null && str.length >= 81) { for (var i = 0; i < 81; ++i) document.getElementById('C'+i).value = '' for (var i = 0; i < 81; ++i) if (str.substr(i, 1) >= 1 && str.substr(i, 1) <= 9) document.getElementById('C'+i).value = str.substr(i, 1) } } function solve_grid() { if ($('#solve').val() == 'Solving') {
$('#grid_info').html('Wait for result please'); return; }; var n_hints = 0; s = ''; for (var i = 0; i < 81; ++i) { // get the sudoku string var y = document.getElementById('C'+i).value if (y >= 1 && y <= 9) { s += ''+y; ++n_hints; } else s += '.' } if (n_hints >= 15) { // enough hints$('#solve').val('Solving')
$.getJSON($SCRIPT_ROOT + '/solve',
{grid: s},
function(data) {
$('#solve').val('Solve') var x = data.result; if (x.length == 0) {$('#grid_info').html('No solution')
} else if (x.length == 81) {
set_grid(x);
$('#grid_info').html('First solution') } }); } else$('#grid_info').html('No less than 15 hints are required')
}

function draw_grid() { // generate the grid and fill it (called "onLoad")
// generate the grid
var s = '<table class="table">\n'
for (var i = 0; i < 9; ++i) {
s += '<tr>'
for (var j = 0; j < 9; ++j) {
var c = 'cell'
if ((i+1)%3 == 0 && j%3 == 0) c = 'cell3'
else if ((i+1)%3 == 0) c = 'cell1'
else if (j%3 == 0) c = 'cell2'
s += '<td class="' + c + '"><input class="input" type="text" size="1" maxlength="1" id="C' + (i*9+j) + '"></td>';
}
s += '</tr>\n'
}
s += '</table>'
$('#grid').html(s) // set the grid with input input = '{{ input }}' set_grid(input)$('#grid_info').html('Fill the grid with at least 15 hints')

}

function clear_grid() {
if ($('#solve').val() == 'Solving') {$('#grid_info').html('Wait for result please');
return;
};
\$('#grid_info').html('Fill the grid with at least 15 hints')
for (var i = 0; i < 81; ++i)
document.getElementById('C'+i).value = ''
}
--></script>
<style type="text/css"><!--
table { margin: 0 auto; }
body, td, p, span { font: 12px "Lucida Grande", "Lucida Sans Unicode", Arial, sans-serif; text-align: center;}
.input { border: 0px; width: 2em; height: 2em; text-align:center; }
.cell {  width: 1em; height: 1em; border-bottom:1px solid; border-left:1px solid; padding: 0.3em}
.cell1 { width: 1em; height: 1em; border-bottom:2px solid; border-left:1px solid; padding: 0.3em}
.cell2 { width: 1em; height: 1em; border-bottom:1px solid; border-left:2px solid; padding: 0.3em}
.cell3 { width: 1em; height: 1em; border-bottom:2px solid; border-left:2px solid; padding: 0.3em}
.table { border-top:2px solid; border-right:2px solid; border-collapse:collapse }
--></style>
<h1>A Sudoku Solver</h1>
<span id="grid"></span>
<p><span id="grid_info" style="color: gray;">Fill the grid with at least 15 hints</span></p>
<input type="button" id="solve" value="Solve" onClick="solve_grid();">&nbsp;<input type="button" id="clear" value="Clear" onClick="clear_grid();">

</body>
</html>

""")

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.

In :
PORT = 9000

host = os.getenv('HOST_PUBLIC_IP')

if host == None: host = 'localhost'

url = 'http://%s:%d' % (host , PORT)

Let's see what we get.

In :
print(url)
http://localhost:9000

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.

We can now create the web service with Flask.

In :

def index():
'''Renders the template with the service url and an initial grid on HTTP GET.'''
return page.render(url=url, input=sudoku_trim(input))

def solve():
'''Solves the input Sudoku and returns it on HTTP GET.'''
input = request.args.get('grid', '')
solution = sudoku_solve(docloud_context, input)
result = sudoku_int2string(solution)
return jsonify(result=result)
In :

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 (KernelInterrupt).

We can run the Flask application in a Tornado WSGIContainer if we want a non blocking web server.

In :