<p>You are correct in that the algorithm iterates over all row that have a 1 in the selected column.</p>
<p>In the example it says</p>
<blockquote>
<p>Step 3—Rows A and B each have a 1 in column 1 and thus are selected (nondeterministically).</p>
</blockquote>
<p>What this is supposed to mean is that these rows are selected <strong>consecutively in a nondeterministic order</strong>.
More specifically, It first selects one row and then recurses with respect to that row (in the example row A). If the recursive call finds a feasible solution the entire algorithm terminates and the recursive call with respect to the other rows can be omitted. Only if no feasible solution is found in the recursive call (as is the case in the example) another recursive call is made with the next row (in the example row B).</p>

CC BY-SA 4.0
2024-10-08T13:31:43.993Z
2024-10-08T13:31:43.993Z
badboul
<p>I was perusing <a href="https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="nofollow noreferrer">the Wikipedia Page for Knuth's Algorithm X</a> and had a question about how it got the answer for it's example. In the algorithm's step 4, it mentions to choose nondeterministically a row R from the column C with the least 1s. However, in the example, it chooses two rows. Later on in the algorithm's steps, it recurses over a reduced matrix. In the example, Row A and Row B are both operated on in the full matrix. Is there a reason as to why the algorithm operates on both Row A and B with the full matrix? As in, does the algorithm iterate over all rows that are in column C and recurses over them independently?</p>

<exact-cover>
Explanation of Knuth's Algorithm X
Kevin Wu
# Explanation of Knuth's Algorithm X

(Asked by: username_0 on 2024-10-07)

I was perusing [the Wikipedia Page for Knuth's Algorithm X](https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X) and had a question about how it got the answer for it's example. In the algorithm's step 4, it mentions to choose nondeterministically a row R from the column C with the least 1s. However, in the example, it chooses two rows. Later on in the algorithm's steps, it recurses over a reduced matrix. In the example, Row A and Row B are both operated on in the full matrix. Is there a reason as to why the algorithm operates on both Row A and B with the full matrix? As in, does the algorithm iterate over all rows that are in column C and recurses over them independently?

**Tags:** exact-cover

---

## 1 answers

### Answer by username_1 on 2024-10-08. Score: 1 | Accepted answer

You are correct in that the algorithm iterates over all row that have a 1 in the selected column.

In the example it says

> Step 3—Rows A and B each have a 1 in column 1 and thus are selected (nondeterministically).

What this is supposed to mean is that these rows are selected **consecutively in a nondeterministic order**.
More specifically, It first selects one row and then recurses with respect to that row (in the example row A). If the recursive call finds a feasible solution the entire algorithm terminates and the recursive call with respect to the other rows can be omitted. Only if no feasible solution is found in the recursive call (as is the case in the example) another recursive call is made with the next row (in the example row B).


---

