歪 で die さんが、Java の Graph Layout ライクな出力機能付き Gauche（Shiro さん作の Scheme の処理系）版 を 「人 狼 羊 菜」で公開してくださいました。
例によって、咀嚼のため直訳ぎみに翻訳。Sqeuak 3.8 + 日本語リソース（手順は こちら）+ ClosureCompiler（ちょー手抜きな手順は こちら）+ 変数に日本語を使えるようにするための超いーかげんパッチ（こちら）で動きます（って、環境が特殊杉！）。
| 初期状態 終了状態 終了？ 失敗パターン 失敗？ 出現済状態 済？ 遷移 |
初期状態 := #((人 狼 羊 菜) ()).
終了状態 := #(() (人 狼 羊 菜)).
終了？ := [: 状態 | 状態 = 終了状態].
失敗パターン := #((羊 菜) (狼 羊)).
失敗？ := [: 状態 |
失敗パターン anySatisfy: [: 失敗 |
状態 anySatisfy: [: 各々 | 各々 = 失敗]]].
出現済状態 := #().
済？ := [: 状態 |
出現済状態 anySatisfy: [: 出現済 | 状態 = 出現済]].
World findATranscript: nil.
Transcript clear.
遷移 := nil.
遷移 := [: 状態 : 戻り？ : 直前の状態 |
| こっち あっち 正規化 〜と渡る 状態表示 |
こっち := 戻り？ ifTrue: [状態 second] ifFalse: [状態 first].
あっち := 戻り？ ifTrue: [状態 first] ifFalse: [状態 second].
正規化 := [: 状態’ | 戻り？ ifTrue: [状態’ reverse] ifFalse: [状態’]].
〜と渡る := [: 同行者 |
正規化 value:
{ こっち reject: [: 各々 | (各々 = 同行者) or: [#人 = 各々]].
#(人), (同行者 = #人 ifTrue: [あっち] ifFalse: [({同行者}, あっち) sort])}].
状態表示 := [: 移動前 : 移動後 |
Transcript cr;
show: '#', (移動前 printString copyWithout: $#);
show: ' -> ';
show: '#', (移動後 printString copyWithout: $#)].
true
caseOf: {
[失敗？ value: 状態] -> [].
[済？ value: 状態] -> [状態表示 value: 直前の状態 value: 状態]}
otherwise:
[ 状態表示 value: 直前の状態 value: 状態.
(終了？ value: 状態) ifTrue: [
状態表示 value: 状態 value: #終了].
出現済状態 := {状態}, 出現済状態.
こっち collect: [: 各々 | 遷移 value: (〜と渡る value: 各々) value: (戻り？ not) value: 状態]]].
遷移 value: 初期状態 value: false value: #開始#開始 -> #((人 狼 羊 菜) ()) #((人 狼 羊 菜) ()) -> #((狼 羊 菜) (人)) #((狼 羊 菜) (人)) -> #((人 狼 羊 菜) ()) #((人 狼 羊 菜) ()) -> #((狼 菜) (人 羊)) #((狼 菜) (人 羊)) -> #((人 狼 菜) (羊)) #((人 狼 菜) (羊)) -> #((狼 菜) (人 羊)) #((人 狼 菜) (羊)) -> #((菜) (人 狼 羊)) #((菜) (人 狼 羊)) -> #((人 狼 菜) (羊)) #((菜) (人 狼 羊)) -> #((人 羊 菜) (狼)) #((人 羊 菜) (狼)) -> #((菜) (人 狼 羊)) #((人 羊 菜) (狼)) -> #((羊) (人 狼 菜)) #((羊) (人 狼 菜)) -> #((人 羊) (狼 菜)) #((人 羊) (狼 菜)) -> #((羊) (人 狼 菜)) #((人 羊) (狼 菜)) -> #(() (人 狼 羊 菜)) #(() (人 狼 羊 菜)) -> #終了 #(() (人 狼 羊 菜)) -> #((人) (狼 羊 菜)) #((人) (狼 羊 菜)) -> #(() (人 狼 羊 菜)) #(() (人 狼 羊 菜)) -> #((人 羊) (狼 菜)) #((羊) (人 狼 菜)) -> #((人 狼 羊) (菜)) #((人 狼 羊) (菜)) -> #((羊) (人 狼 菜)) #((人 狼 羊) (菜)) -> #((狼) (人 羊 菜)) #((狼) (人 羊 菜)) -> #((人 狼 羊) (菜)) #((狼) (人 羊 菜)) -> #((人 狼 菜) (羊)) #((羊) (人 狼 菜)) -> #((人 羊 菜) (狼)) #((人 狼 菜) (羊)) -> #((狼) (人 羊 菜)) #((狼 菜) (人 羊)) -> #((人 狼 羊 菜) ())
他方で nurse さんも、Ruby を使用し、また違ったアプローチにて解を得ておられます（mixi から はてな のほうにリンクを貼り替えました）。こちらも直訳ぎみに…（ただし個人的な趣味で、メソッドの変わりにブロックを使用）。
| cmp trans1 trans2 result |
cmp := [: aa : bb |
| count break |
count := 0.
break := false.
(1 to: aa size) do: [: ii |
(aa at: ii) = (bb at: ii) ifFalse: [
break ifFalse: [
(count ~= 0 and: [count := count * 2. true]) ifTrue: [break := true] ifFalse: [
count := ((aa at: ii) - (bb at: ii)) sign]]]].
count].
trans1 := trans2 := nil.
trans1 := [: stack : answer |
((0 to: 7) collect: [: xx |
{(xx bitAnd: 4) >> 2. (xx bitAnd: 2) >> 1. (xx bitAnd: 1)}])
do: [: state |
(state second = 0 and: [state first = 0 or: [state third = 0]]) ifFalse: [
| diff |
diff := cmp value: state value: stack last.
((diff = 0 and: [(stack atWrap: -1) ~= state])
or: [diff = 1 and: [(stack includes: state) not]]) not ifFalse: [
state = #(1 1 1)
ifTrue: [answer add: (stack copyWith: state)]
ifFalse: [trans2 value: (stack copyWith: state) value: answer]]]].
answer].
trans2 := [: stack : answer |
((0 to: 7) collect: [: xx |
{(xx bitAnd: 4) >> 2. (xx bitAnd: 2) >> 1. (xx bitAnd: 1)}])
do: [: state |
| diff |
(state second ~= 0 and: [state first ~= 0 or: [state third ~= 0]]) ifFalse: [
diff := cmp value: state value: stack last.
((diff = 0 and: [(stack atWrap: -1) ~= state])
or: [diff = -1 and: [(stack includes: state) not]]) not ifFalse: [
trans1 value: (stack copyWith: state) value: answer]]].
answer].
result := trans1 value: #((0 0 0)) value: OrderedCollection new.
World findATranscript: nil.
result do: [: xx | Transcript cr; show: xx]||<
>||
#(#(0 0 0) #(0 1 0) #(0 1 0) #(0 1 1) #(0 0 1) #(1 0 1) #(1 0 1) #(1 1 1))
#(#(0 0 0) #(0 1 0) #(0 1 0) #(1 1 0) #(1 0 0) #(1 0 1) #(1 0 1) #(1 1 1))#人はかならず移動するため、各状態を表わす配列から外してよいということで、要素は三つです。それぞれ #狼 #羊 #菜 に対応して、0/1 で対岸に渡った状態かを示しています（たぶん(^_^;)）。連続して同じ状態の時は、人だけ移動した場合ですね。あえて #(人 狼 羊 菜) に置き換えるなら、こんなかんじでしょうか。
#(() (人 羊) (羊) (人 羊 菜) (菜) (人 狼 菜) (狼 菜) (人 狼 羊 菜)) #(() (人 羊) (羊) (人 狼 羊) (狼) (人 狼 菜) (狼 菜) (人 狼 羊 菜))
