## Exercise ‹5›:

Sequence matching
Solve the following exercise by means of a reduction to SAT:
• Given an $n\times n$ board $M$ of $0$’s and $1$’s and an $n^2$-long sequence $S$ of $0$’s and $1$’s, determine if it is possible to find a path through adjacent cells of $M$, starting at its top-left cell and going through each of its cells exactly once, matching the sequence $S$.
The input of the exercise and the output with the solution (when the input is solvable) are as follows:
• M: array of array of int
S: array of int

The input contains the board as a matrix $M$ with $n$ rows and $n$ columns of $0$’s and $1$’s, and the sequence as an array $S$ with $n^2$ $0$’s and $1$’s. The top-left cell is the cell $(0,0)$.
• path: array of array of int

The output contains the details of the path. It is a two-dimensional matrix that must have size $n\times n$, with the position $(i,j)$ indicating the index in the path of the cell $(i,j)$, i.e., a value between $0$ and $n^2-1$. Thus, the position $(0,0)$ of path must always contain a $0$, since the path starts at the cell $(0,0)$.
Authors: Nil Mamano / Documentation:
 reduction { // Write here your reduction to SAT... } reconstruction { // Write here your solution reconstruction... } To be able to submit you need to either log in, register, or become a guest.