COMPUTER SCIENCE TRIPOS Part IB – 2018 – Paper 6
Artificial Intelligence (SBH)
Consider the standard 3 × 3 sliding blocks puzzle.
5
8 8
2 3
7 8
4 5 6
1 2 3
7 5
4 6
1
7
4 6
1 2 3
The aim is to find a sequence of moves that re-arranges the puzzle to the state shown
on the right, where each move involves sliding a single square into the empty space.
(a) Explain in detail how this problem can be treated as a planning problem by
translating it into a Boolean satisfiability (SAT) problem. Your answer should
address the following issues, and in each case should provide specific examples
of the SAT representation:
(i) The representation of the start state and goal state. [4 marks]
(ii) The representation of the relevant actions using successor-state axioms.
[4 marks]
(iii) The need for precondition axioms. [2 marks]
(iv) The need for action-exclusion or state-constraint axioms, and why one
might be preferred over the other. [3 marks]
(v) The algorithm that can be used to employ a SAT-solver to solve a given
sliding blocks problem, and the method for extracting a solution.
[3 marks]
(b) You do not have a SAT-solver available. You do however have a solver for general
local search problems. Explain how you might use the latter to solve the SAT
problem obtained in Part (a). [4 marks]
1