We are now ready the show how to implement
a program that will solve the Guarini puzzle for us.
Let me remind you once again the statement of this puzzle.
In this case we're given two configurations,
for example a three by three board with two white knights and two black knights,
and the question is whether one configuration is reachable from the other one.
In other words, the question is whether we can move the knight
so that to get the second configuration from the first one.
Let me also remind you how we were able to solve this puzzle using graph theory.
In this case there is an underlying graph
connected to this board which can be drawn as follows.
So first let's introduce a new vertex,
you note for every cell
except for the middle one actually because it is not reachable by any knight.
So there are six, there are eight, I'm sorry,
essential cells in this case.
Okay, then we connect to cells by an edge
if they are within one knight moved in this case.
So this gives us the following graph with eight nodes and eight edges,
and it is instructive to draw this graph like this to untangle this graph and if
we untangle it then we see that it is actually just a cycle
with eight nodes and eight edges.
So it is six,
seven is connected with three and finally three is connected to two,
no three is connected to four,
six is connected to five
and two and four
are connected to eight.
So initially what we have is here we have
a white knight and also we have a white knight here
and a black knight is at position six and another black knight is at position eight.
Okay and then it is not difficult to see that if we
ask the knights to move around the cycle as clockwise or counter-clockwise,
then we reach a situation showed here on the right.
Okay, we were able to solve this puzzle by analyzing this graph,
but what is more interesting is
that there is a another graph connected to this puzzle or this game.
In this graph, let's use the following.
Let's introduce a separate node for
any possible configuration and by saying configuration,
I mean any 3 x 3 board with two white knights and two black knights,
some way in some cells except for the middle cell which is in any case is not reachable.
Our conflagration is going to be any such 3 x 3 board and
let's just imagine a graph where all the knights have all such possible configurations.
Then let's do the following.
Let's join two such configurations by
a non-directed edge if they are within a single knight move.
As usual this is best illustrated with an example.
So here we show just six possible configurations.
In fact there are many more,
many more such configurations.
So we have six of them shown here on
the slide and there are the folding edges between them.
Let's just try to understand what is the meaning of all these edges.
So for example these two guys are connected by an edge as you remember.
This means that they are within a single knight move and indeed in
this case to get from this configuration to that one from left to right,
we just move this black knight to the bottom right corner,
and vice versa if we would like to get from the right of these two blacks.
To the left of these guys,
we just move this knight here.
This means that they are within a single knight move from each other.
Similarly, if we can see that these two guys,
then we see that they only differ by moving this knight between these two cells.
Similarly, to these two guys,
this one and this one,
they differ just by moving this knight within these two cells, and so on.
Ont he other hand, these two nodes are not connected by an edge
because they're not within a single move from each other.
So there is no edge between them because to reach one of them by the other one,
from he other one you cannot move just a single knight.
At the same time, we see that one of them is reachable from the other one.
For example, if you have this configuration
and you would like to reach a configuration to the left of it,
you can first move the knight to get this configuration,
then you move the knight to reach this configuration and
finally you move the knight to reach the desired configuration.
Okay, so there is a graph connected to this game.
And then what remains to understand is that one configuration is reachable from
some other configuration if and only if they can respond in
two configurations belong to the same connected component in the corresponding graph.
This in turn means that if you have a program
which for a given graph computes connected components
then you can easily solve this puzzle just by
constructing the corresponding graph namely first by constructing all the nodes,
then by joining some pairs
of nodes by edges and then just passing this graph to your black box procedure.
Then what remains to be done is just to check whether
the given two configurations lie in the same connected component.
If they do, then one of them is reachable from the other one.
If they do not belong to the same component, then this actually the
prove that one of them is not reachable from the.