カラー円盤パズルをPrologで解いてみる

暇だったのでカラー円盤パズルを勉強中のPrologを使って解いてみました。

カラー円盤パズルっていうのは写真みたいなやつです。接触する辺同士が同じく色になるように上手く組み合わせないといけないみたいです。

自分なりの解き方

こんな感じのコードになりました。

next(1, green, brown).
next(1, brown, white).
next(1, white, blue).
next(1, blue, black).
next(1, black, yellow).
next(1, yellow, green).

next(2, green, blue).
next(2, blue, yellow).
next(2, yellow, brown).
next(2, brown, white).
next(2, white, black).
next(2, black, green).

next(3, green, black).
next(3, black, blue).
next(3, blue, yellow).
next(3, yellow, brown).
next(3, brown, white).
next(3, white, green).

next(4, green, black).
next(4, black, brown).
next(4, brown, white).
next(4, white, blue).
next(4, blue, yellow).
next(4, yellow, green).

next(5, green, yellow).
next(5, yellow, blue).
next(5, blue, brown).
next(5, brown, black).
next(5, black, white).
next(5, white, green).

next(6, green, brown).
next(6, brown, black).
next(6, black, yellow).
next(6, yellow, white).
next(6, white, blue).
next(6, blue, green).

next(7, green, yellow).
next(7, yellow, black).
next(7, black, blue).
next(7, blue, white).
next(7, white, brown).
next(7, brown, green).

memberSub(X,[X|Y],Y).
memberSub(X,[Y|Z],[Y|W]) :- memberSub(X,Z,W).

puzzle(X1, X2, X3, X4, X5, X6, X7) :-
  memberSub(X1, [1,2,3,4,5,6,7], Z1),
  memberSub(X2, Z1, Z2),
  memberSub(X3, Z2, Z3),
  memberSub(X4, Z3, Z4),
  memberSub(X5, Z4, Z5),
  memberSub(X6, Z5, Z6),
  memberSub(X7, Z6, []),
  next(X1, green, C1),
  next(X1, C1, C2),
  next(X1, C2, C3),
  next(X1, C3, C4),
  next(X1, C4, C5),
  next(X1, C5, green),
  next(X2, L1, C1),
  next(X2, C1, L6),
  next(X3, L2, C2),
  next(X3, C2, L1),
  next(X4, L3, C3),
  next(X4, C3, L2),
  next(X5, L4, C4),
  next(X5, C4, L3),
  next(X6, L5, C5),
  next(X6, C5, L4),
  next(X7, L6, green),
  next(X7, green, L5).

まず、7つある円盤にそれぞれ1〜7の番号をふります。各円盤には六つの点があって、それぞれ別の色で塗られているので、

円盤その1は、greenの次にbrownがあって、brownの次にwhiteがあって、…、yellowの次にgreenがある。

という感じに、循環リストみたいなのを7つの円盤それぞれに用意。これで素材が揃いました。

次に、可能な組み合わせを考える述語puzzleを考えます。当然ですが、ボードの形の制約上、円盤を縦に一列に並べたりとかはできなくて、一個の円盤の周りを6つの円盤が取り囲むように並べるしかありません。そこで、中央の円盤をX1、周りを順番にX2〜X7という変数であらわします。問題は場所X1にあてはまるのは何番の円盤かということになるわけです。

円盤の組み合わせにはふたつの制約があります。

1. 同じ円盤は一度しか使えない。場所X2とX5に同じ円盤が嵌まるということはありえない(当然)
2. 接触する円盤同士は同じく色の点で繋がらなければならない

memberSubというのが1の条件を満たすための述語で、memberSub(X, Ys, Zs)はXがリストYsのメンバーでリストZsはYsからXをのぞいたものな時に真になります。X1は1〜7のどれかで、そこからX1をのぞいたもののどれかがX2で…、みたいな意味です。ちなみに、この述語はどっかからコピペしてきました。

後半のnextを羅列してるところが、2の条件の部分です。この円盤とこの円盤の接触している部分の色が同じで〜という内容をづらづらと列挙しています。ただし、そのままだと出来た解を60度回転したものも解になってしまうので、中央の円盤の緑色の位置だけは固定にしました。

というわけで、完成したのが上のコードです。同じような述語が並んでいて美しくないですが、思いのほかすんなり書けました。やっぱりPrologはこの手の問題に強いなぁと。