|
Size: 2965
Comment:
|
Size: 3019
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 5: | Line 5: |
| == Predicates == * '''Input''': row/1, col/1, maxRow/1, maxCol/1, entrance/2, exit/2, input_empty/2, input_wall/2 * '''Output''': empty/2, wall/2 |
|
| Line 6: | Line 12: |
* Input Predicates: row/1, col/1, maxRow/1, maxCol/1, entrance/2, exit/2, input_empty/2, input_wall/2 * Output Predicates: empty/2, wall/2 |
|
| Line 56: | Line 58: |
| Line 59: | Line 60: |
| == Authors == * Martin Brain * University of Bath, UK * Mario Alviano * University of Calabria, Italy |
== Author(s) == * Author: Martin Brain * Affiliation: University of Bath, UK * Author: Mario Alviano * Affiliation: University of Calabria, Italy |
Maze Generation
Contents
Predicates
Input: row/1, col/1, maxRow/1, maxCol/1, entrance/2, exit/2, input_empty/2, input_wall/2
Output: empty/2, wall/2
Problem Description
A maze is an M x N grid in which two distinct cells on the edges are indicated as entrance and exit and satisfying the following conditions:
- Each cell is empty or a wall.
- Each cell in an edge of the grid is a wall, except entrance and exit that are empty.
- There is no 2 x 2 square of empty cells or walls.
- If two walls are on a diagonal of a 2 x 2 square, then not both of their common neighbors are empty.
- No wall is completely surrounded by empty cells.
- There is a path from the entrance to every empty cell (a path is a finite sequence of cells, in which each cell is horizontally or vertically adjacent to the next cell in the sequence).
The problem has been defined by Martin Brain for the Second ASP Competition. NP-completeness of the decisional variant of the problem (given a partially filled grid G, can G be extended to a maze?) has been proved in the following paper:
* Mario Alviano, "The Maze Generation Problem is NP-complete", 11th Italian Conference on Theoretical Computer Science (ICTCS ’09). URL: http://archives.alviano.com/publications/2009/ictcs09-mazegeneration.pdf
where efficiently recognizable classes of unsatisfiable instances have also been identified (all instances that will be used for the 3rd ASP Competition do not belong to these classes).
Input format
A number of row facts, defining the rows in the grid. These are given as a range of consecutive, ascending integers, starting at 1. Instances of maxRow and maxCol are provided too.
A number of col facts, defining the columns in the grid. These are given as a range of consecutive, ascending integers, starting at 1.
One entrance fact, giving the column and row index of the entrance. This will be on the edges of the grid.
One exit fact, giving the column and row index of the exit. This will be on the edges of the grid.
One or more input_empty or input_wall statements, giving the column and row index of cells that are known to be empty of contain walls.
For example:
row(1). row(2). row(3). row(4). row(5). maxRow(5). col(1). col(2). col(3). col(4). col(5). maxCol(5). entrance(1,2). exit(5,4). input_wall(3,3). input_empty(3,4).
Output format
A wall or an empty fact for every square on the grid. Continuing the above example:
wall(1,1). empty(1,2). wall(1,3). wall(1,4). wall(1,5). wall(2,1). empty(2,2). empty(2,3). empty(2,4). wall(2,5). wall(3,1). wall(3,2). wall(3,3). empty(3,4). wall(3,5). wall(4,1). empty(4,2). empty(4,3). empty(4,4). wall(4,5). wall(5,1). wall(5,2). wall(5,3). empty(5,4). wall(5,5).
Example
Author(s)
- Author: Martin Brain
- Affiliation: University of Bath, UK
- Author: Mario Alviano
- Affiliation: University of Calabria, Italy