Constraint satisfaction problems are closely related to optimization problems. The space of possible solutions to a constraint satisfaction problem is typically defined by a set of decision variables (e.g. the squares to be filled in Sudoku). The task is to find some particular assignment to these variables that will meet a predefined set of constraints.

Optimization problems are similar in that they often also involve constraints that a solution needs to satisfy, but in addition to that, there is also a criterion to be minimized or maximized. Creating a school’s timetable could be viewed as a constraint satisfaction problem: you need to assign teachers, students to time slots and classrooms. If you also have other other goals such as minimizing the number of blank slots in between classes during which students have to wait for their next class to start, that would turn the constraint satisfaction problem into an optimization problem with constraints. The resulting timetable would still have to meet constraints to be valid, but there would now be a notion of a better or a worse valid timetable.

Interestingly, there are ways to use optimization methods to solve constraint satisfaction problems and even vice-versa: to have a constraint satisfaction method solve an optimization problem (this is typically achieved by first finding a valid solution and then constraining future solutions to be better in terms of the optimization criterion; and continuing to do this iteratively).