Sudoku

Project created to solve sudoku game for any square dimension (9x9, 16x16, 25x25 ...) employing linear problem concepts.

You can also check a linear solution to solve Radar Positioning problem here.

How to run  |   Dependencies  |   What is sudoku?  |   What is linear programming?  |   Sudoku model  |   Credits

🏃 How to run

python3 LP_Sudoku.py sudoku_9x9.txt

Input example

9
3 0 6 5 0 8 4 0 0
5 2 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 5 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 0 5 2 0 6 3 0 0

Output example

3  1  6  | 5  7  8  | 4  9  2
5  2  9  | 1  3  4  | 7  6  8
4  8  7  | 6  2  9  | 5  3  1
-------------------------------
2  6  3  | 4  1  5  | 9  8  7
9  7  4  | 8  6  3  | 1  2  5
8  5  1  | 7  9  2  | 6  4  3
-------------------------------
1  3  8  | 9  4  7  | 2  5  6
6  9  2  | 3  5  1  | 8  7  4
7  4  5  | 2  8  6  | 3  1  9

📝 Dependencies

gurobipy library must be installed.

Installation instructions in Gurobi.

---

🎲 What is sudoku?

Sudoku is a logic puzzle game with the objective to fill a 9x9 grid with digits from 1 to 9. It respects a set of rules to fill this grid:

• Each row must have all digits from 1 to 9
• Each column must have all digits from 1 to 9
• Each of the nine 3x3 subgrid must have all digits from 1 to 9

✏️ What is linear programming?

Linear programming is a technique used to solve optimization problems where the elements have a linear relationship.

Linear programs aims to maximize a objective function made of decision variables subject to constraints which ensures that all the elements have a linear relationship and all variables are non-negative.

📐 Sudoku model

In this case we just want to find a combination of variables that solves the puzzle. Therefore there will be no objetive function do be maximized, only linear constraints as follows:

$$\sum_{i=1}^nx_{ijk} \ = \ 1 \ \text{for} \ j,k \ \in \ [1,n]$$

$$\sum_{j=1}^nx_{ijk} \ = \ 1 \ \text{for} \ i,k \ \in \ [1,n]$$

$$\sum_{k=1}^nx_{ijk} \ = \ 1 \ \text{for} \ i,j \ \in \ [1,n]$$

$$\sum_{j=3p-2}^{3p} \ \sum_{i=3q-2}^{3q}x_{ijk} \ = \ 1 \ \text{for} \ k \ \in \ [1,n] \ \text{and} \ p,q \ \in \ \left[ 1,\sqrt n \right]$$

We want to generalize the problem to solve a sudoku of any square dimension (9x9, 16x16, 25x25 ...). For that purpose, $n$ represents the dimension of the puzzle, $x_{ijk}$ are decision variables, $i$ represents the columns, $j$ represents the rows, $k$ represents all possible digitis depending on the puzzle dimension, and $p$ and $q$ represents an auxiliar variable to iterate in all subgrids.

The first and the second constraints ensures that all columns and all rows will be filled must have only one of the available digits. The third constraint ensures that each cell in the grid will have only one digit. The last constraint ensures that all subgrid will have only one of the available digits.

---

🍪 Credits

Thanks to Harshit Sidhwa in providing back tracking code as an inspiration to solve this problem.