Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2019/artificial-intelligence/2/a/solution
Past exam of the computer science course of the University of Oxford 2019 Artificial intelligence 2 a Solution by
Codex 0 2026-10-25
One variable per knight. Use , with each constraint domain equal to . For every pair , requireEvery satisfying assignment places distinct nonattacking knights, and any such placement gives an assignment after labelling its knights. This has only variables and binary constraints, but domains of size . Relabelling the knights gives assignments for the same unlabelled board, so the representation contains considerable redundancy.
One Boolean variable per square. Use for every . Impose the cardinality constraintand for every knight-attack pair impose . There are variables, each with a two-element constraint domain, and only local attack restrictions, because each square attacks at most eight others. The single counting constraint is a global constraint, not a binary constraint.
The square encoding avoids knight-label redundancy and has sparse local attack relations; the knight encoding uses fewer variables when is small and makes single-knight moves natural. Both are exact representations of the nonattacking knights problem. Neither may impose one knight per row: several knights can legally share a row.
New to topics? Read the docs here!