すっかりご紹介が遅れてしまいましたが、id:koichik さんがこの手の問題にぴったりの Prolog を使って、状態遷移まで一気に解く試みをされています。すごいですね。エビちゃん、カワイイっすね…。
SHIMADA さんからもコメントをいただきました。
導いた組み合わせから状態遷移図を生成するところが一番興味があったんですが、なんと青木先生の回答にも載ってないんですよね〜。
そう、状態遷移図を作成する前に、もうワンステップくらい欲しいところなんですよね。どうして書いてないでしょうか。似たような方法で導けるから…だとしたら、そう書かれると思うんですが…。
ともあれ、Prolog のようにスマートにはいきませんが、状態遷移図のひとつ手前までいけるように、先のスクリプトを改変してみましょう。
| 構成 無効状態 可なら追加 補集合 可否 状態 移動 有効移動 状態１ 状態２ 遷移可能か |
構成 := #(人 狼 羊 菜).
無効状態 := #((狼 羊) (羊 菜) (狼 羊 菜)).
有効移動 := 構成 collect: [: 各々 | (Set with: #人) add: 各々; yourself].
状態 := OrderedCollection new.
可なら追加 := [: 集合 |
補集合 := 構成 reject: [: 要素 | 集合 includes: 要素].
可否 := {集合. 補集合} noneSatisfy: [: 各々 | 無効状態 includes: 各々].
可否 ifTrue: [状態 add: {補集合 copy. 集合 copy}]].
可なら追加 value: #().
(1 to: 構成 size) do: [: nn |
構成 combinations: nn atATimeDo: [: 組み合わせ | 可なら追加 value: 組み合わせ]].
World findATranscript: nil.
状態 combinations: 2 atATimeDo: [: 組み合わせ |
状態１ := 組み合わせ first.
状態２ := 組み合わせ second.
遷移可能か := 状態１ first includesAllOf: 状態２ first.
移動 := 状態１ first reject: [: 各々 | 状態２ first includes: 各々].
(遷移可能か and: [有効移動 includes: 移動 asSet]) ifTrue: [
Transcript cr.
Transcript show: 状態１.
Transcript show: ' <--[', 移動 printString, ']--> '.
Transcript show: 状態２]].
前のスクリプトでは、結果をコレクトしていなかったのでそうするように書き換えてから、同じ #combinations:atATimeDo: を使って、遷移が許される状態どうしの組み合わせを列挙してみました。
#((人 狼 羊 菜) ()) <--[#(人 羊)]--> #((狼 菜) (人 羊)) #((人 羊 菜) (狼)) <--[#(人 羊)]--> #((菜) (人 狼 羊)) #((人 羊 菜) (狼)) <--[#(人 菜)]--> #((羊) (人 狼 菜)) #((人 狼 菜) (羊)) <--[#(人) ]--> #((狼 菜) (人 羊)) #((人 狼 菜) (羊)) <--[#(人 狼)]--> #((菜) (人 狼 羊)) #((人 狼 菜) (羊)) <--[#(人 菜)]--> #((狼) (人 羊 菜)) #((人 狼 羊) (菜)) <--[#(人 狼)]--> #((羊) (人 狼 菜)) #((人 狼 羊) (菜)) <--[#(人 羊)]--> #((狼) (人 羊 菜)) #((人 羊) (狼 菜)) <--[#(人) ]--> #((羊) (人 狼 菜)) #((人 羊) (狼 菜)) <--[#(人 羊)]--> #(() (人 狼 羊 菜))
（ちょっと # だらけで読みにくかったので、不要な # は省きました）
ここまで情報が揃えば、あとは手でも書けそうです。もちろん、最後までスクリプトで…ということも可能だと思います。（こういうのは DNA コンピュータが得意そう…）
