Interfacing with Gurobi or PuLP: A Sudoku Solver

You can see this app running online at: Sudoku Solver App Online

What this app does:

  • Solves the well known sudoku puzzle

This app aims to demonstrate:

Gurobi worked example

  • The code that solves the optimisation problem within this app is taken from two online examples
  • One from Gurobi Sudoku and is used with permission.
  • One from PuLP Sudoku and is used with permission.

Setup Instructions

Before you can run this app, you will need to install Gurobi. Note the trail licenses limit of 500 variables means that unless you have an unlimited license you will not be able to run the Gurobi code. By default PuLP is used to solve this model. Details can be found on the Gurobi website

Next, use the app name 'tropofy_gurobi_sudoku' to quickstart as in Running and Debugging Tropofy Apps

Full Source

"""
Authors: www.tropofy.com and www.gurobi.com

Copyright 2015 Tropofy Pty Ltd, all rights reserved.
Copyright 2013, Gurobi Optimization, Inc.

This source file (where not indicated as under the copyright of Gurobi)
is part of Tropofy and governed by the Tropofy terms of service
available at: http://www.tropofy.com/terms_of_service.html

Parts of the formulation provided by Gurobi have been modified.
The original example is in the Gurobi installation in the example file dietmodel.py

Used with permission.

This source file is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the license files for details.
"""

import os
import pkg_resources
import StringIO
from pulp import *

# Note the trial license of Gurobi is limited to 500 variables
# The number of variables for the sudoku formulation is pow(9, 3) = 729
# This code will only work if you have an unrestricted Gurobi license
#from gurobipy import GRB, Model, quicksum, tuplelist

from sqlalchemy.types import Integer
from sqlalchemy.schema import Column
from sqlalchemy.orm import relationship, backref

from tropofy.app import AppWithDataSets, Step, StepGroup
from tropofy.widgets import ExecuteFunction, SimpleGrid
from tropofy.database.tropofy_orm import DataSetMixin


class SudokuRow(DataSetMixin):
    col1 = Column(Integer, nullable=True)
    col2 = Column(Integer, nullable=True)
    col3 = Column(Integer, nullable=True)
    col4 = Column(Integer, nullable=True)
    col5 = Column(Integer, nullable=True)
    col6 = Column(Integer, nullable=True)
    col7 = Column(Integer, nullable=True)
    col8 = Column(Integer, nullable=True)
    col9 = Column(Integer, nullable=True)

    def __init__(self, col1, col2, col3, col4, col5, col6, col7, col8, col9):
        self.col1 = col1
        self.col2 = col2
        self.col3 = col3
        self.col4 = col4
        self.col5 = col5
        self.col6 = col6
        self.col7 = col7
        self.col8 = col8
        self.col9 = col9


class SudokuAnswerRow(DataSetMixin):
    col1 = Column(Integer, nullable=True)
    col2 = Column(Integer, nullable=True)
    col3 = Column(Integer, nullable=True)
    col4 = Column(Integer, nullable=True)
    col5 = Column(Integer, nullable=True)
    col6 = Column(Integer, nullable=True)
    col7 = Column(Integer, nullable=True)
    col8 = Column(Integer, nullable=True)
    col9 = Column(Integer, nullable=True)

    def __init__(self, col1, col2, col3, col4, col5, col6, col7, col8, col9):
        self.col1 = col1
        self.col2 = col2
        self.col3 = col3
        self.col4 = col4
        self.col5 = col5
        self.col6 = col6
        self.col7 = col7
        self.col8 = col8
        self.col9 = col9


class ExecuteGurobiSolver(ExecuteFunction):

    def get_button_text(self, app_session):
        return "Solve Sudoku Puzzle"

    def execute_function(self, app_session):
        # Note the trial license of Gurobi is limited to 500 variables
        # The number of variables for the sudoku formulation is pow(9, 3) = 729
        # This code will only work if you have an unrestricted Gurobi license
        #solve_sudoku_puzzle_using_gurobi(data_set):
        solve_sudoku_puzzle_using_pulp(app_session)


class GurobiSudokuApp(AppWithDataSets):

    def get_name(self):
        return 'Sudoku Solver'

    def get_examples(self):
        return {"Demo data set from Gurobi": load_example_data}

    def get_static_content_path(self, app_session):
        return pkg_resources.resource_filename('te_gurobi_sudoku', 'static')

    def get_gui(self):
        step_group1 = StepGroup(name='Enter your sudoku puzzle')
        step_group1.add_step(Step(name='Enter your sudoku puzzle', widgets=[SimpleGrid(SudokuRow)]))

        step_group2 = StepGroup(name='Solve')
        step_group2.add_step(Step(name='Solve your sudoku puzzle', widgets=[ExecuteGurobiSolver()]))

        step_group3 = StepGroup(name='View the solution')
        step_group3.add_step(Step(name='View the solution', widgets=[SimpleGrid(SudokuAnswerRow)]))

        return [step_group1, step_group2, step_group3]

    def get_icon_url(self):
        return "/{}/static/{}/sudoku.png".format(
            self.url_name,
            self.get_app_version(),
        )


def load_example_data(app_session):
    app_session.data_set.add(SudokuRow(None, 2, 8, 4, 7, 6, 3, None, None))
    app_session.data_set.add(SudokuRow(None, None, None, 8, 3, 9, None, 2, None))
    app_session.data_set.add(SudokuRow(7, None, None, 5, 1, 2, None, 8, None))
    app_session.data_set.add(SudokuRow(None, None, 1, 7, 9, None, None, 4, None))
    app_session.data_set.add(SudokuRow(3, None, None, None, None, None, None, None, None))
    app_session.data_set.add(SudokuRow(None, None, 9, None, None, None, 1, None, None))
    app_session.data_set.add(SudokuRow(None, 5, None, None, 8, None, None, None, None))
    app_session.data_set.add(SudokuRow(None, None, 6, 9, 2, None, None, None, 5))
    app_session.data_set.add(SudokuRow(None, None, 2, 6, 4, 5, None, None, 8))


def solve_sudoku_puzzle_using_pulp(app_session):
    """
    The Sudoku Problem Formulation for the PuLP Modeller
    Authors: Antony Phillips, Dr Stuart Mitcehll, PuLP
    See http://pythonhosted.org/PuLP/CaseStudies/a_sudoku_problem.html
    Used with permission
    """
    data_set = app_session.data_set

    # A list of strings from "1" to "9" is created
    Sequence = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]

    # The Vals, Rows and Cols sequences all follow this form
    Vals = Sequence
    Rows = Sequence
    Cols = Sequence

    # The boxes list is created, with the row and column index of each square in each box
    Boxes = []
    for i in range(3):
        for j in range(3):
            Boxes += [[(Rows[3 * i + k], Cols[3 * j + l]) for k in range(3) for l in range(3)]]

    # The prob variable is created to contain the problem data
    prob = LpProblem("Sudoku Problem", LpMinimize)

    # The problem variables are created
    choices = LpVariable.dicts("Choice", (Vals, Rows, Cols), 0, 1, LpInteger)

    # The arbitrary objective function is added
    prob += 0, "Arbitrary Objective Function"

    # A constraint ensuring that only one value can be in each square is created
    for r in Rows:
        for c in Cols:
            prob += lpSum([choices[v][r][c] for v in Vals]) == 1, ""

    # The row, column and box constraints are added for each value
    for v in Vals:
        for r in Rows:
            prob += lpSum([choices[v][r][c] for c in Cols]) == 1, ""
        for c in Cols:
            prob += lpSum([choices[v][r][c] for r in Rows]) == 1, ""
        for b in Boxes:
            prob += lpSum([choices[v][r][c] for (r, c) in b]) == 1, ""

    # The starting numbers are entered as constraints
    starting_grid = []
    for r in data_set.query(SudokuRow).all():
        starting_grid.append([r.col1, r.col2, r.col3, r.col4, r.col5, r.col6, r.col7, r.col8, r.col9])

    for i in range(9):
        for j in range(9):
            if starting_grid[i][j]:
                prob += choices[str(starting_grid[i][j])][str(i + 1)][str(j + 1)] == 1, ""

    prob.solve()

    # The status of the solution is printed to the screen
    app_session.task_manager.send_progress_message("Status: %s" % LpStatus[prob.status])

    # The solution is written to a string
    sudokuout = StringIO.StringIO()
    for r in Rows:
        if r == "1" or r == "4" or r == "7":
            sudokuout.write("+-------+-------+-------+<br>")
        row_sol = []
        for c in Cols:
            for v in Vals:
                if value(choices[v][r][c]) == 1:
                    if c == "1" or c == "4" or c == "7":
                        sudokuout.write("| ")
                    sudokuout.write(v + " ")
                    row_sol.append(v)
                    if c == "9":
                        sudokuout.write("|<br>")
        data_set.add(SudokuAnswerRow(row_sol[0], row_sol[1], row_sol[2], row_sol[3], row_sol[4], row_sol[5], row_sol[6], row_sol[7], row_sol[8]))
    sudokuout.write("+-------+-------+-------+")

    app_session.task_manager.send_progress_message(sudokuout.getvalue())

# Note the trial license of Gurobi is limited to 500 variables
# The number of variables for the sudoku formulation is pow(9, 3) = 729
# This code will only work if you have an unrestricted Gurobi license
'''
def solve_sudoku_puzzle_using_gurobi(data_set):
    # Copyright 2013, Gurobi Optimization, Inc.

    # Sudoku example.

    # The Sudoku board is a 9x9 grid, which is further divided into a 3x3 grid
    # of 3x3 grids.  Each cell in the grid must take a value from 0 to 9.
    # No two grid cells in the same row, column, or 3x3 subgrid may take the
    # same value.
    #
    # In the MIP formulation, binary variables x[i,j,v] indicate whether
    # cell <i,j> takes value 'v'.  The constraints are as follows:
    #   1. Each cell must take exactly one value (sum_v x[i,j,v] = 1)
    #   2. Each value is used exactly once per row (sum_i x[i,j,v] = 1)
    #   3. Each value is used exactly once per column (sum_j x[i,j,v] = 1)
    #   4. Each value is used exactly once per 3x3 subgrid (sum_grid x[i,j,v] = 1)

    n = 9
    s = 3

    vars_ = {}

    grid = []
    for r in data_set.query(SudokuRow).all():
        grid.append([r.col1, r.col2, r.col3, r.col4, r.col5, r.col6, r.col7, r.col8, r.col9])

    # Create our 3-D array of model variables

    model = Model('sudoku')

    for i in range(n):
        for j in range(n):
            for v in range(n):
                vars_[i, j, v] = model.addVar(vtype=GRB.BINARY, name='G_' + str(i) + '_' + str(j) + '_' + str(v))

    # Update model to integrate new variables

    model.update()

    # Fix variables associated with cells whose values are pre-specified

    for i in range(n):
        for j in range(n):
            if grid[i][j]:
                v = int(grid[i][j]) - 1
                model.addConstr(vars_[i, j, v] == 1, 'Fix_' + str(i) + '_' + str(j))

    # Each cell must take one value

    for i in range(n):
        for j in range(n):
            model.addConstr(quicksum([vars_[i, j, v] for v in range(n)]) == 1, 'V_' + str(i) + '_' + str(j))

    # Each value appears once per row

    for i in range(n):
        for v in range(n):
            model.addConstr(quicksum([vars_[i, j, v] for j in range(n)]) == 1, 'R_' + str(i) + '_' + str(v))

    # Each value appears once per column

    for j in range(n):
        for v in range(n):
            model.addConstr(quicksum([vars_[i, j, v] for i in range(n)]) == 1, 'C_' + str(j) + '_' + str(v))

    # Each value appears once per subgrid

    for v in range(n):
        for i0 in range(s):
            for j0 in range(s):
                subgrid = [vars_[i, j, v] for i in range(i0 * s, (i0 + 1) * s) for j in range(j0 * s, (j0 + 1) * s)]
                model.addConstr(quicksum(subgrid) == 1, 'Sub_' + str(i0) + '_' + str(j0) + '_' + str(v))

    model.optimize()

    # Retrieve optimization result

    solution = model.getAttr('X', vars_)

    for i in range(n):
        sol = ''
        for j in range(n):
            for v in range(n):
                if solution[i, j, v] > 0.5:
                    sol += str(v + 1)
        data_set.send_progress_message(sol)
'''