COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

## Constraint Satisfaction ProblemsAdd to your list(s) Download to your calendar using vCal - Diptarko Roy, Churchill College
- Wednesday 29 November 2017, 19:30-20:00
- Wolfson Hall, Churchill College.
If you have a question about this talk, please contact Matthew Ireland. Constraint satisfaction problems (CSPs) involve finding an assignment of discrete values to variables under the presence of constraints which limit what combinations of assignments are allowed. An example would be colouring a graph with a limited number of colours, such that no two adjacent nodes have the same colour, or solving a Sudoku puzzle. These both involve potentially searching a combinatorially large space of candidate solutions for a feasible assignment. The talk will begin with an introduction to CSPs and some examples, and point out the specific deficiencies of naive approaches such as basic backtracking (as in Prolog), and how constraint propagation and specialised algorithms for global constraints improve on this. We’ll then see how a sequence of successively more sophisticated approaches and heuristics reduce graph colouring and Sudoku from requiring intractable amounts of time to being solvable within seconds. This talk is part of the Churchill CompSci Talks series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsGut feeling: how bacteria influence our wellbeing Outreach University of Cambridge Conservation Research Institute (UCCRI)## Other talksEurostar with Philippe Mouly The interpretation of black hole solutions in general relativity Radiocarbon as a carbon cycle tracer in the 21st century Dispersion for the wave and the Schrodinger equations outside strictly convex obstacles What You Don't Know About God Propagation of Very Low Frequency Emissions from Lightning |