| 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 |
|
| Instances 1 - 20 of 50 |
|
Expand All
Collapse All
