AJ + AL + AF = 28
(AJ+ X) + (AL+ X) + (AF+ X) = 37
Step 5: Solve the Problem
Once the problem has been properly framed into a
(formal) model and a solving technique has been
chosen for solving it, it is possible to run the algorithms and compute the solution.
The solution to this problem is X = 3.
Example 2: 10-Digit Puzzle
The following example, taken from Martin Gardner’s
Mathematical Puzzle Tales (Gardner 1981), is more difficult for a human player, at least with regard to the
three friends example. Indeed, it is targeted to secondary school students, and would require more
advanced problem-solving capabilities.
Find a 10-digit number where the first digit is how
many zeros there are in the number, the second digit
is how many 1s in the number, and so on, until the
10th digit, which is how many 9s in the number.
From a human viewpoint, the understanding of the
text and the problem modeling (steps 1–3) should be
straightforward, while solving the problem (step 4) is
more difficult. If a generate-and-test approach has to
be avoided, a number of different reasoning actions
have to be implemented by a human, and a more creative process is called in.
However, from a computer viewpoint, steps 1–3 are
rather complex, while step 4 (solving the problem)
might be definitely easier, for example by exploiting
constraint-satisfaction techniques aimed at exploring
large search spaces. In the following, we simply
sketch how this problem can be faced by following
the steps previously described.
Step 1: Understanding Text (and Pictures)
Understanding text here would amount to discover-
ing the following:
Find a number made of 10 digits (this is the goal).
A digit is a number from 0 to 9.
“How many zeros” in the number means counting the
occurrences of zeros among the digits of the number
itself. This information should be generalized for all
the other digits by correctly understanding the “and so
on, until …” part of the sentence.
The occurrences of the i value in the list of digits
should be equal to the ith digit. This step is again a
consequence of a generalization from the “and so on,
until…” part of the sentence.
Step 2: Identify the Modeling and Solving Technique
Given the structure of the problem, a constraint
model and a constraint-solving technique based on
backtrack search (with possible propagation) can be
Step 3: Identify Problem Components
and Hidden Knowledge
Since the problem can be encoded into a constraint-
satisfaction problem, the main components that have
to be identified are variables, domains, and con-
There are 10 variables, each one representing a digit of
the number to be determined.
Each digit has a position (from 0 to 9).
Each variable has an integer domain between 0 and 9.
As a constraint, the number of occurrences of i in the
digits should be equal to the ith digit.
Step 4: Model the Problem
In a constraint model we have variables, domains,
and constraints (expressed in a constraint language of
choice). Using constraint logic programming, it is
possible to model the problem directly as a set of 10
variables, each with domain [0 … 9], and each variable being subjected to a global constraint that captures the number of occurrences of the ith digit.
Step 5: Solve the Problem
The problem-solving process in this case exploits a
constraint solver that uses propagation algorithms
The solution of this problem is the number
Notice that more information could be inferred. In
our case such information is not needed for deter-
mining a solution, although this is not the case in
general. For example, we would infer that:
The sum of all digits is 10.
The weighted sum of all digits where the weight is
their position is again 10.
The first digit cannot be a zero, and hence there is at
least one or more zeros.
No digit can take the value 9.
In the constraint-programming literature, these are
called redundant constraints, namely constraints that
are subsumed by other constraints of the problem.
Depending on the technique used to solve the problem, redundant constraints should either be identified and removed from the model or should be left in
the model. For example, in linear integer programming solvers redundant constraints do not bring any
advantage to the solving algorithm and are removed
in preprocessing. In constraint programming on
finite domain solvers where propagation is not complete, instead, they might help reducing the search
space and find a solution more quickly.
Example 3: Knights and Knaves
There are many mathematical puzzles that are indeed
logic puzzles, and that are typically aimed at determining the truth value of a proposition, given some
assertions whose truth value is a priori known. The
following problem is taken from Smullyan (1978).
There is an island where every inhabitants is either a
knight or a knave (exclusive or). Knights always tell the
truth, while knaves always lie. You are a tourist just
arrived in the island, and you met two inhabitant A