１−１２．おしどりの遊びと入れ替え問題

　おしどり（鴛鴦）の遊びというのは、白石ｎ個、黒石ｎ個を交互に並べたものをおしどりがつがいで並んでいる姿に見立てて、これを雌雄別々に並ぶようにする遊びである。ただし、石を動かすには、隣合った二つの石を同時に動かさねばならない。
　この問題は中根彦循の『勘者御伽双紙』（1743）にｎが３の場合が載っている。原文には解答が「四五を取り七八へ」というように文章で書かれているが、見やすいように図で示すと、[1]のようになる。つまり、アンダーラインの引いてある石を順に右の方へ移していけばよい。

[1]おしどりの遊び（ｎ＝３）

　西洋では、この問題をテートの問題と呼んでいるが、それはイギリスの物理学者Ｐ．Ｇ．テートが1884年に論文を発表したことによる。テートは金貨と銀貨各４枚を交互に並べたものを別々にする形にしている。
　一般にｎ個（ｎ≧４）の場合、隣に空所が２個分あれば、ｎ回の移動で並べ替えることが可能である。ｎが３の場合だけは、もし隣に２個分の空所しかなければ、４回移動させる必要がある。ｎが４の場合のやり方を[2]に示した。

[2]おしどりの遊び（ｎ＝４）

　おしどりの遊びは入れ替え問題の古典であるが、入れ替え問題は非常に数が多く、カエルの入れ替え、汽車の入れ替え、自動車の入れ替え、将棋の入れ替え等、枚挙にいとまがない。

　ここではもう一つ、カエルの入れ替え問題をご紹介しよう。
　１から４までの番号のついた４匹のカエルが [3]のようにはすの葉の上に左から番号順に並んでいる。これらのカエルは、隣の葉が空いていればそこに移ることができる。また、隣の葉にカエルがいて、その向う側の葉が空いている場合、隣のカエルを飛び越して、空いている葉にうつることが可能である。
　それでは、このカエルを今並んでいるのと逆の順序、つまり４３２１と並ぶようにするには、どうしたらよいだろうか。ただし、２匹以上のカエルを１度に飛び越えたり、同じ葉の上に２匹のカエルが乗ることは許されない。
　この問題を解くには、[3]のままで考えるより、[4]のＡのようなカエルの移動が可能な路線図を作ってみる方がよい。これからＢのようなルート図ができるので、あとはこのサイクルを回転していけばよい。解は、３、１、２、４、３、１、２、４、３、１（10手）。

[3]カエルの入れ替え問題

[4]カエルの入れ替えの路線図(A)とコース図(B)