宣教師と人食い人種の渡河問題の解答例を示します。
問題（１）の解１
最初、4人がいる場所を左岸(L)とし、向こう岸を右岸(R)とする。ボートは左岸にあるとする。
(左岸にいる人食い人種の人数、左岸にいる宣教師の人数、ボートのある川岸)で状態を表す。人数は数字、左岸にボートがある場合L、右岸にボートがある場合Rとする。
最初の状態は、22Lで、目標の状態は、00R である。
最初の状態から５つの状態、12R,21R,11R,02R,20R への移動が考えられる。
５つの状態は状態（22L）の下につぎのように表すことができる。
ある状態から得られる状態をつぎつぎに求めると、木を構成できる。
この木では、状態を節点とみなす。根からある状態までの経路中に同じ状態がある場合と、人食い人種が宣教師より多い場合には、その状態を枠で囲み葉とする。前者は繰り返しになるためであり、後者は題意を満たさないためである。
題意を満たす状態（00R）が得られたときも葉とする。
木を根（22L）から出発して、反時計回りにたどりすべての状態を調べる。その結果、根（22L）から葉（00R）への長さ5の４つの経路が解に対応することがわかる。
解(1)： 22L → 11R → 12L → 10R → 20L → 00R
解(2)： 22L → 11R → 12L → 10R → 11L → 00R
解(3)： 22L → 02R → 12L → 10R → 20L → 00R
解(4)： 22L → 02R → 12L → 10R → 11L → 00R
