We Tango in this post. Now it's time to continue having fun with optimization and solve some mini-sudoku.
What is mini-sudoku?
Well, it is Sudoku; but, emm, well, mini.
Instead of having 3x3 blocks of 3x3, it has 3x2 blocks of 2x3. Now instead of assigning an integer from 1 to 9, you are assigning an integer from, yes you guessed it right, 1 to 6.
And just like the regular Sudoko, no number can be repeated in a row, in column, and within a block.
Here is an example of it:
How do we solve it using OR-Tool?
Remember the steps we mentioned in "Let's Tango" post?! That's how we solve it.
Step 1: Decision Variables
In this case, we have 3x2 blocks of 2x3, adding up to a total of 36 cells. Each cell can have an integer value of 1 to 6.
Step 2: Objective Function
Again, we do not have any objective function here to optimize. So we are good.
Step 3: Constraints
We have three constraints:
- The numbers must be unique in each block,
- The numbers must be unique in each row, and finally
- The number must be unique in each column.
And we are done! Let's see how we can implement that using OR-Tools.
Implementing a Mini-Sudoku Solver in OR-Tools
First of all, not claiming this is the best approach. But I am having fun with Mathematical Optimization and Constraint Programming using OR-Tools. So, let's have fun!
Implementing A Single Block
I decided to break down the problem into two classes. One that implements and take cares of each block and another that handles the entire Sudoku board by initializing the blocks.
In this section let's see the implementation of a single block of Sudoku:
class SudokuBlock:
BLOCK_ROW_SIZE: int = 2
BLOCK_COL_SIZE: int = 3
def __init__(
self,
model: CpModel,
block_row_id: int,
block_col_id: int,
block_row_size: int = BLOCK_ROW_SIZE,
block_col_size: int = BLOCK_COL_SIZE,
verbose: bool = False
):
self._verbose = verbose
self._model = model
self._block_row_id = block_row_id
self._block_col_id = block_col_id
self._block_name = f"b_{block_row_id}_{block_col_id}"
self._block_row_size = block_row_size
self._block_col_size = block_col_size
self._block_size = block_row_size * block_col_size
self._block_model_variables: list[IntVar] = []
self.init_model()
@property
def name(self) -> str:
return self._block_name
def init_model(self):
if self._verbose:
print(f"Initializing block variables for block ({self._block_row_id},{self._block_col_id}) ...")
self._block_model_variables = [
self._model.NewIntVar(
lb=1,
ub=self._block_size,
name=f"{self.name}_{cell_block_row_id}_{cell_block_col_id}"
)
for cell_block_row_id in range(self._block_row_size)
for cell_block_col_id in range(self._block_col_size)
]
# All Different Values
if self._verbose:
print("Enforcing All different values within a block ...")
self._model.AddAllDifferent(self._block_model_variables)
def block_cell_row_col_to_idx(self, block_cell_row_id: int, block_cell_col_id: int):
if (block_cell_row_id < 0) or (block_cell_row_id >= self._block_row_size):
raise ValueError(f"block_cell_row_id ({block_cell_row_id}) must be between 1 and {self._block_row_size - 1}.")
if (block_cell_col_id < 0) or (block_cell_col_id >= self._block_col_size):
raise ValueError(f"block_cell_col_id ({block_cell_col_id}) must be between 1 and {self._block_col_size - 1}.")
return block_cell_row_id * self._block_col_size + block_cell_col_id
def get_block_cell(self, block_cell_row_id: int, block_cell_col_id: int):
return self._block_model_variables[self.block_cell_row_col_to_idx(block_cell_row_id, block_cell_col_id)]The above code, creates one single block of Sudoku. Each block has:
- Block Row and Column ID, which determines where in the entire board this block is located, and
- The size of the block, of course.
The OR-Tool model (i.e. CpModel) is shared across all boards and as you can see is another input. Not generated by the block.
When the block is created, it will initialize one decision variable for each cell of the block (line 34 to 42):
self._model.NewIntVar(
lb=1,
ub=self._block_size,
name=f"{self.name}_{cell_block_row_id}_{cell_block_col_id}"
)the lb is the Lower-Bound and the ub is Upper-Bound value that each cell could have. In our case, the upper-bound is 6 (each block had 2x3 cells).
Also, OR-Tools comes with some utility method that makes life much easier, when setting up an optimization problem.
For example, if you remember one of the constraint was that each cell must have a unique values in each block; or you cannot repeat the same number in two cells that belong to the same block.
You can implement this in OR-Tools simply by using AddAllDifferent method. This is done in our code on line 47:
self._model.AddAllDifferent(self._block_model_variables)Now the entire Sudoku Board
Now, let's see an implementation of the entire Sudoku Board using the block class that we implemented above:
class MiniSudokuSolver:
GRID_ROW_SIZE: int = 3
GRID_COL_SIZE: int = 2
def __init__(
self,
init_values: list[tuple[int, int, int]],
grid_row_size: int = GRID_ROW_SIZE,
grid_col_size: int = GRID_COL_SIZE,
block_row_size: int = SudokuBlock.BLOCK_ROW_SIZE,
block_col_size: int = SudokuBlock.BLOCK_COL_SIZE,
verbose: bool = False
):
self._verbose = verbose
self._model: CpModel = CpModel()
self._solver: CpSolver = CpSolver()
self._grid_row_size=grid_row_size
self._grid_col_size=grid_col_size
self._block_row_size=block_row_size
self._block_col_size=block_col_size
self._board_row_size = self._grid_row_size * self._block_row_size
self._board_col_size = self._grid_col_size * self._block_col_size
self._board_blocks: list[SudokuBlock] = []
self.init_board(init_values)
@property
def row_range(self) -> range:
return range(self._board_row_size)
@property
def col_range(self) -> range:
return range(self._board_col_size)
def get_block(self, block_row_id: int, block_col_id: int) -> SudokuBlock:
if (block_row_id < 0) or (block_row_id >= self._grid_row_size):
raise ValueError(f"block_row_id ({block_row_id}) must be between 0 and {self._grid_row_size - 1}.")
if (block_col_id < 0) or (block_col_id >= self._grid_row_size):
raise ValueError(f"block_col_id ({block_col_id}) must be between 0 and {self._grid_col_size - 1}.")
block_id = block_row_id * self._grid_col_size + block_col_id
return self._board_blocks[block_id]
def get_cell(self, row_id: int, col_id: int):
if (row_id < 0) or (row_id >= self._board_row_size):
raise ValueError(f"row_id ({row_id}) must be between 0 and {self._board_row_size - 1}.")
if (row_id < 0) or (row_id >= self._board_col_size):
raise ValueError(f"row_id ({row_id}) must be between 0 and {self._board_col_size - 1}.")
block_row_id: int = row_id // self._block_row_size
block_col_id: int = col_id // self._block_col_size
cell_block_row_id: int = row_id % self._block_row_size
cell_block_col_id: int = col_id % self._block_col_size
return self.get_block(block_row_id, block_col_id).get_block_cell(cell_block_row_id, cell_block_col_id)
def get_value(self, row_id, col_id) -> int:
return self._solver.value(
self.get_cell(row_id, col_id)
)
def init_board(self, init_values: list[tuple[int, int, int]]):
if self._verbose:
print("Initializing board blocks ...")
self._board_blocks = [
SudokuBlock(
model=self._model,
block_row_id=block_row_id,
block_col_id=block_col_id,
block_row_size=self._block_row_size,
block_col_size=self._block_col_size,
verbose=self._verbose
)
for block_row_id in range(self._grid_row_size)
for block_col_id in range(self._grid_col_size)
]
# All Different each row
if self._verbose:
print("Enforcing All different values in a row ...")
for row_id in self.row_range:
self._model.AddAllDifferent([
self.get_cell(row_id, col_id)
for col_id in self.col_range
])
# All Different each column
if self._verbose:
print("Enforcing All different values in a column ...")
for col_id in self.col_range:
self._model.AddAllDifferent([
self.get_cell(row_id, col_id)
for row_id in self.row_range
])
# Setting initial values for cells
if self._verbose:
print("Setting Initial Cell Values ...")
for row_id, col_id, value in init_values:
self._model.add(
self.get_cell(row_id, col_id) == value
)
if self._verbose:
print("Ready to solve.")
def solve(self, print_solution: bool = False) -> bool:
status = self._solver.solve(self._model)
output = status == OPTIMAL
if output and print_solution:
solution = [
[
self.get_value(row_id, col_id)
for col_id in self.col_range
]
for row_id in self.row_range
]
print(tabulate(solution, tablefmt="grid"))
return outputAfter getting relevant information regarding the board-size and block-size, the board starts to initialize as follows:
First, from line 71 to line 81, it creates an instance of a block for each of the 7 blocks. See that the model (CpModel) that the board is created is passed to each block and each block ads its own variables and constraints.
Then, from line 83 to line 90, we add the constraint that each integer from 1 to 6 must be used only once in each row.
We are using some special or utility methods that we implemented earlier to essentially be able to pull the variable that is associated to each row, column.
Likewise, from line 101 to line 99 we are enforcing the constraint for the columns to guarantee that each columns has unique integers.
Finally, from line 104 to line 107, we are setting the initial values for certain cells that we already know what number should be associated to them. We are again setting that using constraint, rather than removing those variables as a decision variable. But we discussed this already in "Let's Tango", when we discussed pre-solve.
Let’s solve some Mini-Sudoku
Ok, let's call our code and see if it is able to solve a Sudoku. Let's call our [Mini-]Sudoku solver for the puzzle shown on top of this page.
mini_sudoku_solver = MiniSudokuSolver(
init_values=[
(0, 0, 1),
(1, 0, 2),
(1, 5, 6),
(2, 1, 3),
(2, 5, 5),
(3, 1, 4),
(3, 4, 3),
(4, 4, 4),
]
)
if mini_sudoku_solver.solve(print_solution=True):
print("Found a solution.")
else:
print("Failed to find a solution.")which you will get:
+---+---+---+---+---+---+
| 1 | 6 | 3 | 2 | 5 | 4 |
+---+---+---+---+---+---+
| 2 | 5 | 4 | 3 | 1 | 6 |
+---+---+---+---+---+---+
| 6 | 3 | 1 | 4 | 2 | 5 |
+---+---+---+---+---+---+
| 5 | 4 | 2 | 6 | 3 | 1 |
+---+---+---+---+---+---+
| 3 | 1 | 6 | 5 | 4 | 2 |
+---+---+---+---+---+---+
| 4 | 2 | 5 | 1 | 6 | 3 |
+---+---+---+---+---+---+
Found a solution.Accessing the code
If you are interested to access the code (Jupyter Notebook) and run it for yourself, you can access the entire notebook here.