exact cover
- an exact cover S of X satifies two conditions:
- The intersection of any two distinct subsets in S is empty
- The union of the subsets in S* is X
- represent exact problem as a matrix:
- row = all subsets = possible solutions
- column = element of the cover = constraint of the problem
- an exact cover can be solved by Algorithm X:
- choose a column (deterministically)
- preferably with a column with less valid rows
- choose a row (nondeterministically)
- basically, guess between all the valid rows
- remove other rows that contains same cover as the chosen row
- repeat until no column can be chosen
- fail if a cover cannot be achieved
- Algorithm X can be implemented using dancing links:
- implement the matrix as doubly circular linked list
- each nodes are connected to all surounding nodes
- a special headers are included so that a entire column can be removed
- when removing nodes, two adjecent nodes are connected
- the removed nodes still retain the connection information
- limitation:
- all subsets needs to known?
- problem size? for sudoku
- col = 9 row * 9 number + 9 col * 9 number + 9 block * 9 number + 9 row * 9 col (cell has one number?)
- row = 9 row * 9 col* 9 number