状態空間による定義

• 状態を(m, c, b)で表現する
• 初期状態 (3,3,1)
• 目標状態 (0,0,0)

考え方

• 左岸で安全であるためには，m>=c あるいは m=0
• 右岸で安全であるためには，3-m>=3-c あるいは 3-m=0，すなわち，m<=c あるいは m=3
• 両岸で安全であるためには，m=cあるいはm=0あるいはm=3となる

伝道師(宣教師)と土人の解答例

(3,3,1) → CC → (3,1,0) → C  → (3,2,1) → CC → (3,0,0)
        → C  → (3,1,1) → MM → (1,1,0) → MC → (2,2,1) → MM → (0,2,0)
        → C  → (0,3,1) → CC → (0,1,0) → C  → (0,2,1) → CC → (0,0,0)