NetworkXを使ってエイト・クイーンパズルを解く

“Python言語によるビジネスアナリティクス”と言う本の中に、NetworkXについての記述があるのですが、
その演習問題(問題43)として8-クイーン問題が出題されています。
面白そうだったので挑戦してみたところ、なんとか解けました。
この問題がネットワーク解析に関係あるとは意外ですね。

まず、8-クイーン問題については、Wikipediaの説明が分かりやすいと思います。
エイト・クイーン – Wikipedia

簡単に言うと、8×8の盤面状にチェスのクイーン(将棋の飛車と角を足した動きができる最強のコマ)をお互いに取り合えない位置に並べるパズルです。
正解は92通り(盤面の反転や回転を除いた本質的なものは12通り)あるそうです。

さて、これを解くために、次のアプローチを考えました。

1. 8×8の各マスをノードとするグラフを構築する。
2. クイーンがお互いに取り合えるマス同士をエッジで結ぶ。
3. そのグラフの補グラフを取得することで、クイーンがお互いに取り合えないマス通しが結ばれたグラフを作る。
4. ノード数が8のクリーク(その中に含まれる全てのノードが結ばれている部分グラフ)を探索する。

最初からお互いに取り合えないマスの間を結ぶのではなく、2.と3.に分けてるのはその方が実装がシンプルになるからです。


import networkx as nx

# 盤面の一辺のマス数
bord_size = 8

# グラフ生成
G = nx.Graph()

# ノードを作成する
for i in range(bord_size):
    for j in range(bord_size):
        G.add_node((i, j))

# 同じ行か同じ列に並ぶノードをエッジで結ぶ
for i in range(bord_size):
    for m in range(bord_size):
        for n in range(m+1, bord_size):
            G.add_edge((i, m), (i, n))
            G.add_edge((m, i), (n, i))

# 同じ斜め線状に並ぶノードをエッジで結ぶ
for n1 in G.nodes:
    for n2 in G.nodes:
        if n1 == n2:
            continue
        elif n1[0]+n1[1] == n2[0]+n2[1]:
            G.add_edge(n1, n2)
        elif n1[0]-n1[1] == n2[0]-n2[1]:
            G.add_edge(n1, n2)


# 補グラフを得る (お互いに取り合わない辺が結ばれている)
G_complement = nx.complement(G)

# サイズが変の数に等しいクリークの一覧を得る
answers = [
        clieque for clieque in nx.find_cliques(G_complement)
        if len(clieque) == bord_size
    ]

# 得られた解の個数
print(len(answers))
# 92

こうして、92個の解が得られました。
あとは実際にこれを可視化してみましょう。


import numpy as np
import matplotlib.pyplot as plt

fig = plt.figure(figsize=(12, 30), facecolor="w")

for i, answer in enumerate(answers, start=1):
    bord = np.zeros([bord_size, bord_size])
    ax = fig.add_subplot(16, 6, i)

    for cell in answer:
        bord[cell] = 1

    ax.imshow(bord, cmap="gray_r")

plt.show()

出力がこちらです。　一個一個みていくと確かに縦横斜めにダブらない様にQueen(黒い点)が配置できています。
ただ、全部相異なることを確認するのは少し手間ですね。

もともと出題されていた本には解答が載っていないので、
もしかしたらこの記事のコードでは相当非効率なことをやっているかもしれませんが、
おそらくこんなイメージで解くのだと思います。

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル