In this question, we consider the Magnet Tile Building Problem: you have a set of r different

shapes of tiles that come in k colours. Given a structure, you want to know if it$$s possible to select a colour

for each tile such that no connecting tiles share a colour. The input to the Magnet Tile Building Problem

consists of:

$$ a list of tiles in the structure numbered from $1$ to n$,$ each of which has an identifier from $1$ to r

specifying the shape of the tile;

$$ a set of m ordered pairs $($i$,$ j$)($with i $<$ j$)$ which indicates that tile i is connected to tile j;

$$ the number of available colours k$.$

You can assume that you have arbitrarily many tiles in each shape and colour, and that any input you$$re

given will correspond to a structure that is physically possible to build with your tiles $($so$,$ for example, you

won$$t have a triangle that$$s supposed to be connected to $1,157$ other triangles of the same size$).$

$1.[4$ points$]$ Show how to reduce an arbitrary instance of the magnet tile building problem into an instance

of Boolean Satisfiability $($SAT$).$ Hint: my reduction uses nk variables