Programming Problem #2
"Spatial Relationships"

A planning commission recently completed a population survey of several small counties. The population for each county is a unique positive integer (less than 2000), and all of the populations are stored in a two-dimensional matrix. The planning commission wants to use the matrix to divide the counties into two regions subject to the following constraints:
  1. Each county must be assigned to exactly one region.
  2. The total populations of the two regions must be equal. However, the number of counties does not have to be the same in each region.
  3. At least one path must exist from every county in a region to every other county in the same region, such that:
    1. The path consists only of counties in the same region.
    2. The path only passes through counties that are horizontally or vertically adjacent in the matrix.
Your job is to find all the possible ways that this subdivision can be performed.

The input consists of one or more matrices. Each matrix is represented by a line containing the number of rows m and columns n in the matrix, followed by m lines each containing n population values separated by spaces. A zero value for m or n signals the end of input. A matrix will have at most 16 elements. For each nonempty matrix, output a line of the form Matrix #i: s solution(s), where i is 1 for the first matrix, 2 for the second, etc, and s is the number of ways that the matrix can be subdivided. If s > 0, output each solution on a line by itself exactly as shown in the example below; list the populations in one region surrounded by parentheses, then the populations in the other region surrounded by parentheses. It doesn't matter in what order the regions or populations are listed.

Input must be read from the file "prob2.in", and output must be written to the file "prob2.out". All output to the screen will be ignored.

Example Input

<BOF>
4 4
50 85 9 33
301 46 40 19
105 29 11 12
20 13 23 16
2 3
3 5 12
4 1 30
3 4
16 11 91 14
77 55 82 23
31 10 18 72
0 3
<EOF>

Example Output

Matrix #1: 1 solution(s)
(301 105) (50 85 9 33 46 40 19 29 11 12 20 13 23 16)
Matrix #2: 0 solution(s)
Matrix #3: 2 solution(s)
(16 11 91 77 55) (14 82 23 31 10 18 72)
(82 23 18 72 55) (16 11 91 14 77 31 10)
A version of this problem originally appeared in the 1991 ACM Finals.

Dr. Eric Shade