川渡り問題
川岸にいる一団を対岸に渡す。
川を渡る手段は小船だけであり、小さいので全員は乗れないため、小分けにして往復する必要がある。 「小船を漕げる者が限定されており、その者が小船に乗っていないと移動できない」という条件が与えられる場合もある。
特定の組み合わせがどちらかの岸にできてはいけない。 多くは「○○がいない状態で□□と△△を一緒にしてはいけない」という形で条件が与えられる。