Super Sudoku

10 min readMar 31, 2020

1 The well known Sudoku Puzzle

1.1 Introduction

The Sudoku version played on a 9 x 9 squares board, is a well known puzzle game. The goal of the puzzle is for the player to put a digit from 1 to 9 in each free square, so that: (a) in every row of 9 squares, no digit occurs more than once (b) in every column of 9 squares, no digit occurs more than once (c) in every marked 3x3 subsquare, no digit occurs more than once. A given 9 * 9 Sudoku puzzle typically contains some squares that already contain a number from 1 to 9. An example Sudoku challenge, taken from [1] is:

which visualises as

1.2 Sudoku Model Formulation

A Sudoku is a quintessential problem to formulate as an Integer Linear Programming (ILP) problem. The basic version is also easy to solve. Its mathematical declarative model can be stated as follows.

1.2.1 Sets and Indices

𝐷 ∈ ℕ : meta sudoku dimension of the Sudoku board.

n̅ =D²: the maximum number to be filled out in the Sudoku. The minimum number is always 1.

s ∈ S: indices for the row resp. column of a SubSquare of the Sudoku board, starting at 0, up to the number of rows reps. columns of a SubSquare -1 included.

𝑟 ∈ 𝑅: indices for the row of the Sudoku board, starting at 0, up to the number of rows -1 included.

𝑐 ∈ C: indices for the column of the Sudoku board, starting at 0, up to the number of columns -1 included.

𝑛 ∈ N: indices for the allowable number set of the Sudoku board, starting at 0 up to n̅-1 included.

𝑛 ∈ N⁺: allowed numbers for each square on the Sudoku board, starting at 1 up to n̅ included.

1.2.2 Parameters

𝑓:𝑅×𝐶 ↦𝑁: specifies the already decided — fixed — numbers for some board squares in the Sudoku problem definition. fn:𝑅×𝐶×𝑁 ↦𝑁 is 1 if n is the number decided for row r and column c of the Sudoku board and 0 otherwise. Typically, not all combinations of r and c are specified in 𝑓.

1.2.3 Decision Variables

𝑏:𝑅×𝐶×𝑁⁺ ↦{0,1}. This 3D matrix of variables maps a triplet (r,c,n) on 1, if we decide to put in row r and column c the number n. Otherwise, the decision variable is equal to zero.

n:𝑅×𝐶 ↦𝑁⁺. This 2D matrix of variables maps a couple (r,c) on n, if we decide to put in row r and column c the number n. Otherwise, the decision variable is equal to zero. They formulate a more direct way to represent the solution than the b variables. Of course b and n cannot be decided upon separately so there will be binding constraints between them.

1.2.4 Objective Function

Since Sudoku is a feasibility problem only, there is no concept of optimality here and so no objective function to be minimized or maximized needs to be specified.

1.2.5 Constraints

Square-wise constraints. Each square of the Sudoku board holds exactly 1 number 𝑛∈𝑁+.

Row-wise constraints. For each row 𝑟, ensure that each number 𝑛∈𝑁⁺ occurs exactly once.

Columns-wise constraints. For each column 𝑐, ensure that each number 𝑛∈𝑁⁺ occurs exactly once.

SubBoard-wise constraints. For each 𝐷∗𝐷-sized subboard 𝑛, ensure that each number 𝑛∈𝑁⁺ occurs exactly once.

Note that the indices of b here are still relatively simple formulae thanks to the fact of having offset 0 for rows and columns.

Preset squares constraints.

Linking constraints between binary and numeric decision variables.

Note that the n+1 in the two last equations above occurs because the set N is offset 0 based while the function f as well as the variables n and the set N⁺ are all offset 1 based.

2 General Implementation in Python3 with gurobipy API to the Gurobi MILP Solver

2.1 Store a Sudoku Problem specification in a Json File

We store the Sudoku problem formulation in a json file, like this one.

cat 'sudokuDim3.json'

which gives

{
  "dim": 3,
  "fixed": {
    "1": {
      "1": "5",
      "2": "3",
      "5": "7"
    },
    "2": {
      "1": "6",
      "4": "1",
      "5": "9",
      "6": "5"
    },
    "3": {
      "2": "9",
      "3": "8",
      "8": "6"
    },
    "4": {
      "1": "8",
      "5": "6",
      "9": "3"
    },
    "5": {
      "1": "4",
      "4": "8",
      "6": "3",
      "9": "1"
    },
    "6": {
      "1": "7",
      "5": "2",
      "9": "6"
    },
    "7": {
      "2": "6",
      "7": "2",
      "8": "8"
    },
    "8": {
      "4": "4",
      "5": "1",
      "6": "9",
      "9": "5"
    },
    "9": {
      "5": "8",
      "8": "7",
      "9": "9"
    }
  },
  "solved":
  {
  }
}

The “dim” field indicates the dimension of the Sudoku which is in the most common case equal to 3. The “fixed” field prefixes a dictionary with first key being the Sudoku board row, second key being the board column and the value being the number that is already decided for that row and column of the board.

2.2 Read a Sudoku Problem from a Json File

We then write a function to read the sudoku from such a json file, perform some checks at the same time and return us the dimension “dim” and the “fixed” data structure as a python dictionary.

This prints

I have read a valid MetaSudoku problem description of dimension 3.

2.3 Solve a Sudoku Problem

The following function solves the problem using the solver Gurobi and its python API, called gurobipy.

This outputs

Using license file /Library/gurobi901/gurobi.lic
Gurobi Optimizer version 9.0.1 build v9.0.1rc0 (mac64)
Optimize a model with 435 rows, 810 columns and 3996 nonzeros
Model fingerprint: 0x2c4eb571
Variable types: 0 continuous, 810 integer (729 binary)
Coefficient statistics:
  Matrix range     [1e+00, 9e+00]
  Objective range  [0e+00, 0e+00]
  Bounds range     [1e+00, 9e+00]
  RHS range        [1e+00, 9e+00]
Presolve removed 435 rows and 810 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.01 seconds
Thread count was 1 (of 16 available processors)

Solution count 1: 0 

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%

So it is done in 10 milliseconds.

2.4 Display a solved Sudoku problem

We now want a function that generates html code because html can be easily rendered in a python notebook.

and this outputs

red numbers were specified, black numbers are solver decided

You may want to check that all constraints are indeed satisfied.

2.5 Write the solution back to a Json File

You may have spotted that our input file ‘sudokuDim3.json’, specifying the Sudoku problem, contained an empty subdictionary with key “solved” and that it was not read at all by the function ‘read_sudoku_from_json_file_and_check’. This is of course a placeholder for the solution to be written back. Let’s write a function to do that. Note that we want to keep the separation between the fixed and the solved squares in the output file.

cat 'sudokuDim3_solved.json

gives

{
  "dim": 3,
  "fixed": {
    "1": {
      "1": "5",
      "2": "3",
      "5": "7"
    },
    "2": {
      "1": "6",
      "4": "1",
      "5": "9",
      "6": "5"
    },
    "3": {
      "2": "9",
      "3": "8",
      "8": "6"
    },
    "4": {
      "1": "8",
      "5": "6",
      "9": "3"
    },
    "5": {
      "1": "4",
      "4": "8",
      "6": "3",
      "9": "1"
    },
    "6": {
      "1": "7",
      "5": "2",
      "9": "6"
    },
    "7": {
      "2": "6",
      "7": "2",
      "8": "8"
    },
    "8": {
      "4": "4",
      "5": "1",
      "6": "9",
      "9": "5"
    },
    "9": {
      "5": "8",
      "8": "7",
      "9": "9"
    }
  },
  "solved": {
    "1": {
      "3": 4,
      "4": 6,
      "6": 8,
      "7": 9,
      "8": 1,
      "9": 2
    },
    "2": {
      "2": 7,
      "3": 2,
      "7": 3,
      "8": 4,
      "9": 8
    },
    "3": {
      "1": 1,
      "4": 3,
      "5": 4,
      "6": 2,
      "7": 5,
      "9": 7
    },
    "4": {
      "2": 5,
      "3": 9,
      "4": 7,
      "6": 1,
      "7": 4,
      "8": 2
    },
    "5": {
      "2": 2,
      "3": 6,
      "5": 5,
      "7": 7,
      "8": 9
    },
    "6": {
      "2": 1,
      "3": 3,
      "4": 9,
      "6": 4,
      "7": 8,
      "8": 5
    },
    "7": {
      "1": 9,
      "3": 1,
      "4": 5,
      "5": 3,
      "6": 7,
      "9": 4
    },
    "8": {
      "1": 2,
      "2": 8,
      "3": 7,
      "7": 6,
      "8": 3
    },
    "9": {
      "1": 3,
      "2": 4,
      "3": 5,
      "4": 2,
      "6": 6,
      "7": 1
    }
  }
}

2.6 One function to read, solve, write and display a Sudoku

Taking it all together we can bundle the reading, solving and displaying into one function.

2.7 Fixed point check

The fixed part of this dictionary is of course exactly the same as of the unsolved version in the file ‘sudokuDim3.json’. This means we could test that the solved version solves to the same solution.

generates in 0.01 seconds the same solution. Indeed

diff sudokuDim3_solved.json sudokuDim3_solved_solved.json

gives no output, meaning the files are identical.

3 Meta Sudoku

By the definition of the variable D above, or just by the title of this article, you will have realised that
a Sudoku can be extended to higher values of dim. An example of a Meta Sudoku of dimension 4 is for example.

3.1 Scaling Down

Oh, let’s first try to solve smaller Sudokus, like for D=1 and for D=2. That’s a good test to see if our code is robust against corner cases.

gives after 10 ms

which is easy to check for correctness.

gives in 0 seconds

That’s fine and the only 1x1 Sudoku around.ound.

gives in no time

Even that works! :) That may not surprise you but for example the solver XPRESS, at least for its C++ API in 2016, gave an error if you pass it a problem with 0 variables and zero constraints.

3.2 Scaling Up

Time to scale up now. How about dimension 4?

gives after 1.41 seconds

gives after 38.55 seconds

Click on it once to see it in the original, better resolution.

gives after 1416.57 seconds

gives after 2807.12 seconds

4 Cross Testing Solvers on Super Sudoku

The gurobi Python API works only with the Gurobi solver. However a quick rewrite in AMPL allows to test different IP solvers on Super Sudoku problem instances.
The AMPL general model looks like the one below. (The N=3 below can simply be replaced with the dimension called ‘D’ in the above.)

Running various tests with this code with different Sudoku dimensions, we were able to generate a DB with results and a graph from that.

in a python notebook, directly displays the svg figure. Here, in this Medium article, we show a png converted with the command

rsvg-convert -h 960 sudokuSolverTimes.svg sudokuSolverTimes.png

Note that the solver versions pitched against each other here were CBC 2.9.7, CPLEX 12.6 and Gurobi 7.0.2.

We clearly see that for Sudoku dimensions of 0,1,2,3 times are below 1 second and so don’t matter much. For the smaller problems of dimension 3 and 4, cplex is faster than CBC, which is faster than gurobi, but we are talking about times in the range: 0.01 to 25 seconds, which is not a long wait. For dimensions 5 and 6, gurobi becomes the fastest solver, then cbc and then cplex. So the order completely turns around. In this range we have solver times from 28 seconds to 282236 seconds (which is 3.26 days), so there waiting time starts to matter.

5 Other Sudoku Related Ideas

An App on your phone that would recognize a Sudoku problem by camera, also recognize the filled in digits using some OCR and then immediately solve the problem and overlay the solution on screen in an Augmented Reality sense would not save the world, but still be really cool, right?! :)

We can very well solve Sudokus by computer now, but in fact Sudokus are created because some humans seem to derive pleasure from solving them with their natural brains. So depriving them from that satisfaction is not a very useful undertaking. Here, we have been reading Sudokus from a json file, but I generated them manually in a pretty much trial and error way. As for both human and computer generation of them, generation of random numbers for some random squares can lead to infeasible Sudoku problems. So clearly something smarter is needed. It could be enjoyable to dabble a bit into that. However, there are plenty to be found on the internet already.

I also wonder how a technique like reinforcement learning could solve these discrete optimisation problems. We could have agents per constraint, each trying to satisfy their constraint, without coordination with any other agent. They would receive a reward if their constraint is satisfied or close to satisfied. Would that work? Or, due to the discrete nature of the problem, rather just keep oscillating and never converge to a valid solution? It sounds quite similar to decoupling a MILP approach into an ADMM approach, which also generally has no guarantees to converge to a solution when integer variables are contained in the problem. However, [2] argues it proves convergence for a special ADMM case it set up.

6 References

[1] Sudoku Solving Algorithms, Wikipedia (https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Computation_time)

[2] Baoyuan Wu, Bernard Ghanem, lp-Box ADMM: A Versatile Framework for Integer Programming. (https://arxiv.org/pdf/1604.07666.pdf)

The code snippets in this article are all from the complete notebook at GitHub: https://github.com/PeterSels/OnComputation/tree/master/SuperSudoku.The notebook gist is available at https://gist.github.com/PeterSels/02be944085006dd9f6cf7fb0bd527c3f.

Peter Sels, March 22nd, 2020.