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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.