The four tiles shown in Figure are used in Exercise. In this situation, tiles may not be f...

The four tiles shown in Figure are used in Exercise. In this situation, tiles may not be flipped or rotated when used to cover a given figure. For example, tile U will always have its dot in the up position.

Figure

Exercise

Figure can be covered in two different ways using U, D, R, L exactly once each. Use Algorithm X to prove this.

Figure

ALGORITHM X

Label the rows of the original matrix A and retain these labels throughout the application of the algorithm. Begin with M = A and L = { }.

Step 1 If M has a column of 0’s, then there is no solution, since by definition the rows representing an exact cover must together have 1’s in every position.

Step 2 Otherwise:

(a) Choose the column c of M with the fewest 1’s.

---

(b) Choose a row r with a 1 in column c, and place the number r in L.

---

(c) Eliminate any row r1 having the property (where 0 represents a row with all 0 entries).

---

(d) Eliminate all columns in which r has a 1.

---

(e) Eliminate row r.

---

(f) Let M be the resulting matrix and repeat steps 1 and 2.