# Encoding Class Maze Generation

Class Tree [Root]    Puzzles (51)    Grid (17)    Maze Generation (2) 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) Author: Martin Brain maze-generation_decision.gringo   un-/mark all