{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "## Disclaimer\n", "This notebook is only working under the versions:\n", "\n", "- JuMP 0.19\n", "\n", "- MathOptInterface 0.8.4\n", "\n", "- GLPK 0.9.1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Description**: Shows how to solve [Sudoku](http://en.wikipedia.org/wiki/Sudoku) puzzles using integer programming and JuMP.\n", "\n", "**Author**: Iain Dunning\n", "\n", "**License**: \"Creative
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Solving Sudoku with JuMP\n", "\n", "\n", "

A partially solved Sudoku puzzle

\n", "\n", "Sudoku is a popular number puzzle. The goal is to place the digits 1,...,9 on a nine-by-nine grid, with some of the digits already filled in. Your solution must satisfy the following rules:\n", "\n", "* The numbers 1 to 9 must appear in each 3x3 square\n", "* The numbers 1 to 9 must appear in each row\n", "* The numbers 1 to 9 must appear in each column\n", "\n", "This isn't an optimization problem, its actually a *feasibility* problem: we wish to find a feasible solution that satsifies these rules. You can think of it as an optimization problem with an objective of 0.\n", "\n", "We can model this problem using 0-1 integer programming: a problem where all the decision variables are binary. We'll use JuMP to create the model, and then we can solve it with any integer programming solver." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "MathOptInterface.Utilities" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Load JuMP\n", "using JuMP\n", "using MathOptInterface\n", "# Load solver package\n", "using GLPK\n", "# shortcuts\n", "const MOI = MathOptInterface\n", "const MOIU = MathOptInterface.Utilities" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will define a binary variable (a variable that is either 0 or 1) for each possible number in each possible cell. The meaning of each variable is as follows:\n", "\n", " x[i,j,k] = 1 if and only if cell (i,j) has number k\n", "\n", "where `i` is the row and `j` is the column." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9×9×9 Array{VariableRef,3}:\n", "[:, :, 1] =\n", " x[1,1,1] x[1,2,1] x[1,3,1] x[1,4,1] … x[1,7,1] x[1,8,1] x[1,9,1]\n", " x[2,1,1] x[2,2,1] x[2,3,1] x[2,4,1] x[2,7,1] x[2,8,1] x[2,9,1]\n", " x[3,1,1] x[3,2,1] x[3,3,1] x[3,4,1] x[3,7,1] x[3,8,1] x[3,9,1]\n", " x[4,1,1] x[4,2,1] x[4,3,1] x[4,4,1] x[4,7,1] x[4,8,1] x[4,9,1]\n", " x[5,1,1] x[5,2,1] x[5,3,1] x[5,4,1] x[5,7,1] x[5,8,1] x[5,9,1]\n", " x[6,1,1] x[6,2,1] x[6,3,1] x[6,4,1] … x[6,7,1] x[6,8,1] x[6,9,1]\n", " x[7,1,1] x[7,2,1] x[7,3,1] x[7,4,1] x[7,7,1] x[7,8,1] x[7,9,1]\n", " x[8,1,1] x[8,2,1] x[8,3,1] x[8,4,1] x[8,7,1] x[8,8,1] x[8,9,1]\n", " x[9,1,1] x[9,2,1] x[9,3,1] x[9,4,1] x[9,7,1] x[9,8,1] x[9,9,1]\n", "\n", "[:, :, 2] =\n", " x[1,1,2] x[1,2,2] x[1,3,2] x[1,4,2] … x[1,7,2] x[1,8,2] x[1,9,2]\n", " x[2,1,2] x[2,2,2] x[2,3,2] x[2,4,2] x[2,7,2] x[2,8,2] x[2,9,2]\n", " x[3,1,2] x[3,2,2] x[3,3,2] x[3,4,2] x[3,7,2] x[3,8,2] x[3,9,2]\n", " x[4,1,2] x[4,2,2] x[4,3,2] x[4,4,2] x[4,7,2] x[4,8,2] x[4,9,2]\n", " x[5,1,2] x[5,2,2] x[5,3,2] x[5,4,2] x[5,7,2] x[5,8,2] x[5,9,2]\n", " x[6,1,2] x[6,2,2] x[6,3,2] x[6,4,2] … x[6,7,2] x[6,8,2] x[6,9,2]\n", " x[7,1,2] x[7,2,2] x[7,3,2] x[7,4,2] x[7,7,2] x[7,8,2] x[7,9,2]\n", " x[8,1,2] x[8,2,2] x[8,3,2] x[8,4,2] x[8,7,2] x[8,8,2] x[8,9,2]\n", " x[9,1,2] x[9,2,2] x[9,3,2] x[9,4,2] x[9,7,2] x[9,8,2] x[9,9,2]\n", "\n", "[:, :, 3] =\n", " x[1,1,3] x[1,2,3] x[1,3,3] x[1,4,3] … x[1,7,3] x[1,8,3] x[1,9,3]\n", " x[2,1,3] x[2,2,3] x[2,3,3] x[2,4,3] x[2,7,3] x[2,8,3] x[2,9,3]\n", " x[3,1,3] x[3,2,3] x[3,3,3] x[3,4,3] x[3,7,3] x[3,8,3] x[3,9,3]\n", " x[4,1,3] x[4,2,3] x[4,3,3] x[4,4,3] x[4,7,3] x[4,8,3] x[4,9,3]\n", " x[5,1,3] x[5,2,3] x[5,3,3] x[5,4,3] x[5,7,3] x[5,8,3] x[5,9,3]\n", " x[6,1,3] x[6,2,3] x[6,3,3] x[6,4,3] … x[6,7,3] x[6,8,3] x[6,9,3]\n", " x[7,1,3] x[7,2,3] x[7,3,3] x[7,4,3] x[7,7,3] x[7,8,3] x[7,9,3]\n", " x[8,1,3] x[8,2,3] x[8,3,3] x[8,4,3] x[8,7,3] x[8,8,3] x[8,9,3]\n", " x[9,1,3] x[9,2,3] x[9,3,3] x[9,4,3] x[9,7,3] x[9,8,3] x[9,9,3]\n", "\n", "[:, :, 4] =\n", " x[1,1,4] x[1,2,4] x[1,3,4] x[1,4,4] … x[1,7,4] x[1,8,4] x[1,9,4]\n", " x[2,1,4] x[2,2,4] x[2,3,4] x[2,4,4] x[2,7,4] x[2,8,4] x[2,9,4]\n", " x[3,1,4] x[3,2,4] x[3,3,4] x[3,4,4] x[3,7,4] x[3,8,4] x[3,9,4]\n", " x[4,1,4] x[4,2,4] x[4,3,4] x[4,4,4] x[4,7,4] x[4,8,4] x[4,9,4]\n", " x[5,1,4] x[5,2,4] x[5,3,4] x[5,4,4] x[5,7,4] x[5,8,4] x[5,9,4]\n", " x[6,1,4] x[6,2,4] x[6,3,4] x[6,4,4] … x[6,7,4] x[6,8,4] x[6,9,4]\n", " x[7,1,4] x[7,2,4] x[7,3,4] x[7,4,4] x[7,7,4] x[7,8,4] x[7,9,4]\n", " x[8,1,4] x[8,2,4] x[8,3,4] x[8,4,4] x[8,7,4] x[8,8,4] x[8,9,4]\n", " x[9,1,4] x[9,2,4] x[9,3,4] x[9,4,4] x[9,7,4] x[9,8,4] x[9,9,4]\n", "\n", "[:, :, 5] =\n", " x[1,1,5] x[1,2,5] x[1,3,5] x[1,4,5] … x[1,7,5] x[1,8,5] x[1,9,5]\n", " x[2,1,5] x[2,2,5] x[2,3,5] x[2,4,5] x[2,7,5] x[2,8,5] x[2,9,5]\n", " x[3,1,5] x[3,2,5] x[3,3,5] x[3,4,5] x[3,7,5] x[3,8,5] x[3,9,5]\n", " x[4,1,5] x[4,2,5] x[4,3,5] x[4,4,5] x[4,7,5] x[4,8,5] x[4,9,5]\n", " x[5,1,5] x[5,2,5] x[5,3,5] x[5,4,5] x[5,7,5] x[5,8,5] x[5,9,5]\n", " x[6,1,5] x[6,2,5] x[6,3,5] x[6,4,5] … x[6,7,5] x[6,8,5] x[6,9,5]\n", " x[7,1,5] x[7,2,5] x[7,3,5] x[7,4,5] x[7,7,5] x[7,8,5] x[7,9,5]\n", " x[8,1,5] x[8,2,5] x[8,3,5] x[8,4,5] x[8,7,5] x[8,8,5] x[8,9,5]\n", " x[9,1,5] x[9,2,5] x[9,3,5] x[9,4,5] x[9,7,5] x[9,8,5] x[9,9,5]\n", "\n", "[:, :, 6] =\n", " x[1,1,6] x[1,2,6] x[1,3,6] x[1,4,6] … x[1,7,6] x[1,8,6] x[1,9,6]\n", " x[2,1,6] x[2,2,6] x[2,3,6] x[2,4,6] x[2,7,6] x[2,8,6] x[2,9,6]\n", " x[3,1,6] x[3,2,6] x[3,3,6] x[3,4,6] x[3,7,6] x[3,8,6] x[3,9,6]\n", " x[4,1,6] x[4,2,6] x[4,3,6] x[4,4,6] x[4,7,6] x[4,8,6] x[4,9,6]\n", " x[5,1,6] x[5,2,6] x[5,3,6] x[5,4,6] x[5,7,6] x[5,8,6] x[5,9,6]\n", " x[6,1,6] x[6,2,6] x[6,3,6] x[6,4,6] … x[6,7,6] x[6,8,6] x[6,9,6]\n", " x[7,1,6] x[7,2,6] x[7,3,6] x[7,4,6] x[7,7,6] x[7,8,6] x[7,9,6]\n", " x[8,1,6] x[8,2,6] x[8,3,6] x[8,4,6] x[8,7,6] x[8,8,6] x[8,9,6]\n", " x[9,1,6] x[9,2,6] x[9,3,6] x[9,4,6] x[9,7,6] x[9,8,6] x[9,9,6]\n", "\n", "[:, :, 7] =\n", " x[1,1,7] x[1,2,7] x[1,3,7] x[1,4,7] … x[1,7,7] x[1,8,7] x[1,9,7]\n", " x[2,1,7] x[2,2,7] x[2,3,7] x[2,4,7] x[2,7,7] x[2,8,7] x[2,9,7]\n", " x[3,1,7] x[3,2,7] x[3,3,7] x[3,4,7] x[3,7,7] x[3,8,7] x[3,9,7]\n", " x[4,1,7] x[4,2,7] x[4,3,7] x[4,4,7] x[4,7,7] x[4,8,7] x[4,9,7]\n", " x[5,1,7] x[5,2,7] x[5,3,7] x[5,4,7] x[5,7,7] x[5,8,7] x[5,9,7]\n", " x[6,1,7] x[6,2,7] x[6,3,7] x[6,4,7] … x[6,7,7] x[6,8,7] x[6,9,7]\n", " x[7,1,7] x[7,2,7] x[7,3,7] x[7,4,7] x[7,7,7] x[7,8,7] x[7,9,7]\n", " x[8,1,7] x[8,2,7] x[8,3,7] x[8,4,7] x[8,7,7] x[8,8,7] x[8,9,7]\n", " x[9,1,7] x[9,2,7] x[9,3,7] x[9,4,7] x[9,7,7] x[9,8,7] x[9,9,7]\n", "\n", "[:, :, 8] =\n", " x[1,1,8] x[1,2,8] x[1,3,8] x[1,4,8] … x[1,7,8] x[1,8,8] x[1,9,8]\n", " x[2,1,8] x[2,2,8] x[2,3,8] x[2,4,8] x[2,7,8] x[2,8,8] x[2,9,8]\n", " x[3,1,8] x[3,2,8] x[3,3,8] x[3,4,8] x[3,7,8] x[3,8,8] x[3,9,8]\n", " x[4,1,8] x[4,2,8] x[4,3,8] x[4,4,8] x[4,7,8] x[4,8,8] x[4,9,8]\n", " x[5,1,8] x[5,2,8] x[5,3,8] x[5,4,8] x[5,7,8] x[5,8,8] x[5,9,8]\n", " x[6,1,8] x[6,2,8] x[6,3,8] x[6,4,8] … x[6,7,8] x[6,8,8] x[6,9,8]\n", " x[7,1,8] x[7,2,8] x[7,3,8] x[7,4,8] x[7,7,8] x[7,8,8] x[7,9,8]\n", " x[8,1,8] x[8,2,8] x[8,3,8] x[8,4,8] x[8,7,8] x[8,8,8] x[8,9,8]\n", " x[9,1,8] x[9,2,8] x[9,3,8] x[9,4,8] x[9,7,8] x[9,8,8] x[9,9,8]\n", "\n", "[:, :, 9] =\n", " x[1,1,9] x[1,2,9] x[1,3,9] x[1,4,9] … x[1,7,9] x[1,8,9] x[1,9,9]\n", " x[2,1,9] x[2,2,9] x[2,3,9] x[2,4,9] x[2,7,9] x[2,8,9] x[2,9,9]\n", " x[3,1,9] x[3,2,9] x[3,3,9] x[3,4,9] x[3,7,9] x[3,8,9] x[3,9,9]\n", " x[4,1,9] x[4,2,9] x[4,3,9] x[4,4,9] x[4,7,9] x[4,8,9] x[4,9,9]\n", " x[5,1,9] x[5,2,9] x[5,3,9] x[5,4,9] x[5,7,9] x[5,8,9] x[5,9,9]\n", " x[6,1,9] x[6,2,9] x[6,3,9] x[6,4,9] … x[6,7,9] x[6,8,9] x[6,9,9]\n", " x[7,1,9] x[7,2,9] x[7,3,9] x[7,4,9] x[7,7,9] x[7,8,9] x[7,9,9]\n", " x[8,1,9] x[8,2,9] x[8,3,9] x[8,4,9] x[8,7,9] x[8,8,9] x[8,9,9]\n", " x[9,1,9] x[9,2,9] x[9,3,9] x[9,4,9] x[9,7,9] x[9,8,9] x[9,9,9]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create a model\n", "sudoku = Model(with_optimizer(GLPK.Optimizer))\n", "\n", "# Create our variables\n", "@variable(sudoku, x[i=1:9, j=1:9, k=1:9], Bin)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can begin to add our constraints. We'll actually start with something obvious to us as humans, but what we need to enforce: that there can be only one number per cell." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "for i = 1:9, j = 1:9 # Each row and each column\n", " # Sum across all the possible digits\n", " # One and only one of the digits can be in this cell, \n", " # so the sum must be equal to one\n", " @constraint(sudoku, sum(x[i,j,k] for k in 1:9) == 1)\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next we'll add the constraints for the rows and the columns. These constraints are all very similar, so much so that we can actually add them at the same time." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "for ind = 1:9 # Each row, OR each column\n", " for k = 1:9 # Each digit\n", " # Sum across columns (j) - row constraint\n", " @constraint(sudoku, sum(x[ind,j,k] for j in 1:9) == 1)\n", " # Sum across rows (i) - column constraint\n", " @constraint(sudoku, sum(x[i,ind,k] for i in 1:9) == 1)\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we have the to enforce the constraint that each digit appears once in each of the nine 3x3 sub-grids. Our strategy will be to index over the top-left corners of each 3x3 square with `for` loops, then sum over the squares." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "for i = 1:3:7, j = 1:3:7, k = 1:9\n", " # i is the top left row, j is the top left column\n", " # We'll sum from i to i+2, e.g. i=4, r=4, 5, 6\n", " @constraint(sudoku, sum(x[r,c,k] for r in i:i+2, c in j:j+2) == 1)\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The final step is to add the initial solution as a set of constraints. We'll solve the problem that is in the picture at the start of the notebook. We'll put a `0` if there is no digit in that location." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "# The given digits\n", "init_sol = [ 5 3 0 0 7 0 0 0 0;\n", " 6 0 0 1 9 5 0 0 0;\n", " 0 9 8 0 0 0 0 6 0;\n", " 8 0 0 0 6 0 0 0 3;\n", " 4 0 0 8 0 3 0 0 1;\n", " 7 0 0 0 2 0 0 0 6;\n", " 0 6 0 0 0 0 2 8 0;\n", " 0 0 0 4 1 9 0 0 5;\n", " 0 0 0 0 8 0 0 7 9]\n", "for i = 1:9, j = 1:9\n", " # If the space isn't empty\n", " if init_sol[i,j] != 0\n", " # Then the corresponding variable for that digit\n", " # and location must be 1\n", " @constraint(sudoku, x[i,j,init_sol[i,j]] == 1)\n", " end\n", "end" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "# solve problem\n", "optimize!(sudoku)" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "has_values(sudoku) = true\n", "termination_status(sudoku) == MOI.OPTIMAL = true\n", "primal_status(sudoku) == MOI.FEASIBLE_POINT = true\n" ] }, { "data": { "text/plain": [ "true" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# test if optimization worked out properly\n", "@show has_values(sudoku)\n", "@show termination_status(sudoku) == MOI.OPTIMAL\n", "@show primal_status(sudoku) == MOI.FEASIBLE_POINT" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To display the solution, we need to look for the values of `x[i,j,k]` that are 1." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9×9 Array{Int64,2}:\n", " 5 3 4 6 7 8 9 1 2\n", " 6 7 2 1 9 5 3 4 8\n", " 1 9 8 3 4 2 5 6 7\n", " 8 5 9 7 6 1 4 2 3\n", " 4 2 6 8 5 3 7 9 1\n", " 7 1 3 9 2 4 8 5 6\n", " 9 6 1 5 3 7 2 8 4\n", " 2 8 7 4 1 9 6 3 5\n", " 3 4 5 2 8 6 1 7 9" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Extract the values of x\n", "x_val = value.(x)\n", "# Create a matrix to store the solution\n", "sol = zeros(Int,9,9) # 9x9 matrix of integers\n", "for i in 1:9, j in 1:9, k in 1:9\n", " # Integer programs are solved as a series of linear programs\n", " # so the values might not be precisely 0 and 1. We can just\n", " # round them to the nearest integer to make it easier\n", " if round(Int,x_val[i,j,k]) == 1\n", " sol[i,j] = k\n", " end\n", "end\n", "# Display the solution\n", "sol" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Which is the correct solution:\n", "\n", "

A completed Sudoku puzzle

" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.0.3", "language": "julia", "name": "julia-1.0" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.0.3" } }, "nbformat": 4, "nbformat_minor": 1 }