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.
First, let's group all imports at the beginning
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 flask import Flask, request, jsonify
import tornado.httpserver
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.
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.
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.
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 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.
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
sudoku = [[[model.binary_var("x_%d_%d_%d" % (i,j,k)) for k in digits] for j in columns] for i in rows]
Our first constraint is that there is exactly one digit per square
for i in rows:
for j in columns:
model.add_constraint(model.sum(sudoku[i][j]) == 1)
Our second constraint is that the digits on each line are different.
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.
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
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
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)
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.
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.
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.
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.
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
sudoku_trim(input1)
'000006000059000008200008000045000000003000000006003054000325006000000000000000000'
sudoku_trim(input2)
'000006000059000008200008000045000000003000000006003054000325006000000000000000000'
sudoku_int2string(sudoku_string2int(input1))
'000006000059000008200008000045000000003000000006003054000325006000000000000000000'
grid = sudoku_string2int(input1)
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:
sudoku[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
model.add_constraint(sudoku[i][j][k] == 1)
We can now solve the problem. We print information about the model before and after solving it
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.
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:
raw_solution[0][0]
[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
solution = [[1+np.dot(raw_solution[i][j],digits) for j in columns] for i in rows]
solution
[[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.
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()
Let's wrap everything into an easy to reuse function
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:
model.add_constraint(model.sum(sudoku[i][j]) == 1)
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.add_constraint(sudoku[i][j][k] == 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.
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
[[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]]
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.
page = jinja2.Template(r"""
<html>
<head>
<title>A Sudoku Solver</title>
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<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>
</head>
<body onLoad='draw_grid();'>
<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();"> <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.
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.
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.
flask_app = Flask('sudoku_demo')
@flask_app.route('/')
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))
@flask_app.route('/solve/')
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)
#flask_app.run(host='0.0.0.0', port=PORT)
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 → Interrupt).
We can run the Flask application in a Tornado WSGIContainer if we want a non blocking web server.
server = tornado.httpserver.HTTPServer(WSGIContainer(flask_app))
server.listen(PORT, '0.0.0.0')
Warning: CPLEX DLL not found, will solve on DOcloud * No objective to optimize - searching for a feasible solution
This concludes our web ap development. To run the web app, simply click on the url above.
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