TwiddleLab / Artificial Intelligence / Search, Games and Plans
Constraint Puzzles
What you will learn
- A constraint problem has variables (clubs, cells, countries), each with a domain of allowed values, and constraints between them.
- Propagation: every choice removes options from its neighbours; a cell with one option left is decided.
- Backtracking: try a value, go on, and at a dead end undo the last choice and try the next value.
- Timetables, sudoku and map colouring are the same kind of puzzle.
How the lesson goes
Five clubs, three rooms, two time slots, and everyone wants robotics. Can a computer find a schedule that works?
Bet first: each club can go in any of 6 places. How many schedules would a blind search have to try?
Make the club timetable. Broken rules light up at once.
Drag each club into a room and time. Drop on a club to swap.
Sudoku, 4 x 4. Each empty cell shows the digits it can still take.
Tap a digit to place it. Watch it vanish from the row, column and box.
These are constraint problems.
Each club, cell or country is a variable. Its allowed values are its domain. The rules are constraints. Crossing out options after each choice is propagation. Undoing a choice at a dead end and trying the next one is backtracking.
Colour the map with 3 colours, like a computer: try, check, back up.
Neighbours (joined by a line) must differ. Step, or Play.
The search is stuck. Which country has no colour left?
Tap it.
D borders B, C and F, which already use yellow, blue and red. D has an empty domain: a dead end. The search must undo the last choice (C) and try something else.
Your turn: paint the map with three colours.
In code this is graph colouring: countries are nodes, borders are edges.
Sudoku sprint: solve it with at most 2 mistakes.
Tap a cell, then a number. You can turn on the options.
A new rule arrived for your timetable. Fix it.
Move clubs until no rule is broken.
The new rule only limits Chess's room. Chess's time slot is already forced by Ana and Cat, so the fix is to change its room within that slot. Every other club can stay.
Previous lesson: Planning: From Goal to Steps · Next lesson: Project: Pathfinder Robot · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
