オオカミとヤギとキャベツをVB.NETで解く(1)

背景

プログラミングで何か作ろうと思い、難しすぎない手頃な課題がないかと探していたら「オオカミとヤギとキャベツ」というのがあったのでやってみました。

オオカミとヤギとキャベツとは

オオカミとヤギを連れ、キャベツを持った農夫が川岸にいる。川には1艘のボートがある。

• ボートを漕げるのは農夫のみ。
• ボートには農夫のほか、動物1頭かキャベツ1個しか乗せられない。
• 農夫がいないときにオオカミとヤギを岸に残すと、オオカミがヤギを食べてしまう。
• 農夫がいないときにヤギとキャベツを岸に残すと、ヤギがキャベツを食べてしまう。

すべてを無事に対岸に渡すにはどうしたらよいか?

(Wikipediaより)

方針

状態を表すクラスStateを用意して、そこに農夫、オオカミ、ヤギ、キャベツがそれぞれどちら側の岸にいるかをメンバーとして持たせる方針で行きます。ここでは西岸から東岸に渡るとして、農夫、オオカミ、ヤギ、キャベツが東岸にいるかどうかをBoolean型で格納することにします。

Class State
    Private Farmer As Boolean   '農夫が東岸に居るか
    Private Wolf As Boolean     'オオカミが東岸に居るか
    Private Goat As Boolean     'ヤギが東岸に居るか
    Private Cabbage As Boolean  'キャベツが東岸にあるか
End Class

Stateクラスにその状態が終了条件と一致しているか判定する関数を付け足します。
終了条件は「農夫、オオカミ、ヤギ、キャベツが全て東岸にいる(つまり全部True)」となります。

Public Function IsGoal() As Boolean
 Return Farmer AndAlso Wolf AndAlso Goat AndAlso Cabbage
End Function

同様にその状態が失敗であるか判定する関数を付け足します。
失敗条件は「農夫がいない時にオオカミとヤギが同じ岸にいる」または「農夫がいない時にヤギとキャベツが同じ岸にいる」となります。
この条件は「農夫とヤギが異なる岸にいる かつ (オオカミとヤギが同じ岸にいる または ヤギとキャベツが同じ岸にいる)」と言い換えることができます。

Public Function IsFailure() As Boolean
    Return Farmer <> Goat AndAlso (Wolf = Goat OrElse Goat = Cabbage)
End Function

次に、可能な渡り方を作っていきます。渡り方は農夫のみ、農夫とオオカミ、農夫とヤギ、農夫とキャベツの4パターンです。渡り方のパターンは限られているのでEnumを使って表現します。

Enum Operate    '可能な操作
    Solo        '農夫のみ
    WithWolf    '農夫とオオカミ
    WithGoat    '農夫とヤギ
    WithCabbage '農夫とキャベツ
End Enum

この時点で自分は、ただ探索してゴールにたどり着いただけではゴールまでの過程がわからないということに気付きました。そこで最初に作ったクラスStateに「1つ前の状態」「1つ前に行った操作」「現在のステップ数」を新たに追加することにしました。Stateクラスに以下のメンバー変数を追加します。

 Private Parent As State     '1つ前の状態
 Private Operation As Operate '実行した操作
 Private Steps As Integer    '移動回数

初期状態には実行した操作が存在しないため、初期状態限定のOperateを追加して以下のようにしました。

Enum Operate    '可能な操作
    Start       '初回
    Solo        '農夫のみ
    WithWolf    '農夫とオオカミ
    WithGoat    '農夫とヤギ
    WithCabbage '農夫とキャベツ
End Enum

次にStateにコンストラクタを作って、初期状態を作ったりOperateを渡された時に次の状態を生み出せるようにしていきます。
コンストラクタは次のように実装しました。

Public Sub New(ByVal Farmer As Boolean,
               ByVal Wolf As Boolean,
               ByVal Goat As Boolean,
               ByVal Cabbage As Boolean,
               ByVal Parent As State,
               ByVal Operation As Operate)
    Me.Farmer = Farmer
    Me.Wolf = Wolf
    Me.Goat = Goat
    Me.Cabbage = Cabbage
    Me.Parent = Parent
    Me.Operation = Operation
    If Parent Is Nothing Then
        Me.Steps = 0
    Else
        Me.Steps = Parent.Steps + 1
    End If
End Sub

続いて初期状態を得る関数を作ります。

Public Shared Function StartState() As State
    Return New State(False, False, False, False, Nothing, Operate.Start)
End Function

与えられたOperateによって次の状態を作る関数も作ります。
農夫、オオカミ、ヤギ、キャベツはBoolean型なのでボートによる移動はNotを使って表現できます。
指定された移動ができない時はNothingを返すようにします。

Public Function MakeNext(ByVal Operation As Operate) As State
    Select Case Operation
    
        Case Operate.Solo
            Return New State(Not Me.Farmer, Me.Wolf, Me.Goat, Me.Cabbage, Me, Operation)
            
        Case Operate.WithWolf
            If Me.Farmer = Me.Wolf Then
                Return New State(Not Me.Farmer, Not Me.Wolf, Me.Goat, Me.Cabbage, Me, Operation)
            End If
            
        Case Operate.WithGoat
            If Me.Farmer = Me.Goat Then
                Return New State(Not Me.Farmer, Me.Wolf, Not Me.Goat, Me.Cabbage, Me, Operation)
            End If
            
        Case Operate.WithCabbage
            If Me.Farmer = Me.Cabbage Then
                Return New State(Not Me.Farmer, Me.Wolf, Me.Goat, Not Me.Cabbage, Me, Operation)
            End If
            
    End Select

    Return Nothing

End Function

長くなってきたので続きは次回書きます。