= Labyrinth = == Problem Description == Ravensburger's Labyrinth game deals with guiding an avatar through a dynamically changing labyrinth to certain fields. The labyrinth is represented by a quadratic board whose fields can (but do not have to) be connected in the four cardinal directions. The shape of the labyrinth changes over time as its rows and columns can be pushed either horizontally or vertically, which involves moving fields out of and into the board. To get to another field, in each turn, the avatar can follow paths that starting from the avatar's location traverse pairwisely connected fields. We here consider a variation of the original game in which: * The field of the labyrinth pushed out of the board (possibly hosting the avatar) immediately returns into the board (possibly with the avatar still residing on it) on the other end of the pushed row or column, respectively. * After a push, the avatar can move to any field reachable via a path in which every (non-terminal) field has a connection to its successor, and vice versa. (Note that there always is a path to a field the avatar already resides on.) * There is a unique starting and a unique goal field in the labyrinth. * A solution is represented by pushes of the labyrinth's rows and columns such that the avatar can from its starting field (which changes its location when pushed) reach the goal field (which also changes its location when pushed) by a move along some path after each push. * There is a maximum number of pushes, and the avatar must be able to reach the goal field (which can be relocated by pushes) by moving along some path after each push. The proposed variant of the Labyrinth game is a hard (presumably NP-complete) search problem. == Predicates == * '''Input''': {{{field/2, init_on/2, goal_on/2, connect/3, max_steps/1}}} * '''Output''': {{{push/3}}} == Input format == The fields of a quadratic NxN-labyrinth are provided by instances of predicate "field" as follows: {{{ field(1,1). field(1,2). ... field(1,N). field(2,1). field(2,2). ... field(2,N). ... field(N,1). field(N,2). ... field(N,N). }}} The starting and the goal field are specified by exactly one instance of "init_on" and exactly one instance of "goal_on": {{{ init_on(x_i,y_i). goal_on(x_g,y_g). }}} It always holds that 1 ≤ x_i,y_i,x_g,y_g ≤ N. The connections of fields are given by instances of "connect" looking as follows: {{{connect(x,y,d).}}} Again, we have 1 ≤ x,y ≤ N. Furthermore, direction d can be "n" for north, "s" for south, "e" for east, or "w" for west. Finally, the maximum number of pushes is determined by exactly one instance of "max_steps": {{{max_steps(m).}}} Argument m is a positive integer. An exemplary input for the above example looks as follows: {{{ field(1,1). ... field(1,4). .... field(4,1). ... field(4,4). init_on(3,2). goal_on(1,4). connect(1,1,s). connect(1,1,w). connect(1,2,n). connect(1,2,e). connect(1,2,w). connect(1,3,e). connect(1,4,n). connect(1,4,w). ... connect(4,4,w). max_steps(2). }}} == Output format == A solution (as described above) is represented by instances of "push": {{{push(z,d,s).}}} In an instance, direction d is one of "n" for north, "s" for south, "e" for east, or "w" for west, indicating that the row (if d="e" or d="w") or column (if d="n" or d="s") z is pushed into direction d. It must hold that 1 ≤ z ≤ N, where NxN is the board size. Furthermore, step number s expresses that the push happens after pushes 1,...,s-1 (and possible moves of the avatar along paths). The sequence of pushes is consecutive, that is, there are t instances of "push" for step numbers 1,...,t, where t ≤ m for maximum number m of pushes. Note that t < m (and even t = 0) is allowed, but the avatar must be able to reach the goal field by moves possible after the performed pushes. The two alternative solutions for our example above are represented as follows: Solution A: {{{ push(1,w,1). push(3,s,2).}}} Solution B: {{{ push(1,w,1). push(2,n,2).}}} == Example(s) == For illustration, consider the following labyrinth on a 4x4-board: {{attachment:labyrinth.gif}} We count rows x vertically from the bottom to the top, and columns y horizontally from the left to the right. The connections of the labyrinth's fields are indicated by lines from the center of a field to the field's border, each connection running in one of the four cardinal directions: "n" for north (upwards), "s" for south (downwards), "e" for east (rightwards), and "w" for west (leftwards). For instance, the field located at (1,3) has a single connection to the east, while the field at (3,4) has three connections running to the north, south, and west. Finally, the avatar is initially located at (3,2), and the goal is to reach the field at (1,4). Assuming a limit of two pushes, there are the following two solutions: === Solution A === The first solution is shown below, providing the initial setting (left part) along with the situations encountered after the first (center part) and second (right part) push. The pushes are indicated by arrows pointing to the pushed row or column, respectively: {{attachment:solutionA.gif}} The first step consists of pushing row 1 to the west. Observe that the field at (1,1) before the push reappears at (1,4) after the push, and also the goal field changes its location from (1,4) to (1,3). In the resulting labyrinth configuration, there are paths from the initial field, still at (3,2), to itself as well as to (4,2). The avatar can move to either one of these two fields to reach the goal field after the next push. (But recall that we are interested only in a sequence of pushes that admits reaching the goal field by some moves, but not in the moves themselves.) In the second step, we push column 3 to the south, so that the goal field reappears at (4,3), which can then be reached by a path both from (3,2) and (4,2). === Solution B === The second solution is presented in the same fashion as the previous one: {{attachment:solutionB.gif}} Again, the first step is to push row 1 to the west. (Afterwards, the avatar must move to the field at (4,2) to reach the goal after the second push, but this move does not belong to the solution.) In the second step, column 2 is pushed to the north, so that the field at (4,2) reappears at (1,2). From there, the avatar has a path to the goal field, which has been pushed to (1,3) before. Finally, note that the second push is necessary even if the field at (1,2) in the middle configuration had a connection to the south (touching the lower border of the board) because the legal moves of the avatar are along paths inside the board, not going out of and back into it. Hence, the transition from (4,2) to (1,2) can only be achieved by a second push, but not by any move. == Further Example(s) == Additional sample instances can be found under: [[https://www.mat.unical.it/aspcomp2013/files/samples/labyrinth-sample.zip|download]] == Problem Peculiarities == '''Type''': Search '''Competition''': System Track == Notes and updates == == Author(s) == * Authors: Carmine Dodaro, Giovambattista Ianni * Affiliation: University of Calabria, Italy * Original Author: Martin Gebser * Affiliation: University of Potsdam, Germany