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.