What is a successor function (in CSPs)?

Question

In Constraint Satisfaction Problems (CSPs), a state is any data structure that supports

• a successor function,
• a heuristic function, and
• a goal test.

In this context, what is a successor function?

Answer 1

A successor function is a function that generates a next state from the current state, plus the choices that affect state changes. In e.g. the 8 queens problem, a state might be the location of 5 queens so far, the choice might be where to put the next queen, and the successor function would return the resulting state with 6 queens on the board.

Typically a solver will store/cache a current state, make a choice, and use the successor function to discover what the next state is. Then it may call the heuristic function on the next state and make a decision whether to continue that search deeper into the search tree (or recursion) or try another choice at the current state.