ドミノを用いたパズルの自動生成
概要
ドミノはトランプと同じくそれひとつでいろいろなゲームを楽しむことができる玩具のひとつである．本記事では，ドミノを用いたパズルの自動生成の手法とサンプルコードを紹介する．
準備
1セットのドミノは28枚の牌からなる*1．それぞれの牌は2つの領域それぞれに0～6のスートのうちいずれかが描かれており，すべての牌のスートの組み合わせが異なっている．
日本ではドミノの遊び方が広く知られているとはいいがたく*2，遊び相手を見つけるにも苦労する状況である．そこで，トランプのソリティアのように，ドミノを使って一人でも遊べるパズルを紹介しよう．次にパズルの例題を掲載する．
ドミノの牌をこの図の通りに並べることができればパズルはクリアとなる．ただし，2, 3, 6の目については目の向きが区別される．そのほかのスートの目の向きは区別しない．例題の解を以下に示す．
このように，問題さえ用意できればパズルで遊ぶことができる．しかしながら，問題を作るために牌を並べていたのではその過程で答えを知ることになってしまう．したがって，本当に一人で遊ぶつもりなら問題を自動生成する必要がある．そこで本記事ではパズルを自動生成し，解の存在を保証する手法と実際にパズルを自動生成して遊べるサンプルコードを紹介する．
問題の自動生成
パズルは長方形とし，その横の大きさを，縦の大きさを
とする．問題の自動生成とはすなわち
枚の牌をこの長方形に敷き詰めることである．ただし，
と
のうち少なくとも一方は偶数でなければならない．
ここで，パズルに用いるスートの種類数と使用できる牌の枚数，被覆できるマスの最大数を表にまとめる．例えば，種類のスート (例えば，0, 1, 2, 4, 5の5種類) を用いたパズルを作成する場合，使用できる牌は
枚であるから，
でなければならない．さもなければ，牌が足りなくなってしまう．
| スートの種類の数 | 牌の枚数 | マスの数 |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 3 | 6 |
| 3 | 6 | 12 |
| 4 | 10 | 20 |
| 5 | 15 | 30 |
| 6 | 21 | 42 |
| 7 | 28 | 56 |
次に，未完成のパズルの盤面に座標を導入しよう．最も左上にあるマスを原点とし，その座標をとする．また，右方向に
座標，下方向に
座標をとる．
このパズルの盤面に1枚の牌を (2つのマスにまたがって) 横向きに置くとき，牌を置いた2つのマスのうち左側のマスをとすれば，右側のマスの座標は
と表せる．ここで，点
の原点からのマンハッタン距離
を考えると，
がわかる．
はいずれも整数であるから，
のうちいずれか一方は奇数，もう一方は偶数である．牌を縦向きに置く場合でも，同様にして牌を置いた2つのマスの原点からのマンハッタン距離のうちいずれか一方は奇数，もう一方は偶数であること，それらの差の絶対値が
であることがわかる．逆に，2つの相異なるマスが縦横に隣接していない場合は1枚の牌で同時に被覆することはできない．
以上のことから，ある2つのマスが1枚の牌で同時に被覆されうることは
であることと同値である．これに基づいて，反射的関係
を定義する．
盤面上のすべてのマスの集合を，原点からのマンハッタン距離が奇数であるマスの集合を
，原点からのマンハッタン距離が偶数であるマスの集合を
とする．明らかに，
である．また，1枚の牌で同時に被覆されうるマスの組の集合
を定義すると，すべての
について
のうちいずれか一方が奇数，もう一方が偶数であるから，
したがって，グラフ
は
を部集合とする二部グラフである．さらに，盤面のある位置に1枚の牌を (2つのマスにまたがって) 置くことを，その2つのマスに対応する
の辺を選択することに対応付ければ，盤面に牌を隙間なく敷き詰めることは
の完全マッチングを発見することと対応付けられる．
は二部グラフであるから，完全マッチングは増加道法により多項式時間で発見できる．牌を不祝儀敷きすることが完全マッチングの1つと対応しているので，完全マッチングは常に存在する．
mathtrain.jp
牌を置く位置が決まったら，よくシャッフルした牌をそれらの位置に置けばパズルの解が完成する．牌の目だけを表示し，牌の敷き方の情報を表示しないように設定すれば，解の存在が保証されたパズルの問題が完成する．
