1 Regular Exact Cover problem Use backtracking to solve the following exact cover problem, that is: is there a set of rows containing exactly one 1 in each column? We use the following recursive procedure, where A is a Boolean matrix, and S is the solution set of rows: ExACTCoVER(A, S) 1 3 5 if A is empty if A has a 0 column Select column c with least number of 1s return Success return Fail 6 for each row r such that A[r,c]--1 Add row r to solution S Cover all columns that are selected by row r, as well as all rows that conflict with r Recursively search reduced matrix A ExACTCoVER(A) /l Partial solutions that include row r have been explored: // backtracking before trying another row Restore previously deleted rows and columns Remove row r from solution S 10 Solutions obtained by selecting column c have been explored backtracking before trying another column 12 Restore column c in matrix A C1 C2 C3 C4 Cs 6 C7 C1 2 C3 4 C5 C6C7 C1 C2 C3 C4 Cs C7 r 0 0 1 0 0 1 r20 0 1 0 0 0 r 00 0 1 0 1 1 00 01 0 1 0 r0 01 0 1 0 01 0 r 01 0 0 0 0 1 c1 C2 C3 C4 cs C6 C7 C1 C2 C3 C4 cs C6 C7 r 00 0 1 0 1 1 Regular Exact Cover problem Use backtracking to solve the following exact cover problem, that is: is there a set of rows containing exactly one 1 in each column? We use the following recursive procedure, where A is a Boolean matrix, and S is the solution set of rows: ExACTCoVER(A, S) 1 3 5 if A is empty if A has a 0 column Select column c with least number of 1s return Success return Fail 6 for each row r such that A[r,c]--1 Add row r to solution S Cover all columns that are selected by row r, as well as all rows that conflict with r Recursively search reduced matrix A ExACTCoVER(A) /l Partial solutions that include row r have been explored: // backtracking before trying another row Restore previously deleted rows and columns Remove row r from solution S 10 Solutions obtained by selecting column c have been explored backtracking before trying another column 12 Restore column c in matrix A C1 C2 C3 C4 Cs 6 C7 C1 2 C3 4 C5 C6C7 C1 C2 C3 C4 Cs C7 r 0 0 1 0 0 1 r20 0 1 0 0 0 r 00 0 1 0 1 1 00 01 0 1 0 r0 01 0 1 0 01 0 r 01 0 0 0 0 1 c1 C2 C3 C4 cs C6 C7 C1 C2 C3 C4 cs C6 C7 r 00 0 1 0 1