welcome: please sign in
location: FinalProblemDescriptions / Numberlink

Numberlink Puzzles

Problem Description

Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid. The player has to pair up all the matching numbers on the grid with single continuous lines (or paths). The lines cannot branch off or cross over each other, and the numbers have to fall at the end of each line (i.e., not in the middle).

The rule of Numberlink is also described in the following Web pages.

Here, the puzzle is defined in a more general setting.

An undirected graph G(V,E) and a list of connections are given. Each connection consists of two terminal nodes and an index number.

The goal of the puzzle is to find a list of paths connecting two terminal nodes for each connection such that no node is included in more than two paths.

Predicates

Input format

An undirected graph G is represented by the predicates node/1 and edge/3.

A predicate "node(v)" is added for each node in G where v is an atom representing the name of the node. The followings are examples.

A predicate "edge(e,u,v)" is added for each edge {u,v} in G where e is an atom representing the name of the edge, and u and v are the node names (u != v). The followings are examples.

Please note that only one edge predicate is added for each edge in G.

A connection is represented by a predicate "connection(i,u,v)" where i is an index number and u and v are node names (u != v). The followings are examples.

  connection(1, v1, v2).
  connection(2, v3, v4).

Instances are taken from the following web page.

Thanks to the corresponding authors of the puzzle instances.

Output format

The output should be given by the unary predicate "link(e)" where e is an edge name given in the input.

Of course, the output must represent a solution, that is, the following "connected(u,v,[],path)" should succeed for any "connection(i,u,v)" in the input and the nodes occurred in the paths are all distinct.

  connected(U, U, Path, Path).
  connected(U, V, Path0, Path) :- adj(U, W), \+ member(W, Path0), connected(W, V, [W|Path0], Path).

  adj(U, V) :- (edge(E, U, V); edge(E, V, U)), link(E).

Example(s)

Puzzle instances can be found in the following web pages.

Author(s)

ASP Competition 2011: FinalProblemDescriptions/Numberlink (last edited 2011-01-20 14:21:15 by CarmenSantoro)