I'm writing a course describing several topics of Artificial Intelligence. Currently I'm working on the "Constraint Processing" part. To illustrate constraint processing I would like to include a simple example. This examples should have the following qualities:
- I want to draw an OR-tree so the example can't have that much variables and options
- Illustrating node consistency, backtracking, backjumping, backmarking, weak relaxation and arc consistency. (The examples should illustrate that these methods make sense and add some value to constraint processing).
- Easy to understand and represent. (Not a two page long array of constraints).
I have browsed the web for some time, but all examples by now don't meet these qualities. (I've also tried to simplify existing problems).
Are there any typical exampes to illustrate these methods/techniques? Giving two different examples and distribute the techniques between these two examples wouldn't be a problem too.
The Traveling Tournament Problem might fit some of your requirements. It's NP hard and doesn't have much variables and options:
Official page
Problem statement