オオカミとヤギとキャベツをVB.NETで解く(全コード)

(1)と(2)で作ったコードの全体を載せます。

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

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

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

    '1つ前の状態を取得
    Public ReadOnly Property ParentState As State
        Get
            Return Me.Parent
        End Get
    End Property

    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 Overloads Function Equals(ByVal obj As State)
        Return Me.Farmer = obj.Farmer AndAlso Me.Wolf = obj.Wolf AndAlso Me.Goat = obj.Goat AndAlso Me.Cabbage = obj.Cabbage
    End Function

    'メンバーが同じなら等価とする
    Public Overrides Function Equals(obj As Object) As Boolean
        'どちらかがNothingまたは型が違えば等価ではない
        If obj Is Nothing OrElse Me Is Nothing OrElse Me.GetType() IsNot obj.GetType() Then
            Return False
        Else
            Return Equals(CType(obj, State))
        End If
    End Function

    'EqualsがTrueの時に同じ値を返す
    Public Overrides Function GetHashCode() As Integer
        Return -(CInt(Me.Farmer) * 8 + CInt(Me.Wolf) * 4 + CInt(Me.Goat) * 2 + CInt(Me.Cabbage))
    End Function

    'ゴールかどうか(農夫、オオカミ、ヤギ、キャベツが東岸にある状態)
    Public Function IsGoal() As Boolean
        Return Farmer AndAlso Wolf AndAlso Goat AndAlso Cabbage
    End Function

    '初期状態(農夫、オオカミ、ヤギ、キャベツが西岸にある状態)
    Public Shared Function StartState() As State
        Return New State(False, False, False, False, Nothing, Operate.Start)
    End Function

    '失敗かどうか(農夫が居ない時にオオカミとヤギが一緒に居る、またはヤギとキャベツが一緒にある状態)
    Public Function IsFailure() As Boolean
        Return Farmer <> Goat AndAlso (Wolf = Goat OrElse Goat = Cabbage)
    End Function

    '移動方法に合わせて次の状態を生成
    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

    '状態を出力
    Public Sub Print()

        If Me.Operation <> Operate.Start Then
            Dim OnBoat As String = ""
            Select Case Me.Operation
                Case Operate.Solo
                    OnBoat = "F "
                Case Operate.WithWolf
                    OnBoat = "FW"
                Case Operate.WithGoat
                    OnBoat = "FG"
                Case Operate.WithCabbage
                    OnBoat = "FC"
            End Select
            If Me.Farmer Then
                OnBoat = "---" & OnBoat & "-->"
            Else
                OnBoat = "<--" & OnBoat & "---"
            End If
            Console.WriteLine(Space(6) & OnBoat)
        End If

        Dim West As String = ""
        Dim East As String = ""

        If Farmer Then
            East &= "F"
        Else
            West &= "F"
        End If

        If Wolf Then
            East &= "W"
        Else
            West &= "W"
        End If

        If Goat Then
            East &= "G"
        Else
            West &= "G"
        End If

        If Cabbage Then
            East &= "C"
        Else
            West &= "C"
        End If

        Console.WriteLine(West.PadRight(5) & "～～～～～" & East.PadLeft(5))

    End Sub

End Class

Module Module1

    '前の状態をたどって結果を出力
    Private Sub Result(ByVal NowState As State)
        If NowState.ParentState IsNot Nothing Then Result(NowState.ParentState)
        NowState.Print()
    End Sub

    Sub Main()
        Dim SearchQueue As Queue(Of State) = New Queue(Of State)    '未探索の状態を格納するキュー
        Dim SearchedList As List(Of State) = New List(Of State)     '探索済みの状態を格納するリスト
        Dim NowState As State = State.StartState()                  '現在調べている状態
        Dim NextState As State                                      '次の状態
        SearchQueue.Enqueue(NowState)
        While SearchQueue.Count > 0
            NowState = SearchQueue.Dequeue()

            If NowState.IsFailure() Then Continue While '失敗なら他の状態を探索

            If SearchedList.IndexOf(NowState) >= 0 Then Continue While '探索済みなら他の状態を探索

            If NowState.IsGoal() Then   'ゴールなら結果を出力して終了
                Result(NowState)
                Exit While
            End If

            For Each Operation As Operate In [Enum].GetValues(GetType(Operate)) '現在の状態から移れる状態を生成してキューに格納
                NextState = NowState.MakeNext(Operation)
                If NextState IsNot Nothing Then SearchQueue.Enqueue(NextState)
            Next

            SearchedList.Add(NowState)  '探索済みに追加

        End While
        Console.ReadLine()
    End Sub

End Module