Representing Sudoku variants as set multicover problems
In previous posts, I introduced the Miracle Sudoku variant and my variant sudoku solver package, which I used for enumerating solutions to that variant. I also explained the algorithm that package uses for solving set-multicover problems: Knuth's dancing links.
In this post, I'll quickly explain how Sudoku problems can be represented as set multicover problems.
Recall the definition of an exact cover problem, and its generalization to set multicover and multiset multicover problems:
A covering problem instance consists of a set of constraints and a set of choices. The constraints simply form an abstract set, with each choice being a subset of the constraints. The intended interpretation is that a given choice satisfies its constraints.
The goal of an exact cover problem is to pick a minimal set of choices to satisfy every constraint.
And we have a matrix representation of exact cover problems:
To put things more concretely, we can take the same approach as Knuth and view the covering problem instance as a 2D matrix, where columns correspond to constraints and rows correspond to choices.
Enumerating the columns \(c\) and rows \(r\), we get a matrix representation \(A\) of the covering problem by placing a \(1\) in \(A(r, c)\) if choice \(r\) belongs to constraint \(c\).
For set multicover problems, the constraints are a multiset, with the intended interpretation being that a constraint which appears with multiplicity should be satisfied as many times as the multiplicity demands.
Another generalization we will require for variant sudoku is to allow for some constraints to be optional: meaning that they can fail to be satisfied, but must not be satisfied more than the specified limit of times.
It's easier to start with a simpler combinatorial example: the \(n\) queens problem. For \(n=8\), the problem asks to find a way to place \(8\) queens on a standard chessboard so that no queen attacks any other queen.
The problem can be represented as an exact cover problem with some optional constraints. The constraints can be identified with the rows (ranks) and columns (files) of the board, along with optional constraints for each diagonal. Each square on the board is a choice, satisfying the row, column, and two diagonals the square belongs to.
In our Sudoku.multicover module, we can represent the \(8\)-queens problem as follows:
from sudoku.multicover import SetMultiCover as SMC
def n_queens_problem(n=8):
constraints = {
("queen_on_position", i, j): (
("queen_on_rank", i),
("queen_on_file", j),
("queen_on_backward_diag", i - j + n - 1),
("queen_on_forward_diag", i + j),
)
for i, j in [(i,j) for i in range(n) for j in range(n)]
}
return SMC(
constraints, must_satisfy=[(r, i) for r in ("queen_on_rank", "queen_on_file") for i in range(8)]
)
N = 8
print(
f"----\nFound {sum(1 for _ in n_queens_problem(N))} solutions to the {N} queens problem"
)
Output ...
----
Found 92 solutions to the 8 queens problem
We can take the ranks and files as required constraints because a solution to the \(8\) queens problem will necessarily satisfy each of those constraints: we have to place \(8\) queens on the baord, there are only 8 ranks and 8 files, and no two queens can occupy the same rank or file without attacking each other. So by the pigeonhole principle, all the ranks and all the files must be filled.
The diagonals are also constraints, meaning we can only have at most one queen on them, but they are optional, since there are many more diagonals than there are queens to fill them.
What if we wanted to place knights on a board so they don't attack each other? Well, we could write the optional constraints for knights as follows:
knight_choices = {
(i, j): [
("knight", i, j, i + 2, j + 1),
("knight", i, j, i + 2, j - 1),
("knight", i - 2, j + 1, i, j),
("knight", i - 2, j - 1, i, j),
("knight", i, j, i + 1, j + 2),
("knight", i, j, i + 1, j - 2),
("knight", i - 1, j + 2, i, j),
("knight", i - 1, j - 2, i, j),
]
for i, j in product(range(N), range(N))
}
The constraints consist of any pair of squares separated by a knight's move, and each square belongs to exactly eight such pairs. Again, these constraints are optional, because there are many more pairs of squares separated by a knight's move than there are knights you can place on the board.
Since all of these constraints are optional, unfortunately Knuth's algorithm cannot be used on this puzzle without significant modification. As soon as there are only optional constraints remaining, Knuth's algorithm returns the partial solution it has constructed as a successful solution, meaning it would place no knights at all on the board.
So what about a Sudoku puzzle? Well, the traditional Sudoku puzzle represents very simply as an exact cover problem. Here are the traditional sudoku constraints from the Sudoku.variant_sudoku module in my Sudoku package:
## Constraints for a traditional sudoku
_base_choices = {
(i, j, k): [ # Traditional Sudoku constraints
("position", i, j),
("row", i, k),
("column", j, k),
("box", (i // (N / 3)) * (N / 3) + (j // (N / 3)), k),
]
for N, (i, j, k) in zip(cycle((N,)),product(range(N), range(N), range(1, N + 1)))
}
The choice (i, j, k) represents that the digit k has been written into the cell (i,j). Each such choice satisfies constraints on its position, its row, column, and box. Also, only one digit can appear in a given box, so we also have a constraint for the cell itself.
All these constraints must be satisfied, so we have the following list of required constraints:
## The constraints for a traditional Sudoku which _must_ be satisfied
_must_con = (
[("position", i, j) for i, j in product(range(N), range(N))]
+ [("row", i, n) for i, n in product(range(N), range(1, N + 1))]
+ [("column", j, n) for j, n in product(range(N), range(1, N + 1))]
+ [("box", b, n) for b, n in product(range(N), range(1, N + 1))]
)
The variant sudoku cosntraints I'm interested are similar to the chess constraints above. The most popular is anti-knight sudoku, however you can also get interesting variants by prohibiting the same digits from being separated by each other by a King's move, and another interesting variant is to prohibit two consecutive digits from appearing adjacent to each other orthogonally. There are all optional constraints.
Here's the whole set of variant constraints from the Sudoku.variant_sudoku module:
## Variant sudoku constraints
_king_choices = {
(i, j, n): [ # king constraints on dominos
("king", i, j, i + 1, j + 1, n),
("king", i - 1, j - 1, i, j, n),
("king", i, j, i + 1, j - 1, n),
("king", i - 1, j + 1, i, j, n),
]
for i, j, n in product(range(N), range(N), range(1, N + 1))
}
_knight_choices = {
(i, j, n): [ # knight constraints on pairs
("knight", i, j, i + 2, j + 1, n),
("knight", i, j, i + 2, j - 1, n),
("knight", i - 2, j + 1, i, j, n),
("knight", i - 2, j - 1, i, j, n),
("knight", i, j, i + 1, j + 2, n),
("knight", i, j, i + 1, j - 2, n),
("knight", i - 1, j + 2, i, j, n),
("knight", i - 1, j - 2, i, j, n),
]
for i, j, n in product(range(N), range(N), range(1, N + 1))
}
_consecutive_choices = {
(i, j, n): [ # consecutive constraints
("consec", i, j, i + 1, j, n, n + 1),
("consec", i, j, i, j + 1, n, n + 1),
("consec", i - 1, j, i, j, n, n + 1),
("consec", i, j - 1, i, j, n, n + 1),
("consec", i, j, i + 1, j, n - 1, n),
("consec", i, j, i, j + 1, n - 1, n),
("consec", i - 1, j, i, j, n - 1, n),
("consec", i, j - 1, i, j, n - 1, n),
]
for i, j, n in product(range(N), range(N), range(1, N + 1))
}