Knuth's Algorithm X: Difference between revisions

Revision as of 18:09, 23 April 2006

Revision as of 03:13, 6 May 2006

Line 18:

Algorithm X functions as follows:

# Using any [[deterministic algorithm]], choose a column, c.

# Nondeterministically choosebranch, choosing any row, r, which has a 1 in column c, and add that row to the solution set.

# Remove any unselected rows which have a 1 in any column which r has a 1 in.

# Remove from the matrix any columns for which row r has a 1.