Exercise 10:

Ukelele song
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: Note: this problem can be solved in asymptotic polynomial time without reducing to SAT.
Authors: Nil Mamano / Documentation:
To be able to submit you need to either log in, register or become a guest.