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
The input of the exercise and the output with the solution (when the input is
solvable) are as follows:
: this problem can be solved in asymptotic polynomial time without reducing to SAT.