   2012 ACM ICPC South Central USA Regional Programming Contest

## 8 - Golumb Cages

A Golomb Ruler is a set of integers in which all differences (e.g. |a-b|) are unique integers. The Atlantean game extends the Golomb Ruler to include sums, products, and quotients where all results are positive integers. The set {2,8,10,11} is an Atlantean Golomb Ruler that also satisfies the constraints of addition, multiplication, and division. E.g. the numbers 2 and 10 from this set produce the results 12, 8, 20, and 5 on the operations +, -, *, and /, respectively. No other pair of numbers from the set will produce these results.

Given an NxN puzzle grid subdivided into cages with a result for each cage, determine the positioning of the numbers from the set so that each row and column contain every number from the set exactly once, and each cage resolves to the result for that cage on one of the four operations of addition, subtraction, multiplication, or division. The operand will not be given.

Sample puzzle on the set {2, 8, 10, 11} Resolves to this: ### Input:

Grid Size
Number Set
Number of cages
Result, grid location 1, grid location 2 (repeated for each individual cage)

The first grid location is at row 0 and column 0 (0,0).
Grid size will be either 4 (4x4), or 6 (6x6).
The number set will be in ascending order and will only consist of positive integers greater than 1 and less than 100.
Cage size is restricted to 2, hence there will be two grid locations per cage.
A grid size of 0 will signify the end of data.

### Output:

Output will be the entire grid. Numbers on the grid must be a 2 digit format with a single space between each number and a blank line between solution grids.

```4
02 08 10 11
8
16 0 0 1 0
22 0 1 1 1
80 0 2 0 3
110 1 2 1 3
2 2 0 2 1
4 2 2 3 2
9 2 3 3 3
1 3 0 3 1
0
```

### SAMPLE OUTPUT:

```02 11 10 08
08 02 11 10
10 08 02 11
11 10 08 02
```