Lesson 3

It turns out that this can be proved by analyzing the connected components of an associated graph. Before discussing how to do this, let us revisit another problem where connected components pop up, Guarini's puzzle. Recall that in this puzzle, one is given two \(3 \times 3\) boards, each containing two black knights and two white knights, and the goal is to get the second configuration from the first one by valid knight moves. We have discussed that the first of the two exchanges shown below is possible whereas the second one is not.

How would you implement a program that given two configurations checks whether they are reachable from each other?