{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "title: Sudoku\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Originally Contributed by**: Iain Dunning" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\"Partially\n", "

A partially solved Sudoku puzzle

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "[Sudoku](http://en.wikipedia.org/wiki/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": [], "source": [ "using JuMP\n", "using GLPK" ] }, { "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": [], "source": [ "# Create a model\n", "sudoku = Model(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": [ { "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": 6, "metadata": {}, "output_type": "execute_result" } ], "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\n", "\n", "# solve problem\n", "optimize!(sudoku)\n", "\n", "# 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", "\"Fully" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 1.5.1", "language": "julia", "name": "julia-1.5" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.5.1" } }, "nbformat": 4, "nbformat_minor": 2 }