鴛鴦の遊び １

　鴛鴦（えんおう、おしどり）の遊びというのは、白石ｎ個、黒石ｎ個を交互に並べたものを鴛鴦（おしどり）が番（つが）いで並んでいる姿に見立てて、これを雌雄別々に並ぶようにする遊びである。ただし、石を動かすには、隣合った二つの石を同時に動かさねばならない。 

　この問題は中根彦循の『勘者御伽双紙』（1743年）にｎが３の場合が載っている。原文には解答が「四五を取り七八へ」というように文章で書かれているが、見やすいように図で示すと、左図のようになる。つまり、アンダーラインの引いてある石を順に右の方へ移していけばよい。
 

　西洋では、この問題をテートの問題と呼んでいるが、それはイギリスの物理学者P.G.Tait（テート、1831～1901年）が1884年に論文を発表したことによる。テートは金貨と銀貨各４枚を交互に並べたものを別々にする形にしている。
　一般にｎ個（ｎ≧４）の場合、隣に空所が２個分あれば、ｎ回の移動で並べ替えることが可能である。ｎが３の場合だけは、もし隣に２個分の空所しかなければ、４回移動させる必要がある。ｎが４の場合のやり方を左にに示した。
 
　鴛鴦の遊びは入れ替え問題の古典であるが、入れ替え問題は非常に数が多く、カエルの入れ替え、汽車の入れ替え、自動車の入れ替え、将棋の入れ替え等、枚挙にいとまがない。
 
　ここではもう一つ、カエルの入れ替え問題をご紹介しよう。
　１から４までの番号のついた４匹のカエルが左の「カエルの入れ替え問題」の上図ようにはすの葉の上に左から番号順に並んでいる。これらのカエルは、隣の葉が空いていればそこに移ることができる。また、隣の葉にカエルがいて、その向う側の葉が空いている場合、隣のカエルを飛び越して、空いている葉にうつることが可能である。
　それでは、このカエルを今並んでいるのと逆の順序、つまり４３２１と並ぶようにするには、どうしたらよいだろうか。ただし、２匹以上のカエルを１度に飛び越えたり、同じ葉の上に２匹のカエルが乗ることは許されない。
　この問題を解くには、このままで考えるより、下図のＡのようなカエルの移動が可能な路線図を作ってみる方がよい。これからＢのようなルート図ができるので、あとはこのサイクルを回転していけばよい。解は、３、１、２、４、３、１、２、４、３、１（10手）。