Local Search and Backtracking vs Non-Systematic Backtracking

This paper addresses the following question: what is the essential difference between stochastic local search (LS) and systematic backtracking (BT) that gives LS superior sealability? One possibility is LS’s lack of firm commitment to any variable assignment. Three BT algorithms are modified to have this feature by introducing randomness into the choice of backtracking variable: a forward checker for n-queens, the DSATUR graph colouring algorithm, and a Davis-Logemann-Loveland procedure for satisfiability. In each case the modified algorithm scales like LS and sometimes gives better results. It is argued that randomised backtracking is a form of local search.