A method for solving a constraint satisfaction problem (CSP) includes choosing a first state corresponding to a first set of values of a set of variables, and selecting a hop distance within a state space of the variables responsively to a random distance selection criterion. A second state corresponding to a second set of the values of the variables is selected, such that the second state is separated from the first state by the hop distance. Constraint costs of the first and second states are compared. If the cost of the second state is lower than the cost of the first state, the first state is redefined to correspond to the second set of the values of the variables. These steps are repeated until a solution of the CSP is found.