A variant sudoku solver
In a previous post, I enumerated the solutions to a recently-introduced variant sudoku called Miracle Sudoku, which combines several chess-sudoku constraints together with an adjacency constraint.
In this post, I'll demonstrate the variant sudoku library I wrote to produce those counts.
The set multicover module, with the dancing links implementation, and the variant_sudoku module are all combined into a single Python package that I've called sudoku. We can import the Sudoku class like this:
from sudoku import Sudoku
You can also go ahead and import the SetMultiCover class using relative imports, if you want to apply it to other combinatorial problems:
from sudoku.multicover import SetMultiCover as SMC
Using the package is simple. The class by default accepts input sudoku puzzles formatted as 2D arrays of digits between 1-9, with 0 representing a blanks:
# Here's a sample sudoku puzzle
grid = [
[0, 3, 2, 1, 5, 0, 0, 0, 0],
[0, 0, 5, 0, 0, 0, 2, 0, 8],
[1, 9, 0, 2, 0, 4, 0, 0, 0],
[2, 5, 7, 0, 3, 0, 6, 4, 0],
[9, 8, 0, 0, 7, 2, 0, 0, 1],
[6, 0, 0, 0, 0, 9, 0, 2, 7],
[3, 7, 8, 0, 0, 0, 9, 0, 0],
[4, 0, 0, 0, 6, 0, 0, 8, 0],
[0, 0, 0, 0, 0, 0, 3, 0, 0],
]
We can solve the puzzle by calling Sudoku() on it:
solutions = Sudoku(grid)
Sudoku() returns a generator holding all the possible solutions.
for solution in solutions:
print("----\nSolution:\n----")
print(solution)
The Sudoku class implements a __str__ dunder method, so we'll get a nicely formatted printed output:
Output ...
----
Solution:
----
832157496
745396218
196284753
257831649
984672531
613549827
378415962
429763185
561928374
We can also explore variant sudokus. Let's start with a remarkably sparse sudoku board:
grid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
]
Only one given! This would have billions of solutions using just the traditional sudoku ruleset.
But variant constraints can make this fun! Let's use the king and knight "chess sudoku" rules and add a consecutive rule:
solutions = Sudoku(grid, "king", "knight", "consecutive")
# Printing out and numbering all the solutions:
for index, solution in enumerate(solutions):
print(f"----\nSolution #{index}:\n----")
print(solution)
Output ...
----
Solution #0:
----
147582936
693147582
258693147
714258693
369714258
825369714
471825369
936471825
582936471
----
Solution #1:
----
162738495
495162738
738495162
516273849
849516273
273849516
951627384
384951627
627384951
----
Solution #2:
----
159483726
726159483
483726159
615948372
372615948
948372615
261594837
837261594
594837261
----
Solution #3:
----
174639285
528174639
963528174
417963528
852417963
396852417
741396852
285741396
639285741
----
Solution #4:
----
627384951
384951627
951627384
273849516
849516273
516273849
738495162
495162738
162738495
----
Solution #5:
----
582936471
936471825
471825369
825369714
369714258
714258693
258693147
693147582
147582936
----
Solution #6:
----
639285741
285741396
741396852
396852417
852417963
417963528
963528174
528174639
174639285
----
Solution #7:
----
594837261
837261594
261594837
948372615
372615948
615948372
483726159
726159483
159483726
The solutions are returned as Sudoku objects, the Sudoku __str__
dunder method formats them nicely for printing, but they can also
be converted back into a 2D grid list using .to_grid():
print("----\nA solution grid:\n----")
print(solutions.to_grid())
Output ...
----
A solution grid:
----
[[5, 9, 4, 8, 3, 7, 2, 6, 1],
[8, 3, 7, 2, 6, 1, 5, 9, 4],
[2, 6, 1, 5, 9, 4, 8, 3, 7],
[9, 4, 8, 3, 7, 2, 6, 1, 5],
[3, 7, 2, 6, 1, 5, 9, 4, 8],
[6, 1, 5, 9, 4, 8, 3, 7, 2],
[4, 8, 3, 7, 2, 6, 1, 5, 9],
[7, 2, 6, 1, 5, 9, 4, 8, 3],
[1, 5, 9, 4, 8, 3, 7, 2, 6]]
The sudoku package is built on a powerful set-multicover module which uses Knuth's efficient algorithm X behind the scenes, you can use it for all kinds of other combinatorial problems:
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
Try it yourself
If you'd like to play with the package yourself online without downloading the package, I've put it up on repl.it for your convenience.
Keep in mind that although the package is very fast, the spaces of various variant sudoku solutions are enormous, so you could benefit from running the code on your local machine, or a faster cloud server if you have access to one!