Asparagus - Encoding Class Wire Routing

Class Tree	[Root] Puzzles (51) Grid (17) Wire Routing (1)
Description	A wire routing in a n x n grid consists of finding routes for w wires given their start and end points (terminals). The constraints are as follows: 1. No grid edge is used by more than one wire 2. Some grid points allow for two wires to cross; all other points can be used by at most one wire 3. Some areas of the grid are blocked - they cannot be "touched" by any wire Input format Input data are stored in plain text files, one file for each instance. The format of the file is as follows: 1. The file starts with lines that define wires. Wires are defined using predicate name "wires". They are represented as integers that always start from 1 and end at w, where w is the number of the wires. 2. The definition of the n x n grid is given by the predicate "range". Predicate range has one parameter. Intuitively, range(v) means that v is a legal value for the x- and y- coordinates. That predicate specifies consecutive integers from1 to n. 3. The terminals for each wire are given by the predicate "terminal". Intuitively terminal(x, y, w) implies that (x, y) is a terminal grid point for the wire w. There are two terminals for each wire (Comment: but an interesting variant of the problem is to allow more terminal points. Wires should then be understood as trees not paths.) 4. The definition of a blocked grid point is given by the predicate "block" which takes two parameters. Intuitively block(x, y) means the grid point (x, y) does not allow a wire to pass through it. 5. The file ends with predicates with the name "allow" that define the special points in the grid that allow up to two wires to pass through them. Intuitively allow(x, y) means that at most two wires can pass through the grid point (x, y). Output Requirement The programmers must ensure that, in the answer-sets, predicate "path(x, y, w)" is used to imply that wire w passes through the grid point (x, y) of the n x n grid. Example wire(1). wire(2). pt(1). pt(2). pt(3). pt(4). pt(5). terminal(3,1,1). terminal(2,1,2). terminal(2,5,1). terminal(3,5,2). block(1,5). block(4,5). allow(2,3). allow(5,4). allow(1,4). allow(3,3). allow(3,2). The figure below uses circles to represent the special grid points that allow up to 2 wires to pass through them, cross to represent the points that are blocked, and dot to represent the terminal grid points of the two. Valid output: path(3,5,2). path(2,5,1). path(2,1,2). path(3,1,1). path(2,4,1). path(3,2,1). path(3,4,2). path(2,2,2). path(2,3,1). path(3,3,1). path(3,2,2). path(4,2,2). path(4,3,2). path(4,4,2). The figure below uses dots labeled with either "1" or "2" to represent the grid points associated with the wires. Authors: Gayathri Namasivayam and Miroslaw Truszczynski Affiliation: University of Kentucky
Encodings 1 - 1 of 1	wire-routing_decision.gringo un-/mark all

Class Tree

[Root]
- Puzzles (51)
  - Grid (17)
    - Wire Routing (1)

Description

A wire routing in a n x n grid consists of finding routes for w wires given their start and end points (terminals). The constraints are as follows:

1. No grid edge is used by more than one wire
2. Some grid points allow for two wires to cross; all other points can be used by at most one wire
3. Some areas of the grid are blocked - they cannot be "touched" by any wire

Input format

Input data are stored in plain text files, one file for each instance. The format of the file is as follows:

1. The file starts with lines that define wires. Wires are defined using predicate name "wires". They are represented as integers that always start from 1 and end at w, where w is the number of the wires.

2. The definition of the n x n grid is given by the predicate "range". Predicate range has one parameter. Intuitively, range(v) means that v is a legal value for the x- and y- coordinates. That predicate specifies consecutive integers from1 to n.

3. The terminals for each wire are given by the predicate "terminal". Intuitively terminal(x, y, w) implies that (x, y) is a terminal grid point for the wire w. There are two terminals for each wire (Comment: but an interesting variant of the problem is to allow more terminal points. Wires should then be understood as trees not paths.)

4. The definition of a blocked grid point is given by the predicate "block" which takes two parameters. Intuitively block(x, y) means the grid point (x, y) does not allow a wire to pass through it.

5. The file ends with predicates with the name "allow" that define the special points in the grid that allow up to two wires to pass through them. Intuitively allow(x, y) means that at most two wires can pass through the grid point (x, y).

Output Requirement

The programmers must ensure that, in the answer-sets, predicate "path(x, y, w)" is used to imply that wire w passes through the grid point (x, y) of the n x n grid.

Example

wire(1). wire(2). pt(1). pt(2). pt(3). pt(4). pt(5). terminal(3,1,1). terminal(2,1,2). terminal(2,5,1). terminal(3,5,2). block(1,5). block(4,5). allow(2,3). allow(5,4). allow(1,4). allow(3,3). allow(3,2).

The figure below uses circles to represent the special grid points that allow up to 2 wires to pass through them, cross to represent the points that are blocked, and dot to represent the terminal grid points of the two.

Valid output:

path(3,5,2). path(2,5,1). path(2,1,2). path(3,1,1). path(2,4,1). path(3,2,1). path(3,4,2). path(2,2,2). path(2,3,1). path(3,3,1). path(3,2,2). path(4,2,2). path(4,3,2). path(4,4,2).

The figure below uses dots labeled with either "1" or "2" to represent the grid points associated with the wires.

Authors: Gayathri Namasivayam and Miroslaw Truszczynski
Affiliation: University of Kentucky

Encodings
1 - 1 of 1

Actions

Navigation