Problem 56588. Exact Cover
An efficient solution to the exact cover problem can be useful in many situations. In this problem, you are welcome to use Knuth's Algorithm X (utilizing the Dancing Links technique), or any other solution.
The exact cover problem is specified here by a row vector, u, representing the universe, and a cell array, s, containing the sets (row vectors) with which to try to exactly cover the respective universe. Given u and s, return x, a cell array containing one or more sets from s that exactly cover u. If no solution exists, return an empty cell array.
For simplicity, you may assume that all universes consist of integers and that all sets in s are subsets of the respective universes. Solutions may not be unique.
Example:
u = 1:7;
s = {[1 4 7] [1 4] [4 5 7] [3 5 6] [2 3 6 7] [2 7]};
x = {[1 4] [3 5 6] [2 7]}
Solution Stats
Problem Comments
-
1 Comment
Stefan Abendroth
on 21 Dec 2022
Tribute to Donald Knuth!
For those who are interested in his original paper: https://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/0011047.pdf
You can apply this algorithm in the IQpuzzler challenge: https://de.mathworks.com/matlabcentral/cody/problems/56548
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
Find the sum of all the numbers of the input vector
48758 Solvers
-
Remove all the words that end with "ain"
2275 Solvers
-
5133 Solvers
-
Numbers spiral diagonals (Part 1)
197 Solvers
-
83 Solvers
More from this Author45
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!