Pythonとグラフ理論で全国小中学生プログラミング大会グランプリ作品を解く

# グラフ理論とは？
グラフ(Graph)[^1]とは、点と辺によって構成される図形のことです。
例えば鉄道の路線図、Twitterのフォロー関係、コンピューターネットワークなどもグラフで表すことができます。

![exgraph.png](https://qiita-image-store.s3.amazonaws.com/0/137045/03f40839-c895-0155-4201-b39c2ae44431.png)

グラフ理論は、グラフに関する数学の理論のことです。
例えば、A駅からB駅までの経路検索といったシーンで、グラフ理論が応用されています。

# 「つながる。」とは？
「つながる。」は[@YukiMihashi](https://twitter.com/YukiMihashi)さんがScratchで製作されたパズルゲームで、第3回[全国小中学生プログラミング大会](http://jjpc.jp/2018/)のグランプリに選ばれた作品です。
![tsunagaru_animation.gif](https://qiita-image-store.s3.amazonaws.com/0/137045/e15a7f63-e6dc-fae1-89fa-15143eff9a88.gif)
タイルをクリックするとタイルが回転し、人と人が白い線によってつながるようにするゲームです。

「つながる。」はこちらで遊ぶことができます:
https://scratch.mit.edu/projects/180846317/

# グラフ理論で「つながる。」のステージを解けるの？
[Graphillion](https://github.com/takemaru/graphillion/wiki)というPythonライブラリを使って「つながる。」のステージを解くことができます。

Graphillionには、2012年ごろに話題になった「お姉さん問題」を高速に解くことができるアルゴリズムが実装されています。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">再生回数200万回突破！「『フカシギの数え方』おねえさんといっしょ！みんなで数えてみよう！ 」　動画はこちら→　<a href="https://t.co/3XPmHVoSIe">https://t.co/3XPmHVoSIe</a> <a href="https://t.co/yMECCqFX2w">pic.twitter.com/yMECCqFX2w</a></p>&mdash; 日本科学未来館 (@miraikan) <a href="https://twitter.com/miraikan/status/1004618995436224512?ref_src=twsrc%5Etfw">2018年6月7日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

Graphillionを利用するにはグラフ理論の用語を知っている必要がありますが、この記事では必要な用語が出てきたときに注釈を付けるようにしました。

# 「つながる。」のステージを解く
## 何が答えとなるのか？
ステージのタイルを回転させ、人と人を**上手に結ぶこと**ができれば、そのステージが解けたことになります。
![worldstage2_graph.png](https://qiita-image-store.s3.amazonaws.com/0/137045/6df34a22-5a2b-6ce8-530f-d42060495acc.png)
上手に結んだ人と人とのつながりは**グラフ**であると言えます。
この**グラフ**は必ずグリッドグラフ[^2]の部分グラフ[^3]となっています。

## Graphillionが得意なこと
Graphillionはベースとなるグラフから条件を満たす部分グラフ[^3]を高速に探し出すことが得意です。

「お姉さん問題」を例にしてみます。
<img width="575" alt="スクリーンショット 2018-10-26 21.48.27.png" src="https://qiita-image-store.s3.amazonaws.com/0/137045/1128d8e5-e068-f147-d287-85cd502d5228.png">
ベースはグリッドグラフ[^2]で、条件は始点(S)から終点(G)までの道[^4]とすれば、条件を満たす部分グラフは**同じところを2度通らない道順**だといえます。Graphillionを使えば条件を満たす部分グラフの数を数えたり、列挙することができます。

## Graphillionで「つながる。」のステージを解く
「つながる。」のステージもGraphillionが得意な問題に置き換えてみましょう。

「つながる。」のステージを解くには、グリッドグラフ[^2]をベースとし、**タイルを回転してできる**部分グラフをすべて探し出せば良さそうです。
ですが、**タイルを回転してできる**という条件をそのまま利用することはできません。Graphillionで問題を解くにはグラフ理論の言葉で表現されている必要があるからです。

### グラフ理論の言葉で条件を考える
ステージのタイルをよく観察すると、タイルの種類ごとにタイルの上にいる人(以下、点と呼ぶ)の次数[^5]が決まっていることがわかります。

タイル | ![1.png](https://qiita-image-store.s3.amazonaws.com/0/137045/5663d549-33d0-8faa-4a4e-ecc08d64ed74.png) | ![L.png](https://qiita-image-store.s3.amazonaws.com/0/137045/fb2a3fe3-3333-d1d8-ee1d-5f41f538ea1e.png) | ![I.png](https://qiita-image-store.s3.amazonaws.com/0/137045/4d89de53-fe8e-d15e-4b16-42840d3dbf5a.png) | ![3.png](https://qiita-image-store.s3.amazonaws.com/0/137045/720c225d-85bf-0c1c-8904-355b0f48c893.png) | ![4.png](https://qiita-image-store.s3.amazonaws.com/0/137045/239835d8-6a67-e068-518a-fa343610c2ea.png)
--- | :---: | :---: | :---: | :---: | :---:
次数 | 1 | 2 | 2 | 3 | 4

各点に次数の条件を付けることで、**タイルを回転してできる**という条件をうまくグラフ理論の言葉に置き換えできたかのように思えます。
しかし、**点の次数が2**と対応するタイルは2種類あり、次数の条件だけではタイルを区別できる条件とはなっていません。

### L字タイルとI字タイル
**点の次数が2**と対応する2種類のタイルを、L字タイル、I字タイルと名付けて呼ぶことにします。
L字タイルとI字タイルの上にある点には次数2という条件に加え、もう少し条件を付けましょう。

I字タイルの上にある<font color="red">**点**</font>の<font color="red">**周りの辺**</font>は、下図のどちらかになっています。
![worldstage2_graph2.png](https://qiita-image-store.s3.amazonaws.com/0/137045/6bbf54e7-e541-5679-a277-77bad5712f50.png)

同様にL字タイルの上にある<font color="red">**点**</font>の<font color="red">**周りの辺**</font>は、下図のどれかになっています。
![worldstage2_graph3.png](https://qiita-image-store.s3.amazonaws.com/0/137045/9a3d5c4d-32c0-eed1-e03e-7b884d5362c1.png)

条件は上のもので正しいのですが、Graphillionでは「どれか」といったOR条件を付けるよりもAND条件を付ける方が簡単な都合上、L字タイル、I字タイルのお互いの条件を**否定した条件**を付けると良いです。

---

I字タイルの上にある<font color="red">**点**</font>の<font color="red">**周りの辺**</font>は、下図の**どれにも当てはまらない**
![worldstage2_graph5.png](https://qiita-image-store.s3.amazonaws.com/0/137045/405e95ea-dd58-9df6-582c-ffe9af345592.png)

L字タイルの上にある<font color="red">**点**</font>の<font color="red">**周りの辺**</font>は、下図の**どちらにも当てはまらない**
![worldstage2_graph4.png](https://qiita-image-store.s3.amazonaws.com/0/137045/e9c6b77c-9263-99bb-2a26-998344edbbab.png)

(Graphillionでは、excludingメソッドで「部分グラフとして含まない」という条件を設定できるので、<font color="red">**2辺からなるグラフ**</font>を部分グラフとして含まないように条件を設定します)

## プログラムを書いてステージを解く
### 必要なライブラリと環境
* Python 2.7 or Python 3.7.2
    * `graphillion`
    * `networkx`
    * `matplotlib`

[Graphillion - 無数のグラフを効率的に扱うための高速・軽量ライブラリ](https://github.com/takemaru/graphillion/wiki) に書いてあるの手順に従い、 `networkx`, `matplotlib`, `graphillion` を使える状態にしておきます。

(2019/03/21 追記)
Graphillion が Python 3系でも動くようになったので、Python 3.7.2 においても実行できるようにプログラムを修正しました。
macOSの場合、グラフをプロットするにはこちらの設定が必要かもしれません: [matplotlib.pyplotをimportするとエラーが出たり画面が白く描画される問題の対応(macOS)](https://qiita.com/mascii/items/6e5a600d6098bce364bf)

### ステージを解くプログラム
実装方法については割愛しますが、実装の方針はすでに説明しており、[Graphillion: 数え上げおねえさんを救え / Don't count naively
](https://www.youtube.com/watch?v=R3Hp9k876Kk&feature=youtu.be)(YouTube動画)を見ればある程度実装方法がわかるかと思います。

ステージはタイルの並びなので、入力はタイルの並びとなります(`tiles`)。

```python
# coding: UTF-8

from graphillion import GraphSet
import networkx as nx
import matplotlib.pylab as plt
import graphillion.tutorial as tl
(L, I) = ('TILE_L', 'TILE_I')

# tl.draw() のほぼコピペ(ラベルを表示する処理を追加)
def draw(g, universe=None):
    if not isinstance(g, nx.Graph):
        g = nx.Graph(list(g))
    if universe is None:
        universe = GraphSet.universe()
    if not isinstance(universe, nx.Graph):
        universe = nx.Graph(list(universe))
    n = sorted(universe[1].keys())[1] - 1
    m = universe.number_of_nodes() // n
    g.add_nodes_from(universe.nodes())
    pos = {}
    for v in range(1, m * n + 1):
        pos[v] = ((v - 1) % n, (m * n - v) // n)
    nx.draw(g, pos)
    nx.draw_networkx_labels(g, pos)  # ラベルを付与
    plt.show()

def get_degree(tile):
    if tile == L or tile == I:
        return 2
    return tile


# ステージのサイズとタイルの並びをここに入力
# 1: 次数1に対応するタイル
# L: 次数2に対応するタイルでL字のもの
# I: 次数2に対応するタイルでI字のもの
# 3: 次数3に対応するタイル
# 4: 次数4に対応するタイル
n = 9
tiles = [ L, 3, 3, 3, 3, 3, 3, 3, L,
          3, 4, L, L, L, L, L, L, 3,
          3, 3, I, I, I, I, I, 3, 3,
          3, L, L, I, L, 1, L, L, 3,
          3, L, 3, L, L, L, I, L, 3,
          3, L, 3, 3, L, 3, 3, L, 3,
          3, 3, 3, 1, L, L, I, L, 3,
          3, 3, 3, 3, 3, 3, 3, 3, 3,
          L, 3, 3, 3, 3, 3, 3, 3, L, ]

# n*nのグリッドグラフの生成
# draw(grid_graph) で点と辺の位置関係を確認してみてください
grid_graph = tl.grid(n - 1, n - 1)

# ベースのグラフ(grid_graph)をセット
GraphSet.set_universe(grid_graph)

# grid_graphの点のラベルが 1,2,3,...,n*n なのでインデックスをずらす
tiles.insert(0, None)

# 次数条件
degree_constraints = {v: get_degree(tiles[v]) for v in range(1, n * n + 1)}

# 各点に次数条件を付けたグラフセット
graphs = GraphSet.graphs(degree_constraints=degree_constraints)

# I字タイルとL字タイルの上の点には追加の条件を付ける
for v in range(1, n * n + 1):
    if tiles[v] == L:
        if (v - 1, v) in grid_graph and (v, v + 1) in grid_graph:
            graphs = graphs.excluding([(v - 1, v), (v, v + 1)])
        if (v - n, v) in grid_graph and (v, v + n) in grid_graph:
            graphs = graphs.excluding([(v - n, v), (v, v + n)])
    if tiles[v] == I:
        if (v, v + 1) in grid_graph and (v, v + n) in grid_graph:
            graphs = graphs.excluding([(v, v + 1), (v, v + n)])
        if (v, v + n) in grid_graph and (v - 1, v) in grid_graph:
            graphs = graphs.excluding([(v, v + n), (v - 1, v)])
        if (v - 1, v) in grid_graph and (v - n, v) in grid_graph:
            graphs = graphs.excluding([(v - 1, v), (v - n, v)])
        if (v - n, v) in grid_graph and (v, v + 1) in grid_graph:
            graphs = graphs.excluding([(v - n, v), (v, v + 1)])

print('ステージの解:{}通り'.format(graphs.len()))

for g in graphs:
    draw(g)
```

### プログラムを実行
上のコードにある `n` と `tiles` は「つながる。」の「世界のステージ9」に対応しています。
<img width="493" alt="world_stage9.png" src="https://qiita-image-store.s3.amazonaws.com/0/137045/f1e4c75f-cc16-4d23-18ad-9401da8b7db7.png">

Pythonでプログラムを実行すると、 `ステージの解:3通り` と表示され、3通りの答えが表示されます。
<img width="400" src="https://qiita-image-store.s3.amazonaws.com/0/137045/db20b481-76bb-8fac-b8a4-b1dd49cf5b73.gif">
このグラフを見ながらタイルを回転させればステージをクリアできるはずなのですが、「つながる。」では3通りの答えすべてがクリアとならず、3通りの答えのうちひとつだけがクリア扱いとなるようでした。
(ステージの製作者が意図した解答のみがクリア扱いとなります)

# すべての人がつながっている必要はなかった
「つながる。」というタイトルから、すべての人がひとつにつながっていないといけない気がするものですが、連結グラフ[^6]であることがクリア条件ではありませんでした(例: 世界のステージ10)。
<img width="490" alt="world_stage_10.png" src="https://qiita-image-store.s3.amazonaws.com/0/137045/42c0d332-e8b9-6b66-9294-efb1a9581d34.png">

この仕様をうまく利用すると2通りの答えがあるステージで、片方は連結グラフ[^6]でもう一方は非連結グラフ[^7]とすることができ、非連結な方でクリアになるトリッキーなステージを作ることができます[^8]。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">つながっていない方がクリアになる「つながる。」ステージの例 <a href="https://t.co/iitgDKrhog">pic.twitter.com/iitgDKrhog</a></p>&mdash; mascii (@mascii_k) <a href="https://twitter.com/mascii_k/status/1055106010921164801?ref_src=twsrc%5Etfw">2018年10月24日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

Graphillion(とNetworkX)を使えばこのようなステージも探し出すことができます。

# まとめ
* Graphillionを使えば、「お姉さん問題」や「つながる。」といったグラフの組み合わせ問題が解けることは大変素晴らしいことです。
* 「つながる。」はScratchで作られていますが、ここまでのものを作れることを知りませんでした。
* Graphillionの記事が少ない中、「つながる。」という事例としてぴったりなパズルを題材に記事を書くことができて良かったです。読者の方々にグラフ理論とプログラミングの面白さが伝わりましたら幸いです。

# 参考文献
* [超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ－](https://www.amazon.co.jp/dp/4627852614)

[^1]: (この記事では、グラフとは主に有限位数を持つ無向単純グラフのことを指すことにします)
[^2]: グリッドグラフ: 格子状のグラフのこと(お姉さん問題のグラフの形と同じですね！)
[^3]: 部分グラフ: 元のグラフから辺と点を取り除いてできるグラフのこと
[^4]: 道: グラフ理論では「道順」のことをパス(path)や道といいます。パスもグラフだといえます
[^5]: 次数: その点に接している辺の本数のこと
[^6]: 連結グラフ: グラフ上のどの2点間も、辺を渡り歩いてたどり着くことができるグラフのこと
[^7]: 非連結グラフ: 連結グラフでないグラフのこと
[^8]: (プログラムの弱点を指摘したいのではなく、ゲームの面白い性質として考えております)