| |||||||||||
| |||||||||||
Python notebooks Description Python notebooks available in the GitHub repository python-notebooks.
Source Files By clicking on a file name, a preview is opened at the bottom of this page. sudoku.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "2c9533a6",
"metadata": {},
"source": [
"# **Solving a Sudoku problem**"
]
},
{
"cell_type": "markdown",
"id": "cebb2eb7",
"metadata": {},
"source": [
"***sudoku.ipynb***\n",
"\n",
"Sudoku: place numbers from 1 to 9 into a 9x9 grid such that no number repeats in any row, in any column, and in any 3x3 sub-grid. \n",
"\n",
"© Copyright 2025 Fair Isaac Corporation\n",
"\n",
"Licensed under the Apache License, Version 2.0 (the \"License\"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0.\n",
" \n",
"Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
"\n",
"This example uses FICO® Xpress software. By running it, you agree to the Community License terms of the [Xpress Shrinkwrap License Agreement](https://community.fico.com/s/contentdocument/06980000002h0i5AAA) with respect to the FICO® Xpress software. See the [licensing options](https://www.fico.com/en/fico-xpress-trial-and-licensing-options) overview for additional details and information about obtaining a paid license."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c858d7e1",
"metadata": {},
"outputs": [],
"source": [
"# Install the xpress package\n",
"%pip install -q xpress"
]
},
{
"cell_type": "markdown",
"id": "413d5489",
"metadata": {},
"source": [
"## Problem description and formulation\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "12f8b922",
"metadata": {},
"source": [
"In classic sudoku, the objective is to fill a $n \\times n$ grid with digits so that each column, each row, and each of the nine $q \\times q$ subgrids that compose the grid (also called \"boxes\", \"blocks\", or \"regions\") contains all of the digits from 1 to $n$. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.\n",
"\n",
"Several formulations exist for this problem, where choosing the right variables is a fundamental step. Although all cells must contain integer numbers, using integer decision variables would make it hard to guarantee that they are different within a given block (row/column) with a mathematical programming formulation. Alternatively, a Constraint Programming formulation can be applied, as shown in the blog post [Solving Sudoku: A Constraint Programming Play](https://community.fico.com/s/blog-post/a5Q4W000001V7gdUAC/fico2486).\n",
"\n",
"In this example, we use binary variables $assign_{i,j,k}$ that indicate whether a value $k \\in \\{1,..,9\\}$ is assigned to a given cell $i,j \\in \\mathcal{N}$ of the grid (=1) or not (=0). Also, no objective function is needed: this is a __feasibility__ problem not an __optimization__ problem, subject to the following constraints:\n",
"\n",
"* Each cell can only have one value: \n",
"$$\\sum_{k \\in \\mathcal{N}} assign_{i,j,k} = 1, \\qquad \\forall i,j \\in \\mathcal{N}$$\n",
"\n",
"* Assign values already in grid ($g_{i,j}$ has a positive value): \n",
"$$assign_{i,j,k} = 1, \\qquad \\forall i,j \\in \\mathcal{N}, k = g_{i,j}, g_{i,j} > 0$$\n",
"\n",
"* Every number must appear once on every row:\n",
"$$\\sum_{j \\in \\mathcal{N}} assign_{i,j,k} = 1, \\qquad \\forall i,k \\in \\mathcal{N} $$\n",
"\n",
"* Every number must appear once on every column:\n",
"$$\\sum_{i \\in \\mathcal{N}} assign_{i,j,k} = 1, \\qquad \\forall j,k \\in \\mathcal{N} $$\n",
"\n",
"* Every number must appear once in every $q \\times q$ block:\n",
"$$\\sum_{i,j \\in \\mathcal{Q}: n = i+q.h, m = j+q.l} assign_{n,m,k} = 1, \\qquad \\forall h,l \\in \\mathcal{Q}, \\forall k \\in \\mathcal{N} $$\n",
"\n",
"where $\\mathcal{N}=\\{1,..,9\\}$ and $\\mathcal{Q}=\\{1,..,3\\}$."
]
},
{
"cell_type": "markdown",
"id": "01a45272",
"metadata": {},
"source": [
"## Data preparation"
]
},
{
"cell_type": "markdown",
"id": "22d335b2",
"metadata": {},
"source": [
"The input is a starting grid where the unknown numbers are replaced by zero. We start with a $9 \\times 9$ grid, and provide a $16 \\times 16$ option at the bottom of this notebook. \n",
"\n",
"| | | | | | | | | |\n",
"|---|---|---|---|---|---|---|---|---|\n",
"| 8 | | | | | | | | |\n",
"| | | 3 | 6 | | | | | |\n",
"| | 7 | | | 9 | | 2 | | |\n",
"| | 5 | | | | 7 | | | |\n",
"| | | | | 4 | 5 | 7 | | |\n",
"| | | | 1 | | | | 3 | |\n",
"| | | 1 | | | | | 6 | 8 |\n",
"| | | 8 | 5 | | | | 1 | |\n",
"| | 9 | | | | | 4 | | |"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "5ab9befe",
"metadata": {},
"outputs": [],
"source": [
"import xpress as xp\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"import math\n",
"\n",
"# Initial data for the sudoku solver\n",
"grid3x3 = \\\n",
" [[8, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 3, 6, 0, 0, 0, 0, 0],\n",
" [0, 7, 0, 0, 9, 0, 2, 0, 0],\n",
" [0, 5, 0, 0, 0, 7, 0, 0, 0],\n",
" [0, 0, 0, 0, 4, 5, 7, 0, 0],\n",
" [0, 0, 0, 1, 0, 0, 0, 3, 0],\n",
" [0, 0, 1, 0, 0, 0, 0, 6, 8],\n",
" [0, 0, 8, 5, 0, 0, 0, 1, 0],\n",
" [0, 9, 0, 0, 0, 0, 4, 0, 0]]\n",
"\n",
"grid = grid3x3\n",
"q = 3"
]
},
{
"cell_type": "markdown",
"id": "dc2bceef",
"metadata": {},
"source": [
"## Model implementation and results"
]
},
{
"cell_type": "markdown",
"id": "36488945",
"metadata": {},
"source": [
"When passing sets, lists, or range objects to [prob.addVariables()](https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/python/HTML/problem.addVariables.html), the result is a Python dictionary of variables, whose keys are tuples of indices. Variables $x$ are created this way.\n",
"\n",
"The constraints are then created and added to the problem directly by passing the corresponding expression as a list comprehension. Note that no objective is set as this is a feasibility problem."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "aeeb2976",
"metadata": {},
"outputs": [],
"source": [
"# Main dimensions of the problem: q is the size of the qxq block (3x3 in the classic Sudoku game).\n",
"\n",
"n = q**2 # the size must be the square of the size of the subgrids\n",
"N = range(n) # set of numbers from 0 to n-1\n",
"Q = range(q) # set of numbers from 0 to q-1\n",
"\n",
"# Create a model\n",
"prob = xp.problem()\n",
"\n",
"assign = prob.addVariables(N, N, N, vartype=xp.binary)\n",
"\n",
"# Constraint 1: each cell can only have one value\n",
"prob.addConstraint(xp.Sum(assign[i,j,k] for k in N) == 1 for i in N for j in N)\n",
"\n",
"# Constraint 2: fix the cells in the starting grid\n",
"prob.addConstraint(assign[i,j,grid[i][j] - 1] == 1 for i in N for j in N if grid[i][j] > 0)\n",
"\n",
"# Constraint 3a: Every number must appear once on every row\n",
"prob.addConstraint(xp.Sum(assign[i,j,k] for j in N) == 1 for i in N for k in N)\n",
"\n",
"# Constraint 3b: ... and on every column\n",
"prob.addConstraint(xp.Sum(assign[i,j,k] for i in N) == 1 for j in N for k in N)\n",
"\n",
"# Constraint 3c: Every number must appear once in every qxq block\n",
"prob.addConstraint(xp.Sum(assign[i+q*h,j+q*l,k] for i in Q for j in Q) == 1 for h in Q for l in Q for k in N)\n",
"\n",
"prob.optimize()"
]
},
{
"cell_type": "markdown",
"id": "36ecae50",
"metadata": {},
"source": [
"Now we use *matplotlib* to visualize the solution in a $n\\times n$ grid."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fa6ea6d2",
"metadata": {},
"outputs": [],
"source": [
"# Visualize solution\n",
"fig, ax = plt.subplots()\n",
"\n",
"min_val, max_val, diff = 0, n, 1\n",
"\n",
"N_points = (max_val - min_val) / diff\n",
"ind_array = np.arange(min_val, max_val, diff)\n",
"\n",
"# This is used to visualize the Sudoku solution with the 16x16 grid below.\n",
"encode = {1: '1', 2: '2', 3: '3', 4: '4', 5: '5',\n",
" 6: '6', 7: '7', 8: '8', 9: '9', 10: 'A',\n",
" 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F', 16: 'G'}\n",
"\n",
"xsol = prob.getSolution(assign)\n",
"\n",
"for i1 in Q:\n",
" for i2 in Q:\n",
" for j1 in Q:\n",
" for j2 in Q:\n",
" c = encode[math.floor(1 + sum(xsol[i1*q + i2,j1*q + j2,k]*k for k in N) + 0.5)]\n",
" ax.text (j1*q + j2, n - 1 - (i1*q + i2), c, va='center', ha='center')\n",
"\n",
"ax.set_aspect('equal', 'box')\n",
"#set tick marks for grid\n",
"ax.set_xticks(np.arange(min_val-diff/2, max_val-diff/2))\n",
"ax.set_yticks(np.arange(min_val-diff/2, max_val-diff/2))\n",
"ax.set_xticklabels([])\n",
"ax.set_yticklabels([])\n",
"ax.set_xlim(min_val-diff/2, max_val-diff/2)\n",
"ax.set_ylim(min_val-diff/2, max_val-diff/2)\n",
"ax.grid()\n",
"plt.show()\n"
]
},
{
"cell_type": "markdown",
"id": "703fbd28",
"metadata": {},
"source": [
"## A variant with a $16\\times 16$ grid"
]
},
{
"cell_type": "markdown",
"id": "7d34f0be",
"metadata": {},
"source": [
"Below is a sudoku on a $16\\times 16$ grid. Just run this cell and restart from the first cell under the \"*Model implementation and results*\" section."
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "b7d47eeb",
"metadata": {},
"outputs": [],
"source": [
"grid4x4 = \\\n",
" [[ 0, 0,12, 0, 0, 2, 0, 0, 0, 7, 3, 0,13,15, 0, 0],\n",
" [15, 0, 0, 0, 0, 3, 0, 0, 9, 0, 0, 0,12, 0, 0,10],\n",
" [ 0, 0, 0, 0, 9, 0, 6, 0, 0, 0,12, 0, 0, 0, 2, 5],\n",
" [ 6,11, 1, 0, 0,10, 5, 0, 0, 2, 0,15, 0, 0, 0, 0],\n",
" [ 4, 6, 3, 0, 0, 0,13,14, 0, 0, 0, 0, 0, 7, 0, 0],\n",
" [ 0,15,11, 0, 7, 0, 9, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n",
" [ 0, 1, 0,10,15, 0, 0, 0,11, 3,14, 0, 6, 0, 0, 0],\n",
" [13, 0, 8, 7, 0, 5, 0, 0, 0, 1, 9,12, 0, 0, 0, 0],\n",
" [ 0, 0, 0, 6, 3, 7,15, 4, 0, 0, 0, 0, 0,14, 0, 0],\n",
" [ 0, 8, 0, 0, 0, 0, 0, 0, 0,11, 7, 0, 4, 0, 0, 0],\n",
" [ 0, 0, 0, 0, 0, 0, 0, 0,13, 0, 0, 6, 9, 0, 3, 0],\n",
" [ 0, 0, 0, 0, 2, 8,14, 0, 3, 0, 0,10, 0, 0,13, 7],\n",
" [ 0, 0, 0, 8, 0, 0, 0, 7,10, 0, 0, 0, 0, 0, 5, 1],\n",
" [ 0, 4,10, 1, 6, 0, 0, 0, 0,12, 0,14, 7, 3, 9,15],\n",
" [ 3, 0,15, 0, 0, 0, 0, 8, 0, 0, 1, 0,14,12, 0, 0],\n",
" [ 2, 0, 0, 9,12, 0, 0, 1, 0, 0, 0, 0, 0, 6, 8, 0]]\n",
"\n",
"grid = grid4x4\n",
"q = 4"
]
}
],
"metadata": {
"celltoolbar": "Raw Cell Format",
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.9"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
| |||||||||||
| © Copyright 2025 Fair Isaac Corporation. |
