V ← {rcols←1..} ##.X M ⍝ Exact cover: Knuth's Algorithm X.
Given a set of requirements and set of actions, each of which satisfies zero or
more of the requirements, choose a subset of the actions such that each require-
ment is satisfied exactly once.
The problem can be represented as a boolean matrix, where each row is an action
with 1s at the column positions of the requirements it satisfies.
1 2 3 4
┌───┬───┬───┬───┐ Action A satisfies requirements 2 and 4
A │ 0 │ 1 │ 0 │ 1 │ .. B .. .. .. 1 .. 2
├───┼───┼───┼───┤ .. C .. .. .. 1 .. 3
B │ 1 │ 1 │ 0 │ 0 │
├───┼───┼───┼───┤ In this case a solution is 1 0 1, as A and C
C │ 1 │ 0 │ 1 │ 0 │ together satisfy all requirements exactly once.
└───┴───┴───┴───┘
Boolean result vector [V] identifies a subset of the rows of boolean argument
matrix [M] with exactly one 1 in each column: 1∧.=+⌿V⌿M. The selected rows are
said to form an "exact cover" of the argument matrix.
If no exact cover is possible, _scalar_ 0 is returned. This means that a test
for failure might be V≡0 or 0=⍴⍴V.
Many problems, including →sudoku←, →queens← and pentomino-tiling can be reduced
to the exact cover problem. See →sudokuX←, →queensX← and ##.scripts.pentominos
For some problems, such as →queensX←, some of the columns are "optional" and so
need not be covered. Optional boolean left argument vector [rcols], default all
1s, specifies which columns are required to be covered.
Knuth's algorithm is described as being "recursive with backtracking":
[1] If ⍵ has no columns (c=0) the algorithm succeeds with a result of r⍴0
where r c←⍴⍵.
[2] Otherwise, choose any non-empty row r as a potential cover.
[3] Identify a sub-matrix of ⍵: columns not covered by r and rows not covered
by r-covered columns (because each column must be covered only once).
[4] If the sub-matrix has an exact cover, merge this with r as result.
[5] Otherwise, if there are un-tried rows besides r, try these.
[6] Otherwise, return failure.
Knuth suggests a heuristic: given that each column must be covered once and only
once, we can choose rows r by selecting a column with a minimum number of 1s and
examining only those rows selected by 1s in this column.
As an example:
1 2 3 4 5 6 7
┌───┬───┬───┬───┬───┬───┬───┐
A │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
B │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
C │ 0 │ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
D │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
E │ 0 │ 1 │ 1 │ 0 │ 0 │ 1 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
F │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘
Select any column; Knuth's heuristic recommends choosing one with a minimal num-
ber of marked rows (1s). Let's select the leftmost column [1]:
[1] 2 3 4 5 6 7
┌───┬───┬───┬───┬───┬───┬───┐
A │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
B │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
C │ 0 │ 0 │ 0 │ 1 │ 1 │ 0 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
D │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │
├───┼───┼───┼───┼───┼───┼───┤
E │ 0 │ 1 │ 1 │ 0 │ 0 │ 1 │ 1 │
├───┼───┼───┼───┼───┼───┼───┤
F │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │
└───┴───┴───┴───┴───┴───┴───┘
Selecting any marked row in this column identifies an "uncovered" sub-matrix.
First we mark columns selected by this row and then we mark rows selected by any
of the marked columns.
Arbitrarily choosing the second row and marking the covered rows and columns:
┌───────────┬───────────────── Columns marked by second row.
│ │
[1] 2 3 4 5 6 7
┌───┬───┬───┬───┬───┬───┬───┐
A │[1]│ 0 │ 0 │[1]│ 0 │ 0 │ 1 │─┬─ Rows marked by marked columns.
├───┼───┼───┼───┼───┼───┼───┤ │
[B]│[1]│ 0 │ 0 │[1]│ 0 │ 0 │ 0 │─┤
├───┼───┼───┼───┼───┼───┼───┤ │
C │ 0 │ 0 │ 0 │[1]│ 1 │ 0 │ 1 │─┘
├───┼───┼───┼───┼───┼───┼───┤
D │ 0 │ 0 │ 1 │ 0 │ 1 │ 1 │ 0 │─┬─ Unmarked rows
├───┼───┼───┼───┼───┼───┼───┤ │
E │ 0 │ 1 │ 1 │ 0 │ 0 │ 1 │ 1 │─┤
├───┼───┼───┼───┼───┼───┼───┤ │
F │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │─┘
└───┴───┴───┴───┴───┴───┴───┘
│ │ │ │ │
└───┴───────┴───┴───┴───── Unmarked columns
The algorithm is applied recursively to the unmarked submatrix, in this case the
matrix:
2 3 5 6 7
┌───┬───┬───┬───┬───┐
D │ 0 │ 1 │ 1 │ 1 │ 0 │
├───┼───┼───┼───┼───┤
E │ 1 │ 1 │ 0 │ 1 │ 1 │
├───┼───┼───┼───┼───┤
F │ 1 │ 0 │ 0 │ 0 │ 1 │
└───┴───┴───┴───┴───┘
If the recursive call fails to find an exact cover, it "backtracks" and a diff-
erent row is examined. If there are no untried rows, the search fails.
Otherwise, if the recursive call succeeds, the resulting covering vector, ext-
ended with the marked row, is returned as result.
Technical note:
In general, APL provides two ways to identify a subset of the rows and columns
of a matrix: the first is to use indices M[I;] or M[;I] and the second employs a
boolean selection vector B/M or B⌿M. The coding of X arbitrarily chooses the
second (boolean selection) method.
Ref: http://en.wikipedia.org/wiki/Algorithm_X
Alternative
-----------
Phil Last provides this alternative coding, which is good for small arrays:
X←{⍵{⍉(⍵⍴2)⊤{⍵/⍳⍴⍵}1∧.=(⍉⍺)+.∧(⍵⍴2)⊤⍳2*⍵}⍬⍴⍴⍵}
Example:
M ⍝ Constraint matrix.
1 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 0
0 1 1 0 0 1 1
0 1 0 0 0 0 1
X M ⍝ Rows that form exact cover.
0 1 0 1 0 1
(X M)⌿M ⍝ selected covering rows.
1 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 0 0 0 1
1∧.=+⌿(X M)⌿M ⍝ condition for exact cover.
1
⍝ See also →sudokuX← ⍝ Exact cover Sudoku solver.
⍝ See also →queensX← ⍝ Exact cover N-Queens solver.
⍝ See also ##.scripts.pentominos ⍝ Exact cover Pentomino tiling.
See also: Graphs assign sudoku sudokuX queensX
Back to: contents
Back to: Workspaces