「世界初、来店不要のフルオーダーメイド靴」のプレスリリースを行いました。

20-2. vcoptでテント・アンド・ツリーパズルを解く

やること

テント・アンド・ツリーというパズルがあります。

Tents and Trees Puzzles - Apps on Google Play
Place a tent next to each tree in this original puzzle game! Numbers around the grid tell you how many tents must be placed on each row and column. Be careful, ...

例題1

次の3つのルールを満たすように、黒いマスを「テント」か「芝生」で埋めていきます。

  1. 木の4近傍には必ず対となるテントが1つある
  2. テントの8近傍には他のテントがあってはならない
  3. 各行、各列には数字の数だけテントが存在する

解答は一意に定まります。(芝生を1マスだけ残してあります)

今日は、このパズルをvcoptを用いて解いてみます。

実行環境

WinPython3.6をおすすめしています。

WinPython - Browse /WinPython_3.6/3.6.7.0 at SourceForge.net
Portable Scientific Python 2/3 32/64bit Distribution for Windows

vcoptの使い方についてはチュートリアルをご参照ください。

vcoptの仕様については最新の仕様書をご参照ください。本記事執筆時とは仕様が異なる場合があります。

考え方1

まず、テントが入る可能性があるマス(つまり木の4近傍のマス)の数だけ遺伝子座を用意し、各遺伝子座には0または1の遺伝子が入ることにします。0は芝生、1はテントを表します。

例題1の場合は13ヶ所です。

あとは評価関数において、パズルのルールが満たされているかを見て、満たされていなければペナルティを科します。

  1. 木の4近傍にあるテントの数が1でなければペナルティ
  2. テントの8近傍にある他のテントの数が0でなければペナルティ
  3. 各行、各列の「テントの数」と「数字」の差がペナルティ

ペナルティの合計が0になるように最適化します。なんだ簡単じゃないか!()

考え方2

とフラグを立ててしまいましたが、実際にやってみるとうまくいきません。

例えば次のようなとき、

正解がパターン1であれば問題ないのですが、正解がパターン2であるときに困ります。下の木の4近傍にテントが2つあるためペナルティ=1が科されます。最適化ではペナルティ0を目指すのでパターン1に近づきますが、正解はパターン2ですがら、正解から遠ざかっていまいます。

そこで、1番目のペナルティを修正します。

  1. 木の4近傍にあるテントの数が1または2でなければペナルティ
  2. テントの8近傍にある他のテントの数が0でなければペナルティ
  3. 各行、各列の「テントの数」と「数字」の差がペナルティ

※厳密に言えばこの条件では解が一意に定まらず、「木と対になるテントがある」を見たさない解が出ることがありますが、今回はこれで良しとします。

pip, import

まだvcoptをpipしていない場合はpipします。

pip install vcopt

必要なパッケージをimportします。4近傍とか8近傍を畳み込むために signal.convolve2d() を用います。

import numpy as np
import numpy.random as nr
from copy import deepcopy
from scipy import signal
from vcopt import vcopt

パズル問題

パズル問題は ‘-‘ と ‘t’ で表現します。horizontal は右方向に並んだ数字、vertical は縦方向に並んだ数字です。

#============================
# パズル
#============================
pazzle = ['-----',
          '-t-t-',
          '-----',
          'tt---',
          '----t']
horizontal = [2,0,1,1,1]
vertical = [1,1,0,2,1]

前処理を行います。

#============================
# パズルの変換とフィルタの用意
#============================
tree = []
for line in pazzle:
    line = line.replace('-', '0')
    line = line.replace('t', '1')
    tree.append(list(line))
tree = np.array(tree, dtype=int)
print('tree\n{}'.format(tree))

tent = np.zeros(tree.shape, dtype=int)
print('tent\n{}'.format(tent))

horizontal = np.array(horizontal)
print('horizontal\n{}'.format(horizontal))
vertical = np.array(vertical)
print('vertical\n{}'.format(vertical))

#畳み込み用のフィルタ
filter_4 = np.array([[0, 1, 0],
                     [1, 0, 1],
                     [0, 1, 0]], dtype=int)
filter_8 = np.array([[1, 1, 1],
                     [1, 0, 1],
                     [1, 1, 1]], dtype=int)
tree
[[0 0 0 0 0]
 [0 1 0 1 0]
 [0 0 0 0 0]
 [1 1 0 0 0]
 [0 0 0 0 1]]
tent
[[0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]
 [0 0 0 0 0]]
horizontal
[2 0 1 1 1]
vertical
[1 1 0 2 1]

木の配列、テントの配列(空っぽ)ができました。

評価関数

気になる方はコメントアウトを解除して詳しく見てみてください。

#評価関数
def score(para):
    #paraをテント配列に範反映
    tent_tmp = deepcopy(tent)
    tent_tmp[mask_candidate] = para
    #print('tent_tmp\n{}'.format(tent_tmp))
    
    #木の4近傍にあるテントの数
    tent_around_tree = signal.convolve2d(tent_tmp, filter_4, mode='same') * tree
    #print('tent_around_tree\n{}'.format(tent_around_tree))
    #それが1または2でない木
    penalty_tree = (tent_around_tree != 1) * (tent_around_tree != 2) * tree
    #print('penalty_tree\n{}'.format(penalty_tree))
    
    #テントの8近傍にあるテントの数
    tent_around_tent = signal.convolve2d(tent_tmp, filter_8, mode='same') * tent_tmp
    #print('tent_around_tent\n{}'.format(tent_around_tent))
    #それが0でないテント
    penalty_tent = (tent_around_tent != 0) * tent_tmp
    #print('penalty_tent\n{}'.format(penalty_tent))
    
    #horizontalのペナルティ。多いまたは少ない数
    penalty_horizontal = np.abs(np.sum(tent_tmp, axis=0) - horizontal)
    #print('penalty_horizontal\n{}'.format(penalty_horizontal))

    #verticalのペナルティ。多いまたは少ない数
    penalty_vertical = np.abs(np.sum(tent_tmp, axis=1) - vertical)
    #print('penalty_vertical\n{}'.format(penalty_vertical))
    
    #合計ペナルティ
    penalty = np.sum(penalty_tree) + np.sum(penalty_tent) + np.sum(penalty_horizontal) + np.sum(penalty_vertical)
    
    return penalty


#木の4近傍のマス
mask_candidate = (signal.convolve2d(tree, filter_4, mode='same') > 0) * (tree == 0)
print('mask_candidate\n{}'.format(mask_candidate))

#その数(=遺伝子座の数)
para_num = np.sum(mask_candidate)
print('para_num\n{}'.format(para_num))

#その数だけランダムな遺伝子を用意する
para_random = nr.randint(0, 2, para_num)
print('para_random\n{}'.format(para_random))

#ペナルティを表示
print('penalty\n{}'.format(score(para_random)))
mask_candidate
[[False  True False  True False]
 [ True False  True False  True]
 [ True  True False  True False]
 [False False  True False  True]
 [ True  True False  True False]]
para_num
13
para_random
[0 0 1 1 0 0 1 0 1 0 0 0 1]
penalty
15

遺伝子座は13個で、ランダムな遺伝子(para)を評価関数に入れてみると、ペナルティ15が返ってきました。

GAで最適化

離散的なGAができる vcopt().dcGA() を用います。para_range は各遺伝子が取り得る [0, 1] という選択肢が13個並んだ2次元配列です。評価関数はペナルティを返すため、評価値0を目指します。

#===============================================
# GA
#===============================================
#para_range
para_range = [[i for i in range(2)] for j in range(para_num)]
print('para_range\n{}'.format(para_range))

#GA
para, score = vcopt().dcGA(para_range,              #パラメータ範囲
                           score,                   #評価関数
                           0,                       #目標値
                           show_pool_func='print')  #表示オプション

#GA後のテント配列
tent[mask_candidate] = para
print('tent\n{}'.format(tent))
para_range
[[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1]]
___________________ info ___________________
para_range : n=13
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 130
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 130/130        
gen=0, best_score=3.0, mean_score=15.6385, mean_gap=15.6385, time=0.0
gen=130, best_score=3.0, mean_score=12.4154, mean_gap=12.4154, time=0.1
gen=260, best_score=3.0, mean_score=9.8231, mean_gap=9.8231, time=0.1
gen=390, best_score=3.0, mean_score=8.1615, mean_gap=8.1615, time=0.1
gen=520, best_score=3.0, mean_score=6.8, mean_gap=6.8, time=0.2
gen=650, best_score=3.0, mean_score=5.6615, mean_gap=5.6615, time=0.2
gen=780, best_score=0.0, mean_score=4.8077, mean_gap=4.8077, time=0.3
__________________ results _________________
para : [0 1 1 0 0 0 0 0 1 1 1 0 0]
score : 0.0
____________________ end ___________________
tent
[[0 0 0 1 0]
 [1 0 0 0 0]
 [0 0 0 0 0]
 [0 0 1 0 1]
 [1 0 0 0 0]]

あっという間にペナルティ0になりました。解答と一致したでしょうか?

10*10の問題

次の問題です。

#============================
# パズル
#============================
pazzle = ['-t------t-',
          't----t----',
          '--------t-',
          '-tt-------',
          '----------',
          '-t---t----',
          'tt--t-t--t',
          '-----t----',
          't-------t-',
          '---t---t-t']
horizontal = [4,1,2,1,3,1,3,0,2,3]
vertical = [3,0,2,2,0,5,0,4,0,4]
___________________ info ___________________
para_range : n=47
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 470
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 470/470        
gen=0, best_score=31.0, mean_score=54.3681, mean_gap=54.3681, time=0.1
gen=470, best_score=29.0, mean_score=48.4021, mean_gap=48.4021, time=0.4
...
gen=9400, best_score=2.0, mean_score=5.6234, mean_gap=5.6234, time=3.1
gen=9870, best_score=0.0, mean_score=4.9298, mean_gap=4.9298, time=3.3
__________________ results _________________
para : [1 1 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0
 0 0 0 0 0 1 0 1 1 1]
score : 0.0
____________________ end ___________________
tent
[[1 0 1 0 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 1 0 0 0 1]
 [1 0 0 1 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0]
 [1 0 1 0 1 0 1 0 0 1]
 [0 0 0 0 0 0 0 0 0 0]
 [0 1 0 0 1 0 1 0 1 0]
 [0 0 0 0 0 0 0 0 0 0]
 [1 0 0 0 1 0 1 0 1 0]]

3.3秒で解けました。

18*18の問題

大きなサイズに挑戦します。

#============================
# パズル
#============================
pazzle = ['---tt-----t-------',
          't-------tt---t--t-',
          't-----------t-t---',
          '-----t---t--------',
          '--t-t--------tt---',
          '-----t----------t-',
          '--t--t----t--t---t',
          '------t-t-t-----t-',
          '-tt---t-----t-----',
          '---t----t--t--t---',
          '---------t------t-',
          '------t--t------t-',
          '-t------------t---',
          '--t-t---t-----t---',
          '-----------t------',
          '---tt--t---------t',
          't-----------t-----',
          '----t-tt-t---tt-t-']
horizontal = [3,4,2,5,2,6,2,2,6,2,4,3,3,4,1,5,2,5]
vertical = [5,3,4,2,4,3,4,3,4,2,5,0,6,1,2,5,0,8]

___________________ info ___________________
para_range : n=159
score_func : <class 'function'>
aim : 0.0
show_pool_func : 'print'
seed : None
pool_num : 1590
max_gen : None
core_num : 1 (*vcopt, vc-grendel)
___________________ start __________________
Scoring first gen 1590/1590        
gen=0, best_score=119.0, mean_score=161.6346, mean_gap=161.6346, time=1.3
gen=1590, best_score=112.0, mean_score=149.8025, mean_gap=149.8025, time=2.4
...
gen=151050, best_score=2.0, mean_score=2.073, mean_gap=2.073, time=98.1
gen=152640, best_score=0.0, mean_score=2.0415, mean_gap=2.0415, time=98.9
__________________ results _________________
para : [1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1
 0 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1
 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0
 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0
 0 0 0 1 1 1 1 1 1 1 1]
score : 0.0
____________________ end ___________________
tent
[[1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0]
 [0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1]
 [0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0]
 [0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0]
 [0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1]
 [0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1]
 [0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0]
 [0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
 [0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 1]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [1 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0]
 [0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0]
 [0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1]]

99秒で解けました。これくらいのサイズだと成功率が低いので、pool_numオプションで個体数を増やしても良いかもしれません。

まとめ

GAはざっくり解法なので、論理的なパズルは苦手な傾向があります。実は数独もやってみたのですが非常に相性が悪かったです。GAでなくて、素直に論理的なプログラムを書いたほうが良いです。

タイトルとURLをコピーしました