I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-queens puzzle to illustrate the algorithm working, he stated that in it a queen can only move one row up or down, so for example in a column with the following configuration:
In the first iteration the queen can only move to either rows 4 or 6 (8 rows, 0-based index), then in the next iteration it would be stuck in a local maxima because neither row 3 nor 7 have values lower than 14, so the algorithm would then proceed to the next column or terminate. He argued that even tough a queen can legally move directly through all the rows of its column doing so would make the algorithm fall of the concept of "Local search", because a local search move is limited to only one of its closest neighboors per time/iteration.
I found this weird because it appears to me that such a limitation greatly reduces the usefulness of hill climbing (in the 8-queen problem it makes the success rate abysmal). So I would like to know what's the correct/formal definition of local search and hill climbing, should it always be constrained to the closest neighboor? what constitute a closest neighboor? I would especially appreciate some book references.