In this paper we propose an improved Harmony Search (HS) version inspired in the tonal variation of jazz musical improvisation. To evaluate our approach we considered two well-known problems, a Constraint Satisfaction Problem: Sudoku, and a Constraint Satisfaction Optimisation Problem: the Multidimensional Knapsack Problem (MKP). For each problem, we considered an existing baseline HS algorithm to implement our technique: the HS for Sudoku puzzles and, the Adaptive Binary HS for the MKP. The experiments showed that including tonal variation allows HS algorithms to find better quality solutions in both problems.Keywords. Author Keywords:Harmony search; Sudoku; metaheuristics; entropy KeyWords Plus:OPTIMIZATION ALGORITHM; PUZZLESRegular 2015FONDECYTFONDECYT