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 walls have been indicated with a #, the following path

    1)                       2)                       3)

    ·   #   ·   #   #        ·   #   ·   #   #        ·   #   ·   #   #
                                                      ^
    ·   ·   ·   ·   ·        ·   ·   ·   ·   ·        ·   ·   ·   ·   ·
                                                      ^
    ·   #   ·   #   ·        ·   #   ·   #   ·        ·   #   o   #   ·
                                     ^                ^       v
    ·   ·   · < · < ·        ·   ·   o   o   o        · < · < o   o   o
            v       ^                ^
    #   #   ·   #   s        #   #   o   #   o        #   #   o   #   o



    4)                       5)                       6)

    o   #   ·   #   #        o   #   o   #   #        o   #   o   #   #
    v       ^                        v
    o > · > ·   ·   ·        o   o   o > · > ·        o   o   o   o   o
                                             v
    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).

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_›: