» ASP Competition | |
|
Generalized SlitherlinkProblem description The input is an undirected graph G=(V,E) and a partial function
f: 2E→ N (N are the natural numbers, including 0), an assignment of
numbers to some subsets of edges (called cells). The task is to find a
subgraph S=(V,E') of G such that S is a circle (without node
repetitions) and for each E''⊆ E such that f(E'') is defined, |E''∩ E'|=f(E'') holds (that is, the cardinality of cell edges that
are in the subgraph S should be equal to the number assigned by f).
This problem extends the Slitherlink puzzles by Nikoli, see http://en.wikipedia.org/wiki/Slitherlink. In the Nikoli puzzles, the graph is a square grid and numbers are
assigned to sets of exactly four edges, which form a square. The
subgraph is created by drawing a lines on the chosen edges such that it forms a closed circle and such that the numbers of lines around a cell matches the assigned number (if it exists). Input formatThe undirected input graph G = (V,E) is given by instances of "edge" representing the set E, for example Note that this representation is not symmetric, i.e. for example
edge(0,1) will not be part of the input. This is also important for the output. The set of nodes V is represented implicitly and consists of all nodes that occur in an edge. The example above thus represents the graph ({0,1,2},{(0,1),(2,1)}). In this case the edges (0,1) and (2,1) belong to a cell identified by "c0". Note that the edges appear as in their definition above (and not
as (1,0), for example).
The function value is then represented by the predicate "clue". For states that f(c0)=1, where c0 is the set of edges identified by c0. One can assume that the number of the second argument is positive and not larger than the cardinality of the cell. Output FormatThe output should be given by the binary predicate link(v1,v2) where edge(v1,v2) has been in the input (in particular, edge(v2,v1) should not have been in the input). The output facts represent the solution subgraph. Author: Wolfgang Faber |