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).
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).
A number of row facts, defining the rows in the grid. These are given as a range of consecutive, ascending integers, starting at 1.
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 empty or wall statements, giving the column and row index of cells that are known to be empty of contain walls.
row(1). row(2). row(3). row(4). row(5). col(1). col(2). col(3). col(4). col(5). entrance(1,2). exit(5,4). wall(3,3). empty(3,4).
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).
- Martin Brain
- University of Bath, UK
- Mario Alviano
- University of Calabria, Italy