I'm following the great Wikipedia example of solving a simple "Exact Cover" problem using Knuth's "Dancing Links" DLX algorithm - example is here: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example
On the VERY LAST STEP they show the reduced matrix:
2 3 5 6
D 0 1 1 1
They state that this is a failed solution, but exactly how do we know that? Is it that it's down to one row, any single row? Or is it that the leftmost column has 0 and the right 3 columns have 1's? Or maybe it's down to 1 row and that row is not ENTIRELY 1's ?
Really trying to understand all this stuff (to eventually use with Pentominoes, even though I can download solutions from the web, but I want to code it myself for recreation and learning)
We declare failure if there exists an uncovered column X for which there are zero rows remaining that would cover it. The criterion of branching on the column with the least remaining rows that would cover it makes the existence of such a column easy to detect without much special logic.