Lesson 9

Returning to Guarini's puzzle, one can construct the following configuration graph. The nodes of this graph are all configurations containing two black knights and two white knights on a \(3 \times 3\) board. Two configurations are joined by an edge if they differ by a single knight move. A part of this graph is shown below.

In Python, it is particularly easy to construct the configuration graph. One can then analyze the graph using various built-in methods. The code below shows that the configuration graph consists of 420 nodes and 960 edges. One sees also that there are two connected components. This is not surprising: there is a cluster of configurations where the black and white knights alternate (along the circle) and there is another cluster where two white knights follow two black knights. Finally, the code shows that the minimum number of moves needed is 16: the number of nodes in the shortest path between the corresponding two nodes is 17, hence the minimum number of moves is 16.

import networkx as nx
from itertools import combinations, permutations

board_graph = nx.Graph([(0, 4), (4, 5), (5, 1), (1, 7),
                        (7, 3), (3, 2), (2, 6), (6, 0)])

conf_graph = nx.Graph()
conf_graph.add_nodes_from(permutations('WWBB****'))

for conf1, conf2 in combinations(conf_graph.nodes(), 2):
    diff = [i for i in range(8) if conf1[i] != conf2[i]]
    if len(diff) != 2:
        continue
    i, j = diff

    if board_graph.has_edge(i, j) and \
            (conf1[i] == conf2[j] and conf1[j] == conf2[i]) and \
            [conf1[i], conf1[j]].count('*') == 1:
        conf_graph.add_edge(conf1, conf2)

print(nx.number_of_nodes(conf_graph))
print(nx.number_of_edges(conf_graph))
print(nx.number_connected_components(conf_graph))

print(len(nx.shortest_path(
    conf_graph, tuple("W*W**B*B"), tuple("B*B**W*W"))))

420
960
2
17