In this section we demonstrate the expressive power
and the simple yet powerful modeling language of \gringo{}
by looking at the simple Towers of Hanoi puzzle.
It consists of three pegs and a set of discs of different sizes,
which can be put onto the pegs.
The goal is to move all pegs from the leftmost peg to the rightmost peg,
where at each time only the topmost disc can be moved on top of another peg.
Additionally, a disc may not be put on top of a smaller disc.
We ignore that there is an efficient algorithm to solve this problem
and just specify how a solution, in terms of a sequence of moves, has to look.
In ASP it is custom to provide a \emph{uniform}
problem definition~\cite{martru99a,niemela99a,schlipf95a}.
Following this methodology, we separate the encoding
from an instance of the following problem:
given an initial placement of the discs, a goal situation, and a number $n$,
decide whether there is a sequence of moves of length $n$
that satisfies the conditions given above.
We will see that this decision problem can be elegantly
specified by reducing it to a declarative problem solving paradigm like ASP,
where efficient off-the-shelf tools like \gringo\ and \clasp\
are ready to solve the problem reasonably well.
Such a reduction is now exemplified.
\subsection{Problem Instance}
\begin{figure}[tb]
\centering
\hanoiInstance
\caption{Towers of Hanoi Initial Situation\label{fig:toh_inst}}
\end{figure}
We consider a Towers of Hanoi instance specified via facts over predicates
\pred{peg}/$1$ and \pred{disk}/$1$ that correspond to the pegs and disks in the puzzle.
Discs are enumerated by consecutive integers beginning with one,
where a disc with a lower number is considered to be bigger than a disc with a higher number.
The pegs can have arbitrary names.
Furthermore, the predicates \pred{init\_on}/$2$ and \pred{goal\_on}/$2$ describe the initial and goal situation, respectively.
Their first argument is the number of a disc and the second argument is the peg
on which the disc is located in the initial or goal situation.
Finally, the predicate \pred{moves}/$1$ specifies the number of moves within which the goal situation has to be reached.
Note that the original puzzle had exactly three pegs and a fixed initial and goal situation.
With ASP we can easily change this requirement and
the encoding represented in the following works with an arbitrary number of pegs and any initial or goal situation.
Figure~\ref{fig:toh_inst} depicts a possible instance (the dashed discs mark the goal situation)
corresponding to the ASP program given below.
\begin{lstlisting}
peg(a;b;c).
disk(1..4).
init_on(1..4,a).
goal_on(1..4,c).
moves(15).
\end{lstlisting}
The ``\code{;}'' in the first line is some syntactic sugar (Section \ref{subsec:gringo:pool})
that expands the statement into three facts
\code{peg(a)}, \code{peg(b)}, and \code{peg(c)} representing the three pegs.
Again, in the second line some syntactic sugar is used to
create the facts \code{disc(1)}, \code{disc(2)}, \code{disc(3)}, and \code{disc(4)}.
Here the term \code{1..4}, an intervall (Section \ref{subsec:gringo:interval}), is successively replaced by \code{1}, \code{2}, \code{3}, and \code{4}.
The initial and goal situation is specified in line three and four again using intervall.
Finally, in the last line the number of moves to solve the problem is given.
\subsection{Problem Encoding}
We now proceed by encoding the Towers of Hanoi puzzle via non-ground rules (Section \ref{subsec:gringo:normal}),
i.e, rules with variables that are independent of particular instances.
Typically, an encoding consists of a \emph{Generate}, a \emph{Define},
and a \emph{Test} part~\cite{lifschitz02a}.
We follow this paradigm and
mark respective parts via comment lines beginning with \code{\%} in the encoding below.
The variables \code{D}, \code{P}, \code{T}, and \code{M} are used
to refer to disks, pegs, the \code{T}-th move in the sequence of moves, and the length of the sequence, respectively.