Overview of the problem
If you takes teenagers as vertices of a graph, and have an edge
whenever the two teenagers are compatible. This gives you an
undirected graph, and what you need is a Hamiltonian path in this
graph (a path that contains every node exactly once). Maybe searching
the web on this abstract version of the problem will yield more
information. Much is said in wikipedia about the Hamiltonian path
problem, which is a NP complete problem. I will only try to discuss
some apects, with my limited competence on the topic, taking into
account the way your question is stated.
Backtracking is just a way of implementing a non-deterministic
algorithm. It is usually simpler to describe the non-deterministic
algorithm, and just say that it is implemented by backtracking, and
possibly explain separately what that is (as I do below)
The non-deterministic algorithm
In the case of the Hamiltoniam path problem (which you can translate
back into your teenagers problem), the non-deterministic algorithm is
Choose a starting node for the path, and mark it used.
While there are unmarked nodes do:
Choose a new unmarked node connected to the last node added to the path,
add it at the end of the path, and mark it used.
At the end of the loop you have a Hamiltonian path. The
statement is non deterministic, as you have to take one of many
possibilities, many (or all) of which may not succeed.
Failure may in general occur in different ways. Here you have failure
when none of the unmarked nodes is connected to the last node added to
the path (i.e. none of the remaining teenagers is compatible with the
last one chosen).
The backtracking implementation consist in keeping track, at each
occurrence of a
choose statement, of all the possible choices that
have not yet been tried. If you fail, you go back to the previous
choose, undoing what was done (i.e. node addition to the path and
node marking), discard the choice made and make a new choice from
those that have not yet been tried at that
One way of implementing this is to associate a list of remaining
alternative choices to each node of the constructed path. Another
possibility is to rely on the exception mechanism of the programming
I am not sure what is (or should be) considered pruning in this case.
Checking that a node chosen is connected to the previously chosen one
is a very trivial form of pruning. No pruning at all would be
exploring the complete set of remaining nodes at each
statement, to discover soon after that some fail because the node is
not connected to the end of the path.
The greedy algorithm as described by Yuval Filmus' answer is just the
non-deterministic algorithm, except for the fact that you do not
backtrack. You just fail. I do not know whether there is more to be
He is much more expert than I am on these issues. However, my own
feeling is that the very concept of greedy algorithm makes less or little
sense in this case. The reason is that I understand greedy algorithms
as a way of finding good solutions to quantitative optimization
problems, which may not be optimal in some cases.
A greedy algorithm also has to make choices, and does so on the basis
of local optimizations that may not be optimal globally. But it is
expected to succeed anyway and does not have to backtrack: the price
of greediness is that the "cost" (however defined) of the result obtained
by the algorithm may be higher than the cost of the optimal solution.
I do not think that is really very meaningful in an all or nothing
situation, were you are supposed to succeed or to fail, without any
measure of intermediate situations, like placing the largest possible
number of teenagers, or placing them all with the smallest number of
conflictual sittings. These examples may be seen as optimization
variants of the problem where greediness makes sense.
However, we can use heuristics that could possibly increase the
chances of success. In the case of our optimization variants, they
could e seen as greedy techniques that improve the chances of having
near otpimal solution (Though I did not prove anything). But the
greedy algorithm remains basically the non-deterministic description.
The heuritic comes as a way to choose that improves chances of
success, or of approaching the least cost.
One such heuristic, is to always choose one of the unmarked nodes that
has the least number of edges connecting to other unmarked nodes. The
purpose is to keep in your bag nodes that will be easier to connect to
the path, while removing those that are getting hard to use. And if one
of these node is disconnected from all others, or has only one
connection but cannot be added to the path immediately, you know you
have failed and can start backtracking earlier.
We could say that we try to optimize the cost of the search reather
than the cost of the solution obtained, and that this "greedy"
algorithm does increase the chances of success if there is no
backtrack, or reduce the number of search steps if we use backtrack,
or improve the solution obtained if we consider one of the two
optimization variants I described above (maximum number of
non-conflicting teenagers, or minimum number of conflicts).
A global improvement
A global way to improve the algorithm is to decompose the graph into a
a block tree of the graph, where each node is a biconnected
components. This can be done in linear time.
A Hamiltonian path for the whole graph is composed of subpaths in each
of the biconnected components, connected by the edges of the block
In practice, you solve the given problem at the level of the block
tree, and then you solve it independently for each block, i.e. for
each biconnected component.
Since the algorithm is exponential anyway (NO complete), there is much
to be gained whenever it can be decomposed, thus reducing the size of
Actually, if the block tree is not composed of a simple path without
branching, there is no solution to the problem. So that may be a way
of getting much faster negative answers.
This may also be seen as a form of global pruning of the search space.