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)$.