welcome: please sign in
location: Diff for "FinalProblemDescriptions/MazeGeneration"
Differences between revisions 1 and 7 (spanning 6 versions)
⇤ ← Revision 1 as of 2011-01-18 14:57:26 →
Size: 2958
Editor: CarmenSantoro
Comment:
← Revision 7 as of 2011-02-02 19:34:10 → ⇥
Size: 3198
Editor: MarioAlviano
Comment:
Deletions are marked like this. Additions are marked like this.
Line 7: Line 7:
* Input Predicates: row/1, col/1, maxRow/1, maxCol/1, entrance/2, exit/2, input_empty/2, input_wall/2 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:
Line 9: Line 9:
* Output Predicates: empty/2, wall/2  1. Each cell is empty or a wall.
Line 11: Line 11:
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:  2. Each cell in an edge of the grid is a wall, except entrance and exit that are empty.
Line 13: Line 13:
1. Each cell is empty or a wall.  3. There is no 2 x 2 square of empty cells or walls.
Line 15: Line 15:
2. Each cell in an edge of the grid is a wall, except entrance and exit that are empty.  4. If two walls are on a diagonal of a 2 x 2 square, then not both of their common neighbors are empty.
Line 17: Line 17:
3. There is no 2 x 2 square of empty cells or walls.  5. No wall is completely surrounded by empty cells.
Line 19: Line 19:
4. If two walls are on a diagonal of a 2 x 2 square, then not both of their common neighbors are empty.

5. No wall is completely surrounded by empty cells.

6. 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).		  6. 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).
Line 27: Line 23:
* 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  * 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
Line 30: Line 26:

== 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 43: Line 45:
For example: == Output format ==
Line 45: Line 47:
A wall or an empty fact for every square on the grid.

== Example(s) ==

INPUT
{{{
Line 49: Line 57:
}}}
Line 50: Line 59:
== Output format == OUTPUT
{{{
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).
}}}
Line 52: Line 66:
A wall or an empty fact for every square on the grid. Continuing the above example: == Notes and updates ==
Line 54: Line 68:
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). In this year's edition, instances belonging to trivial polynomial subcases (mazes of m x n size with m and n both even) will not be included.
Line 56: Line 70:

== Example ==

== 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

  1. Maze Generation
    1. Problem Description
    2. Predicates
    3. Input format
    4. Output format
    5. Example(s)
    6. Notes and updates
    7. Author(s)

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:

  1. Each cell is empty or a wall.
  2. Each cell in an edge of the grid is a wall, except entrance and exit that are empty.
  3. There is no 2 x 2 square of empty cells or walls.
  4. If two walls are on a diagonal of a 2 x 2 square, then not both of their common neighbors are empty.
  5. No wall is completely surrounded by empty cells.
  6. 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:

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).

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

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.

Output format

A wall or an empty fact for every square on the grid.

Example(s)

INPUT 

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 

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).

Notes and updates

In this year's edition, instances belonging to trivial polynomial subcases (mazes of m x n size with m and n both even) will not be included.

Author(s)

  • Author: Martin Brain
    • Affiliation: University of Bath, UK
  • Author: Mario Alviano
    • Affiliation: University of Calabria, Italy

ASP Competition 2011: FinalProblemDescriptions/MazeGeneration (last edited 2011-02-02 19:34:10 by MarioAlviano)