Maze Generation

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:

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

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