Generalized Slitherlink

Problem Description

The input is an undirected graph G=(V,E) and a partial function f: 2^E → 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).

Instances will consist of graphs similar to the ones found on http://www.krazydad.com/slitherlink (Altair, Laves, Penrose, Snowflake). Credits are due to Jim Bumgardner, author of that site for supplying software for generating instances.

Input format

The undirected input graph G = (V,E) is given by instances of edge/2 representing the set E, for example

edge(0,1). edge(2,1).

Note that this representation is not symmetric, i.e. for the example above, edge(1,0) will not be part of the input. This is also important for the output, as described below. 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)}).

The function f will be represented by two predicates, cell_contains/3 and clue/2. cell_contains/3 defines the sets on which f is defined. Each of these sets (called cells) will have a unique identifier. Each fact then consists of a cell identifier and an edge which the cell contains, for example

cell_contains(c0,0,1). cell_contains(c0,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 example

clue(c0,1).

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 format

The output should be given by the binary predicate link/2 specifying link(v1,v2) when edge(v1,v2) has been in the input (in particular, link(v2,v1) should not be in the output). The output facts represent the solution subgraph E'.

Example

Author(s)

Author: Wolfgang Faber
Affiliation: University of Calabria, Italy