﻿Given the universe U = {1, 2, 3, 4, 5, 6, 7, 8, 9} and the collection of sets:
S1 = {1, 2, 3}, S2 = {4, 5, 6}, S3 = {7, 8, 9},
S4 = {1, 4, 7}, S5 = {2, 5, 8}, S6 = {3, 6, 9},
S7 = {1, 5, 9}, S8 = {2, 6, 7}, S9 = {3, 4, 8}

Find ALL exact covers of U (subcollections where every element of U appears in exactly one selected set). Implement the search using Knuth's Algorithm X with dancing links. Include a self-contained test that verifies each solution covers U exactly once.
