Constraint Propagation

• Sudoku is typically solved by constraint propagation.
• That's true for machines and people.
• How do you propagate a constraint?
• A Sudoku problem already has some of the values filled in.
• You don't know the values of the others, but you do know that they're 1-9.
• Can you reduce that range?
• Can you reduce it so much that you know the value?
• In some of the cells, you can.
• You look at all the constraints, and can tell the value.
• What mechanisms do you have for solving a Sudoku puzzle? Sudoku Game.
• Constraint Propagation is a type of inference. You're inferring new values or a reduced set of values based on the old values and constraints.