| pjt33
| Joined: 17 Sep 2005 | Posts: 1 | : | | Items |
|
Posted: Sat Sep 17, 2005 3:24 pm Post subject: |
|
|
dukuso wrote: | I can't modify my solver for these.
No exact cover problem with sums.
Can't see how to convert it into a SAT-problem either. | I think the easiest thing to do would be to convert it to exact multiset cover. Shouldn't be too hard to modify Dancing Links.
Incidentally there are (at least) two ways of converting it to exact set cover.
1. Each row represents a solution to a sum group.
2. Extend the universal set for each sum group S of sum |S| to have |S| elements. Instead of 1 cell/value row, you have (|S| - value + 1) rows for that cell/value pair (where S is the sum group containing the cell), with entries for the corresponding additional elements of (1 ... 1 0 ... 0), (0 1 ... 1 0 ... 0), (0 0 1 ... 1 0 ... 0), ..., (0 ... 0 1 ... 1 0), (0 ... 0 1 ... 1). |
|