A computational problem of interest in the music field is how to lay out the notes of a song in the fretboard of a string instrument, like a guitar, in a way that certain criteria are optimized. These criteria can be heuristics that estimate the playing ease. For instance, “consecutive notes should not be very far away in the fretboard”, “chords should have ergonomic positions for the hand”, and so on. Here, we consider a very simple variant. Solve the following exercise by means of a reduction to SAT:

• Determine if a song can be played in an ukelele in a way that is easy, according to the criteria detailed below. A song is a sequence of single notes (or, more precisely, pitches, since we want to distinguish between notes in different octaves).
  
  
  An ukelele has 4 strings, each of which has 12 frets. A string can be played open, without pressing the string against any fret, or at any of the 12 frets. Each combination of string and fret, called a position, produces a pitch. The open string is considered the fret 0, yielding a total of 52 positions. However, many of them correspond to the same pitch. It is for this reason that there may be more than one way to play the same song, with different degrees of difficulty. In fact, there are only 21 different pitches; if we identify them from lowest to highest, then the pitches found in each position are:

                                     Frets
               0   1   2   3   4   5   6   7   8   9  10  11  12
     Strings ---------------------------------------------------
          1  | 9  10  11  12  13  14  15  16  17  18  19  20  21
          2  | 4   5   6   7   8   9  10  11  12  13  14  15  16
          3  | 0   1   2   3   4   5   6   7   8   9  10  11  12
          4  | 7   8   9  10  11  12  13  14  15  16  17  18  19
  

  In particular, the lowest pitch corresponds to the third string open, whereas the highest pitch corresponds to the first string, twelfth fret. Note that, for example, the pitch 10 can be played in 4 different positions.
  
  
  In this problem, we are given a sequence of pitches (numbers between 0 and 21) and must assign a string (a number between 1 and 4) and a fret (a number between 0 and 12) to each one. One such assignment determines a way to play the song. We say that a way to play a song is easy if of any two consecutive positions are in the same string or adjacent strings, and no further than 2 frets away. Thus, for instance, after playing the string 2 on the fret 6, the next position must be in the string 1, 2, or 3, and between the frets 4 and 8. However, this only applies when both of the positions are not open. Open positions are easier to play because they do not require to press any fret, and thus we allow them without any constraint with the previous or following positions.

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

• pitches: array of int
  

  The input is an array of pitch identifiers (numbers between $0$ and $21$) describing a song.

• assignments: array of struct {
     string: int
     fret: int
  }
  

  The output consists of an array assignments of the same length of the input. Each of its elements is a struct with two fields: string is the string assigned to the $i$’th note of the input (a number between $1$ and $4$) and fret is the assigned fret (a number between $0$ and $12$).

Note: this problem can be solved in asymptotic polynomial time without reducing to SAT.