Encoding Class FindingNumbers

Class Tree
Description In this problem the input is a square made of numbers and you have to
find a set of numbers that are hidden in it. The numbers may be there
horizontally or vertically and in both directions.

For example, given the square:

0 2 5
3 1 6
7 2 5

And the numbers: 613, 212, and 730, the correct answer would be that:

613 starts at square (3, 2) and goes to left
212 starts at (2, 3) to down.
730 starts at (1, 1) to up.

The input instances are given as the set of facts:

grid(x, y, d). -- the grid square (x, y) contains the number d.
number(n, i, d). -- the ith digit of the nth number is d.

The above example would be represented as:

grid(1,3,0). grid(2,3,2). grid(3,3,5).
grid(1,2,3). grid(2,2,1). grid(3,2,6).
grid(1,1,7). grid(2,1,2). grid(3,1,5).

number(1,0,6). number(1,1,1). number(1,2,3).
number(2,0,2). number(2,1,2). number(2,2,2).
number(3,0,7). number(3,1,3). number(3,2,0).


- The size of the square. In the benchmarks this ranges from 3x3 up
to 70x70.

- Length of the numbers. This ranges from n-2 to n where n is the
square size.

- Amount of numbers to find. This ranges from 60% to 100% of all
possible strings of a given length in the square.

- Number of different symbols in the square. All examples are
generated randomly with an alphabet of 8 different digits.
However, some of the small benchmarks may not contain all of them.

The instance files are named using the schema:


In general, the problem goes more difficult when the parameters
increase. However, when the number of strings to find increases the
problem may become easier since the solution is more constrained.
1 - 2 of 2