If you're interested in solving sudoku, you've probably heard thatPrecise coverage issues. Given the full set X and the set Y of subsets of X, there exists a subset Y* of Y such that Y* constitutes a kind of partition of X.
Here's an example written in Python.
X = {1, 2, 3, 4, 5, 6, 7}
Y = {
'A': [1, 4, 7],
'B': [1, 4],
'C': [4, 5, 7],
'D': [3, 5, 6],
'E': [2, 3, 6, 7],
'F': [2, 7]}
The only solution to this example is ['B', 'D', 'F'].
The exact coverage problem is NP-complete (translation: there is no fast enough way to find the answer in reasonable time, meaning polynomial time).Algorithm XIt was invented and realized by the great bull Goldner. He came up with an efficient implementation technique calledDance Chain, using a bi-directional linked list to represent the matrix of the problem.
However, dance chains can be quite tedious to implement and are not easy to write correctly. The next moment was to show the wonders of Python! One day I decided to write the X algorithm in Python, and I came up with an interesting variant of Dancing Chain.
arithmetic
The main idea is to use a dictionary instead of a two-way linked list to represent the matrix. We already have Y. From it we can quickly access the column elements of each row. Now we also need to generate the inverse table of the rows, in other words the ability to quickly access the row elements from the columns. To accomplish this, we convert X to a dictionary. In the above example, it should be written as
X = {
1: {'A', 'B'},
2: {'E', 'F'},
3: {'D', 'E'},
4: {'A', 'B', 'C'},
5: {'C', 'D'},
6: {'D', 'E'},
7: {'A', 'C', 'E', 'F'}}
Sharp-eyed readers will notice that this is slightly different from the Y representation. In fact, we need to be able to quickly delete and add rows to each column, which is why we use sets. On the other hand, Goldner fails to mention this, and in fact all rows are held constant throughout the algorithm.
Here is the code for the algorithm.
def solve(X, Y, solution=[]):
if not X:
yield list(solution)
else:
c = min(X, key=lambda c: len(X[c]))
for r in list(X[c]):
(r)
cols = select(X, Y, r)
for s in solve(X, Y, solution):
yield s
deselect(X, Y, r, cols)
()
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
((j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = ()
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].add(i)
It's really only 30 lines!
Formatting Input
Before solving the actual problem, we need to convert the input to the format described above. This can be handled simply like this
X = {j: set(filter(lambda i: j in Y[i], Y)) for j in X}
But this is too slow. If we set the size of X to m and the size of Y to n, then the number of iterations is m*n. In this example, the size of the Sudoku grid is N, so it would take N^5 iterations. We have a better way.
X = {j: set() for j in X}
for i in Y:
for j in Y[i]:
X[j].add(i)
This is still O(m*n) complexity, but it's the worst case. On average it performs much better because it doesn't need to traverse all the space bits. In the Sudoku example, there are exactly 4 entries per row in the matrix, regardless of size, so it has N^3 complexity.
vantage
- Simple: There is no need to construct complex data structures, all the structures used are provided by Python.
- Readability: The first example above is directly from theExamples on WikipediaDirectly transcribed!
- Flexibility: Can be easily extended to solve Sudoku.
sudoku (Japanese: sū doku)
All we need to do is describe Sudoku as an exact covering problem.here areThere is complete code for solving Sudoku, which handles any size, 3×3, 5×5, even 2×3, all in less than 100 lines of code, and includes doctest! (Thanks to Winfried Plappert and David Goodger for their comments and suggestions)