Instance Class Maze Generation

Class Tree
Description Description
===========

A maze is a 2 dimensional grid in which each cell either contains a wall or is empty. There are two (distinct) empty squares on the edge of the grid, known as the entrance and the exit. A path is a finite sequence of cells, in which each distinct cell appears at most once and each cell is horizontally or vertically adjacent to the next cell in the sequence. The maze must meet the following criteria:

1. There must be a path from the entrance to every empty cell (including the exit).

2. If a cell is on any of the edges of the grid, and is not an entrance or an exit, it must contain a wall.

3. There must be no 2x2 blocks of empty cells or walls.

4. No wall can be completely surrounded by empty cells.

5. If two walls are diagonally adjacent then one or other of their common neighbours must be a wall.

Input
-----

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.

For example:

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

Output
------

The initial entrance and exit facts and 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)


Calibration
-----------

Calibration was performed on a 1.8 Ghz Pentium M with the following command line:

./instanceGenerator.pl --width=$W --height=$H | cat - maze-gen.lp | gringo-2.0.2 | /usr/bin/time -v clasp-1.1.3 1 | ./parseMaze.pl

W H Time
10 10 3 seconds
11 11 3 seconds
12 12 28 seconds
13 13 9 seconds
14 14 > 10 minutes
15 15 19 seconds
17 17 51 seconds
19 19 231 seconds

Suggested competition set - 14x14, 16x16, 17x17, 19x19, 21x21

Note that even sized mazes are unsatisfiable and that odd sized mazes are mostly satisfiable. Increasing the density should make the problem easier.

Author: Martin Brain
Submitter Martin Gebser
Compatible Encodings
Output Predicates
  • col/1
  • empty/2
  • entrance/2
  • exit/2
  • row/1
  • wall/2
Instances
1 - 20 of 50