pyzzle

---

はじめに

スケルトンパズルの自動生成ライブラリpyzzleを紹介します。
ここでは簡単な使い方の説明にとどめ， ライブラリの拡張等については別途解説を用意します。

インストール方法

本ライブラリをインストールする方法はいくつかあります。

1. PyPIを用いたインストール

    pip install pyzzle

2. Anacondaを用いたインストール（未対応）

    conda install pyzzle

3. GitHubを用いたインストール

    git clone https://github.com/puzzle-japan/pyzzle.git
    cd pyzzle
    python setup.py install

辞書の用意

パズルに配置する単語のリストをtxt形式で生成します。
なお， pyzzleで予め用意されている辞書を用いる場合は， この手順を飛ばしてください。

animal.txt
アイアイ
アイベックス
アカカンガルー
アカギツネ
アカクビワラビー

なお， 単語に重み（点数）をつける場合は， 以下のように生成します。

animal_ww.txt
アイアイ 10
アイベックス 2
アカカンガルー 50
アカギツネ 20
アカクビワラビー 70

重みを設定することにより， より重みのある単語が優先的にパズルに配置されるようになります。

パズル生成

必要ライブラリのインポート

import sys

import numpy as np

sys.path.append("../") # ライブラリインストール後は削除
from pyzzle import Puzzle, FancyPuzzle, Dictionary

変数設定

• width : パズルの横幅
• height : パズルの縦幅
• seed : 乱数のシード値

width = 15
height = 15
seed = 1

# 乱数設定
np.random.seed(seed=seed)

Puzzleインスタンスの生成

Puzzleクラスは， 生成するパズルのメインオブジェクトです。
初期化時には横幅と縦幅を指定します。
任意の形状の盤面を作成する場合は， 別ドキュメントで紹介するFancyPuzzleクラスを用います。

puzzle = Puzzle(width, height)

Dictionaryインスタンスの生成

パズルに配置する単語リストとして， Dictionaryクラスを使用します。このクラスは事前に用意した辞書ファイルに基づき， 重複単語や不要単語の消去， 自動的に重みを算出するなど， 単語リスト全般の処理に携わります。

1. 自作の辞書を用いる場合

自作の辞書を用いる場合は， 辞書ファイルのパスを引数に与えます：

dic = Dictionary("../dict/pokemon.txt")

2. pyzzleが用意した辞書を用いる場合

pyzzleにはデフォルトで複数の辞書が用意されています。
これらの辞書にアクセスする場合は， Dictionary.datasetを用います。
用意されている辞書のリストはDictionary.dataset.dict_listから一覧を参照できます。

print(Dictionary.dataset.dict_list)

['pokemon', 'r10000', 'pokemon_ww', 'shiga', 'nagasaki', 'kotowaza', 'saga', 'yamagata', 'cats', 'ehime', 'gihu', 'fukuoka', 'sports', 'typhoon', 'okinawa', 'fukui', 'saitama', 'fishes', 'chiba', 'okayama', 'yamanashi', 'fukishima', 'shizuoka', 'akita', 'osaka', 'hokkaido', 'r100000', 'pokemon_kanto', 'animals', 'tochigi', 'ibaraki', 'ooita', 'western_color', 'fruit-vegetable_english', 'aomori', 'instrument_japanese', 'ishikawa', 'kagoshima', 'mie', 'birds', 'dinosaurs', 'tottori', 'hyogo', 'fruit-vegetable_japanese', 'kumamoto', 'miyagi', 'countries', 'kyoto', 'shimane', 'toyama', 'hiroshima', 'yamaguchi', 's_and_p100', 'wakayama', 'kagawa', 'nigata', 'tokyo', 'logo', 'instrument_english', 'iwate', 'miyazaki', 'tokushima', 'kochi', 'shanghai_exe', 'nara', 'prefectures', 'kanagawa', 'nagano', 'color', 'gunma', 'aichi']

例えばpokemonを使う場合， 次のように初期化します：

dic = Dictionary.dataset.pokemon

辞書の中身を確認する

辞書に載っている単語リストは， wordから参照可能です。 今回はwordの先頭10個の要素を確認してみます：

print(dic.word[:10])

['フシギダネ', 'フシギソウ', 'フシギバナ', 'ヒトカゲ', 'リザード', 'リザードン', 'ゼニガメ', 'カメール', 'カメックス', 'キャタピー']

Puzzleインスタンスに辞書をインポートする

Puzzleインスタンスはパズル生成にDictionaryインスタンスを用います。
そのために， PuzzleインスタンスにDictionaryインスタンスをimport_dictメソッドによりインポートする必要があります。
これにより， パズル生成に使う単語群を知ることができます。

puzzle.import_dict(dic)

初期解の生成

まずは， 初期解を生成します。
初期解の生成にはfirst_solveメソッドを使用します。

初期解の生成は次のアルゴリズムに沿って行います：

1. ランダムに単語を配置する
2. 既に配置されている単語に接続可能な単語をランダムに配置する
3. 2を繰り返し， 辞書にある単語の中から最大限まで単語を敷き詰める

なお， first_solveメソッドは一度しか使えません。再び初期解を取得する場合は， 先にreinitメソッドを使用する必要があります。

puzzle.first_solve()
puzzle.show() # 結果の確認

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ				ア		ジ			フ
1	ズ		ツ	タ	ー	ジ	ャ			ク	ロ	バ	ッ	ト
2	パ				ボ		ノ	ク	タ	ス		ニ		リ
3	ス	バ	メ				ビ			ロ		プ		デ
4		ン		マ	シ	ェ	ー	ド		ー		ッ		プ
5		ギ	ア	ル				ッ				チ		ス
6		ラ		ノ		カ		コ	ロ	モ	リ				イ
7	ハ	ス	ボ	ー		プ	テ	ラ			ー				ベ
8				ム		・		ー			シ		グ		ル
9		ム				コ					ャ		ラ	ッ	タ
10		ッ		ア	ー	ケ	ン		チ	ョ	ン	チ	ー		ル
11		ク	ラ	ブ		コ		リ					ド
12		ル		リ				ン		ワ	シ	ボ	ン
13				ボ				グ			シ
14		メ	タ	ン	グ		ア	マ	マ	イ	コ

初期解を改善する

• pyzzleでは，パズルの良し悪しを決定するために目的関数(objective function）を使用します。これについてはすぐに紹介します。
• pyzzleにおけるパズル生成は， ランダムに作成された初期状態のパズルを出発点とし， 新たにランダム生成されるパズルとパズルの良し悪しを比較し， より良いパズルを選択するというプロセスを繰り返して美しいパズルを作り上げていきます。その際に必要になるのが最適化関数（optimizer）です。このクラスについては後ほど改めて紹介します。

目的関数（ObjectiveFunction）を登録する

パズルの良し悪しを定量化するための目的関数について紹介します。
「良いパズル」とはどういうパズルでしょう？ その答えは， おそらく無数にあることでしょう。
ここではpyzzleが提供する複数の指標を紹介します。

目的関数名	意味
weight	重みの合計
nwords	パズルに使われた語数
cross_count	単語同士の交差マス数
fill_count	パズル全体の文字マス数
max_connected_empties	空マスの最大連結数
difficulty	パズルの難易度
ease	パズルの容易度
circulation	循環（別ドキュメントで解説）

なお， difficultyとeaseは反対の関係で， 目的に応じて使い分けます。
pyzzleではこれらの目的関数に加え， 自ら定義した目的関数の拡張にも対応しています。
具体的な実装方法については， 別のドキュメントを参照してください。

これらのうち，好みの目的関数を優先順位順にリスト化したものを用意しましょう。 例えば， 下の実装ではweightが最優先され， 次にnwordsが優先されます。

obj_func = [
    "weight",
    "nwords", 
    "cross_count", 
    "fill_count", 
    "max_connected_empties", 
    "difficulty"
]

最適化手法（Optimizer）

初期解の改善には，設定された目的関数と最適化手法に基づき解の改善を行います。
解の改善手法としてoptimizerを指定します。

pyzzleでは， ランダムに初期化されたパズル（初期解）を出発点とし， そのパズルを改善していくことで美しいパズルを生成します。
では， パズルの「改善」はどのように行うのでしょうか？ このような問題を「組み合わせ最適化問題」と呼びます。
pyzzleでは， いくつかの最適化手法を提供します。

指定子	最適化手法名
local_search	局所探索法

ここでは最も基本的な手法として， 数ある最適化手法の中から「局所探索法」を紹介します。 これは、組み合わせ最適化問題を解く近似解法として代表的なものです。 局所探索法について簡単に解説します。
まず， ランダムに初期化されたパズルを「初期解」とします。次に， 解空間（全てのパズルの解を含む多次元空間）の中で， 初期解の近傍領域に存在する「近傍解」を探します。 近傍解とは、初期解に似ている（解空間において距離の近い）解を意味します。よって、近傍解は初期解を元に得ることができます。
ある手順を踏むことで近傍解が得られたら， 初期解の目的関数値と近傍解の目的関数値を比較します。目的関数値はパズルの良し悪しの指標ですので， 目的関数値から良いパズルと判断された方を新たな解とします（近傍解が必ずしも初期解よりも良いとは限りません）。
このプロセスを繰り返すことで， 初期解の改善を行う手法を「局所探索法」と呼びます。初期解が既に十分良い解だった場合， あまり改善せずとも良いパズルが得られたりします。改悪することはありません。

pyzzleにおける「近傍解」の定義は最適化手法にもよりますが， local_searchにおいては次の手順で近傍解を取得しています：

1. 既存のパズルに配置された単語をランダムに取り除く(drop)
2. 単語の連結性が崩れるまで繰り返し， 1つだった単語の島が2つ以上の島に分離したら単語のdropをストップする(collapse)
3. 最も面積の大きい島だけを残して， それ以外の島を盤面から取り除く(kick)
4. 大きい島だけを残した状態から， 再びパズルを完成させる

これがlocal_searchにおける近傍解の取得プロセスです。
最適化手法の拡張には， このライブラリを十分に理解している必要があります。これについては， 別ドキュメントを参照してください。

epochの指定

局所探索法では，解の改善を試みる回数としてepochを指定します。
解の改善が行われた場合も行われなかった場合もepoch1回分としてカウントされます。

puzzle.solve(epoch=10, optimizer="local_search", objective_function=obj_func)

>>> Interim solution

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ				ア		ジ			フ
1	ズ		ツ	タ	ー	ジ	ャ			ク	ロ	バ	ッ	ト
2	パ				ボ		ノ	ク	タ	ス		ニ		リ
3	ス	バ	メ				ビ			ロ		プ		デ
4		ン		マ	シ	ェ	ー	ド		ー		ッ		プ
5		ギ	ア	ル				ッ				チ		ス
6		ラ		ノ		カ		コ	ロ	モ	リ				イ
7	ハ	ス	ボ	ー		プ	テ	ラ			ー				ベ
8				ム		・		ー			シ		グ		ル
9		ム				コ					ャ		ラ	ッ	タ
10		ッ		ア	ー	ケ	ン		チ	ョ	ン	チ	ー		ル
11		ク	ラ	ブ		コ		リ					ド
12		ル		リ				ン		ワ	シ	ボ	ン
13				ボ				グ			シ
14		メ	タ	ン	グ		ア	マ	マ	イ	コ

>>> Epoch 1/10
    - Improved: [  0.         33.         33.        110.        202.          0.2265625] --> [  0.          36.          36.         113.         202.
   0.22857143]

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ				ア		ジ			フ			ズ
1	ズ		ツ	タ	ー	ジ	ャ			ク	ル	ミ	ル		ブ
2	パ				ボ		ノ	ク	タ	ス			ッ		ル
3	ス	バ	メ				ビ			ロ		リ	グ	レ	ー
4		ン		マ	シ	ェ	ー	ド		ー		オ
5		ギ	ア	ル				ッ				ル	リ	リ
6		ラ		ノ		カ		コ	ロ	モ	リ				イ
7	ハ	ス	ボ	ー		プ	テ	ラ			ー				ベ
8				ム		・		ー			シ		グ		ル
9		ム				コ					ャ		ラ	ッ	タ
10		ッ		ア	ー	ケ	ン		チ	ョ	ン	チ	ー		ル
11		ク	ラ	ブ		コ		リ					ド
12		ル		リ				ン		ワ	シ	ボ	ン
13				ボ				グ			シ
14		メ	タ	ン	グ		ア	マ	マ	イ	コ

>>> Epoch 2/10
    - Stayed: [  0.          36.          36.         113.         202.
   0.22857143]
>>> Epoch 3/10
    - Stayed: [  0.          36.          36.         113.         202.
   0.22857143]
>>> Epoch 4/10
    - Stayed: [  0.          36.          36.         113.         202.
   0.22857143]
>>> Epoch 5/10
    - Improved: [  0.          36.          36.         113.         202.
   0.22857143] --> [  0.          37.          37.         117.         212.
   0.22916667]

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ				ア		ジ			フ			ズ
1	ズ		ツ	タ	ー	ジ	ャ			ク	ル	ミ	ル		ブ
2	パ				ボ		ノ	ク	タ	ス			ッ		ル
3	ス	バ	メ				ビ			ロ		リ	グ	レ	ー
4		ン		マ	シ	ェ	ー	ド		ー		オ
5		ギ	ア	ル				ッ				ル	リ	リ
6		ラ		ノ		カ		コ	ロ	モ	リ				イ
7	ハ	ス	ボ	ー		プ	テ	ラ			ー				ベ
8	ピ			ム		・		ー			シ		グ		ル
9	ナ	ゲ	キ			コ					ャ		ラ	ッ	タ
10	ス			ア	ー	ケ	ン		チ	ョ	ン	チ	ー		ル
11				ブ		コ		リ					ド
12	キ	リ	ン	リ	キ			ン		ワ	シ	ボ	ン
13				ボ				グ			シ
14		メ	タ	ン	グ		ア	マ	マ	イ	コ

>>> Epoch 6/10
    - Improved: [  0.          37.          37.         117.         212.
   0.22916667] --> [  0.          38.          38.         117.         197.
   0.31531532]

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ				ア		ジ			フ			ズ
1	ズ		ツ	タ	ー	ジ	ャ			ク	ル	ミ	ル		ス
2	パ				ボ		ノ	ク	タ	ス			ッ		リ
3	ス	バ	メ				ビ			ロ		リ	グ	レ	ー
4		ン		マ	シ	ェ	ー	ド		ー		オ			プ
5		ギ	ア	ル				ッ				ル	リ	リ
6		ラ		ノ		ク		コ	ロ	モ	リ				イ
7	ハ	ス	ボ	ー		ラ		ラ			ー				ベ
8	ピ			ム		ブ	ル	ー			シ		グ		ル
9	ナ	ゲ	キ								ャ		ラ	ッ	タ
10	ス					ゴ			チ	ョ	ン	チ	ー		ル
11				コ	コ	ロ	モ	リ					ド
12	ア	メ	タ	マ		ン		ン		ワ	シ	ボ	ン
13				タ		ダ		グ			シ
14		マ	イ	ナ	ン		ア	マ	マ	イ	コ

>>> Epoch 7/10
    - Stayed: [  0.          38.          38.         117.         197.
   0.31531532]
>>> Epoch 8/10
    - Replaced(same score): [  0.          38.          38.         117.         197.
   0.31531532] -> [  0.          38.          38.         117.         197.
   0.31531532]

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ		キ				ジ			フ			ズ
1	ズ		ャ		ヒ		ャ			ク	ル	ミ	ル		ス
2	パ		モ		ト		ノ	ク	タ	ス			ッ		リ
3	ス	バ	メ		モ		ビ			ロ		リ	グ	レ	ー
4		ン		マ	シ	ェ	ー	ド		ー		オ			プ
5		ギ	ア	ル				ッ				ル	リ	リ
6		ラ		ノ		ク		コ	ロ	モ	リ				イ
7	ハ	ス	ボ	ー		ラ		ラ			ー				ベ
8	ピ			ム		ブ	ル	ー			シ		グ		ル
9	ナ	ゲ	キ								ャ		ラ	ッ	タ
10	ス					ゴ			チ	ョ	ン	チ	ー		ル
11				コ	コ	ロ	モ	リ					ド
12	ア	メ	タ	マ		ン		ン		ワ	シ	ボ	ン
13				タ		ダ		グ			シ
14		マ	イ	ナ	ン		ア	マ	マ	イ	コ

>>> Epoch 9/10
    - Stayed: [  0.          38.          38.         117.         197.
   0.31531532]
>>> Epoch 10/10
    - Improved: [  0.          38.          38.         117.         197.
   0.31531532] --> [  0.          39.          39.         117.         197.
   0.31578947]

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0	ノ		キ				ジ	ュ	ゴ	ン
1	ズ		ャ		ヒ		ャ		ン		キ		リ	オ	ル
2	パ		モ		ト		ノ		ベ	ベ	ノ	ム		タ
3	ス	バ	メ		モ		ビ				コ		ゴ	チ	ム
4		ン		マ	シ	ェ	ー	ド		ヒ	コ	ザ	ル
5		ギ	ア	ル				ッ					ー
6		ラ		ノ		ク		コ	ロ	モ	リ		グ		イ
7	ハ	ス	ボ	ー		ラ		ラ			ー				ベ
8	ピ			ム		ブ	ル	ー			シ		グ		ル
9	ナ	ゲ	キ								ャ		ラ	ッ	タ
10	ス					ゴ			チ	ョ	ン	チ	ー		ル
11				コ	コ	ロ	モ	リ					ド
12	ア	メ	タ	マ		ン		ン		ワ	シ	ボ	ン
13				タ		ダ		グ			シ
14		マ	イ	ナ	ン		ア	マ	マ	イ	コ

唯一解かどうかを判定する

スケルトンパズルは， 必ずしも唯一解とは限りません。
例えば以下のパズルでは「アイアイ」と「アンザイ」が入れ替え可能です。

ア	イ	ア	イ
ン			ン
ザ			ド
イ	ス

生成されたパズルが唯一解かどうかはis_uniqueプロパティを参照することで確認できます。 唯一解である場合はTrue, 複数解が存在する場合は， 入れ替え可能な単語を示してFalseを返します。
唯一解でなかった場合は， さらにsolveすることで， 複数回を回避できる可能性があります。

puzzle.is_unique

True

パズルの改善履歴を確認する

パズルの改善過程において， それぞれの目的関数値がどのような変化を辿ったのかという情報はlogプロパティに保存されています。

puzzle.log

	weight	nwords	cross_count	fill_count	max_connected_empties	difficulty
0	0.0	33.0	33.0	110.0	202.0	0.226562
1	0.0	36.0	36.0	113.0	202.0	0.228571
2	0.0	36.0	36.0	113.0	202.0	0.228571
3	0.0	36.0	36.0	113.0	202.0	0.228571
4	0.0	36.0	36.0	113.0	202.0	0.228571
5	0.0	37.0	37.0	117.0	212.0	0.229167
6	0.0	38.0	38.0	117.0	197.0	0.315315
7	0.0	38.0	38.0	117.0	197.0	0.315315
8	0.0	38.0	38.0	117.0	197.0	0.315315
9	0.0	38.0	38.0	117.0	197.0	0.315315
10	0.0	39.0	39.0	117.0	197.0	0.315789

さらに， これをepochの時系列として表示するためのshow_logメソッドが用意されています。

puzzle.show_log()

array([<matplotlib.axes._subplots.AxesSubplot object at 0x125399390>,
       <matplotlib.axes._subplots.AxesSubplot object at 0x1264fdb90>,
       <matplotlib.axes._subplots.AxesSubplot object at 0x12547bc10>,
       <matplotlib.axes._subplots.AxesSubplot object at 0x12642cd50>,
       <matplotlib.axes._subplots.AxesSubplot object at 0x126457e90>,
       <matplotlib.axes._subplots.AxesSubplot object at 0x125985fd0>],
      dtype=object)

解の履歴を遡る

Puzzleオブジェクトには， これまでの単語の出し入れが全て記録されています。
一つ一つの動作に対して順番に「履歴番号」が振られています（エポック番号ではありません）。
これを遡ることで， どのような経路を辿ってパズルが生成されたかを確認することができます。
そのためのメソッドの一覧を次に示します：

メソッド名	機能
jump	引数で指定された履歴番号に移動する
get_prev	一つ前の履歴番号に移動する
get_next	一つ後の履歴番号に移動する
get_latest	最新の履歴番号に移動する

それでは， 初期解生成時， 最初に置かれた単語を確認してみます。
履歴番号0は何も単語が置かれていない状態を表すので， この場合は履歴番号に1を指定します。
以下の履歴番号を変えたりしながら， 解の履歴を辿ってみてください。

puzzle.jump(1).show()

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
0							ジ
1							ャ
2							ノ
3							ビ
4							ー
5
6
7
8
9
10
11
12
13
14

パズルの保存

生成されたパズル画像を問題と解答に分けて保存しましょう。
Puzzleクラスには画像を保存するためのsave_problem_imageメソッドとsave_answer_imageメソッドが用意されています。
また， 完成したパズル情報をjson形式で出力するためのexport_jsonメソッドも用意されています。

puzzle.get_latest()

oname = f"{dic.name}_w{width}_h{height}_r{seed}.png"
puzzle.save_problem_image(f"fig/problem_{oname}")
print(f"Save as 'fig/problem_{oname}'")

puzzle.save_answer_image(f"fig/answer_{oname}")
print(f"Save as 'fig/problem_{oname}'")

puzzle.export_json(f"json/{oname[:-4]}.json")
print(f"Save as 'json/{oname[:-4]}.json'")

Save as 'fig/problem_pokemon_w15_h15_r1.png'
Save as 'fig/problem_pokemon_w15_h15_r1.png'
Save as 'json/pokemon_w15_h15_r1.json'

保存された画像を確認してみましょう。

from IPython.display import Image
Image(f"fig/answer_{oname}")

Puzzleオブジェクトのpickle化

pyzzleでは， Puzzleオブジェクトのpickle化をサポートしています。
これにより， 生成過程のパズルや目的間数値のログや解の軌跡をいつでも確認することができ， 他人と共有することもできます。

puzzle.to_pickle(f"pickle/{oname[:-4]}.pickle")
print(f"pickle/{oname[:-4]}.pickle")

pickle/pokemon_w15_h15_r1.pickle

pickle化されたPuzzleオブジェクトをオープンしてみましょう：

import pickle
with open(f"pickle/{oname[:-4]}.pickle", "rb") as f:
    puzzle_pickled = pickle.load(f)
puzzle_pickled.log

	weight	nwords	cross_count	fill_count	max_connected_empties	difficulty
0	0.0	33.0	33.0	110.0	202.0	0.226562
1	0.0	36.0	36.0	113.0	202.0	0.228571
2	0.0	36.0	36.0	113.0	202.0	0.228571
3	0.0	36.0	36.0	113.0	202.0	0.228571
4	0.0	36.0	36.0	113.0	202.0	0.228571
5	0.0	37.0	37.0	117.0	212.0	0.229167
6	0.0	38.0	38.0	117.0	197.0	0.315315
7	0.0	38.0	38.0	117.0	197.0	0.315315
8	0.0	38.0	38.0	117.0	197.0	0.315315
9	0.0	38.0	38.0	117.0	197.0	0.315315
10	0.0	39.0	39.0	117.0	197.0	0.315789