Exercise 11 | RACSO

Exercise _‹11_›:

Grid exploration

Solve the following exercise by means of a reduction to SAT:

Given a grid made of walkable cells and walls, and a walkable cell

s

, find a path from

s

and through adjacent cells such that every walkable cell is visited at least once. The path must not contain more than

k

cells. The ending point of the path does not matter.

For instance, for the grid

     ·   #   ·   #   #

     ·   ·   ·   ·   ·

     ·   #   ·   #   ·

     ·   ·   ·   ·   ·

     #   #   ·   #   s

in which walkable cells have been indicated with . or s and walls with #, the following path

     ·   #   ·   #   #

     ·   ·   ·   ·   ·

     ·   #   ·   #   ·

     ·   ·   · ← · ← ·
             ↓       ↑
     #   #   ·   #   s

     ·   #   ·   #   #

     ·   ·   ·   ·   ·

     ·   #   ·   #   ·
             ↑
     ·   ·   o   o   o
             ↑
     #   #   o   #   o

     ·   #   ·   #   #
     ↑
     ·   ·   ·   ·   ·
     ↑
     ·   #   o   #   ·
     ↑       ↓
     · ← · ← o   o   o

     #   #   o   #   o

     o   #   ·   #   #
     ↓       ↑
     o → · → ·   ·   ·

     o   #   o   #   ·

     o   o   o   o   o

     #   #   o   #   o

     o   #   o   #   #
             ↓
     o   o   o → · → ·
                     ↓
     o   #   o   #   ·

     o   o   o   o   o

     #   #   o   #   o

     o   #   o   #   #

     o   o   o   o   o

     o   #   o   #   o

     o   o   o   o   o

     #   #   o   #   o

visits all walkable cells, and has

21

cells (note that the initial

s

in the path is also counted; visited cells are indicated with o).

The input of the exercise and the output with the solution (when the input is solvable) are as follows:

```
grid: array of array of int
k: int
s: struct {
   r: int
   c: int
}
```
The input has the matrix grid, the maximum number $k$ of cells in the path (counting $s$ ), and the initial cell $s$ . The grid contains the locations of the walls: grid[i][j] has a $0$ to denote that cell $(i,j)$ is walkable, and a $1$ to denote that the cell has a wall. The starting cell $s$ is a struct with two fields: r indicates the row, and c indicates the column. For instance, in the previous example we would have s.r ${} = {}$ s.c ${} = 4$ . It is guaranteed that every walkable cell is reachable from the cell $s$ .
```
path: array of struct {
   r: int
   c: int
}
```
The output consists of an array of variable length, containing the sequence of cells that form the path. Each element in the path is a struct with a pair of numbers r and c, with the same meaning as in s. The $0$ ’th element of the array must be s.

Authors: Nil Mamano / Documentation:

Exercise ‹11›:

Exercise _‹11_›: