Help us understand the problem. What is going on with this article?

組合せ最適化でエデンの園配置を証明する

More than 1 year has passed since last update.

Advent Calendar 3日目の記事 組合せ最適化でボンバーパズルを解く
Advent Calendar 5日目の記事 組合せ最適化でステンドグラスを解く

これなに

エデンの園配置をしっていますか?

エデンの園配置とは、セル・オートマトンにおいて他のいかなる配置からも到達できない配置を指す。
~~~~ エデンの園配置 - wikipediaより

セル・オートマトンの一種であるライフゲームの下記のエデンの園配置が本当にそうか確かめてみましょう。

組合せ最適化で使われるソルバーは、全ての組合せを調べてくれます。ソルバーで答えが出ないことがわかれば、エデンの園配置であることが証明できます。

考え方

ライフゲームで許される条件を数式で表現します。

  • 現在=生:
    • 過去=生、過去の周り8マス=2
    • 過去の周り8マス=3
  • 現在=死:
    • 過去の周り8マス<=1
    • 過去=死、過去の周り8マス=2
    • 過去の周り8マス>=4

OR条件は、線形式で表現できないので、0-1変数を使って場合分けします。

Pythonのプログラム

1つ前の状態を計算するプログラム(solve)は下記のようになります。

python
import pandas as pd, matplotlib.pyplot as plt
from pulp import LpProblem, LpStatus, lpSum, value
from ortoolpy import addbinvar, addbinvars
def solve(data):
    ni,nj = len(data),len(data[0])
    a = pd.DataFrame([(i,j,data[i][j]!='.') for i in range(ni)
        for j in range(nj)], columns=list('行列値'))
    a['Var'] = addbinvars(len(a))
    m = LpProblem()
    for _,r in a.iterrows():
        v = lpSum(a.query(f'{r.-1}<=行<={r.+1}&{r.-1}<=列<={r.+1}').Var)-r.Var
        if r.: # 3 <= v+x, 2v+x <= 7
            m += v + r.Var >= 3
            m += 2*v + r.Var <= 7
        else: # v+x <= 2 or >=4
            y = addbinvar()
            m += v + r.Var <= 2 + 7*y # y==0 → v+x <= 2
            m += v         >= 4*y     # y==1 →   v >= 4
    m.solve()
    print(LpStatus[m.status])
    if m.status==1:
        a['Val'] = a.Var.apply(value)
        plt.imshow((a.Val<0.5).values.reshape(ni,nj), cmap='gray', interpolation='none')
        plt.show()

確認その1

最初に、solveが1つ前の状態を計算できているか、簡単な例で確かめてみましょう。
(下記は、エデンの園配置ではなくグライダーです)

python
solve("""\
.#.
#..
###""".splitlines())
>>>
Optimal

image.png

Optimalなので、解が存在します。確かに、図の状態から1ステップ進めると、入力の状態になることが確認できます。solveが1つ前の状態(の1つ)を計算できているのが確認できました。

確認その2

python
solve("""\
.##..#.##...
#..##..#.#.#
.#.#.##.#.#.
#....##..##.
.###...#....
..#.#.##.#..
.#.##...#.#.
#....#.#....""".splitlines())
>>>
Infeasible

今度は、Infeasible1です。確かに、エデンの園配置のようです。

以上


  1. 2018/10/25、筆者のPRでバグが修正されて「Infeasible」と表示されるようになりました。 fix: issue-171, add MIP Infeasible status 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした