« 今日のカープ | メイン | 代数学セミナー »

解を数える

この間考えた解の数え上げ問題について。将棋の指し始めの局面から後手が連続して9手指し、最後に先手が1手指して後手玉が詰んだとするとき、詰め上がり図に到達する手順前後解は全部でいくつあるか、である。

SeriesHelp9-1.pngまず左の図面について考えてみよう。後手が指した手は74歩(1手)、51玉→95玉(4手)、83歩→85歩(2手)、84飛(1手)、94歩(1手)の9手である。このうち94歩は他の手と全く干渉しておらず、いつ指すこともできるので、一番最後にまとめて考えることにしよう。残りの8手だが、玉の8筋の横断が83の歩を突く前か後かで分けると考えやすいと思う。歩を突く前に84玉と出る手順は、それ以降の手順が95玉、84歩、85歩、84飛と完全に決まってしまうので、74歩と62玉のどちらを先に指すかという2通りしか選択の余地がない。一方、歩を85まで突いてから玉を通す場合は、84玉から先はやはり手順が一意に決まってしまうので、[85歩・74歩・73玉]の形に至るまでに何通りあるかを数えればよい。これは84歩、85歩の2手を残りの3手の並びのどこで挿入するかで決まるから、組み合わせの計算で20通り。これに先ほどの2通りを足して22通り。最後に、とっておいた94歩をどこで指すかという可能性を考えて9倍すれば、解の個数は全部で22×9=198通りになる。

SeriesHelp9-2.png続いて左の図面。王手がかかってはいけないことを考えると、後手が最後に指した手は17としかあり得ない。ということは、(51玉-)42玉-32玉-23玉-14玉と玉を動かす4手と、(23歩-)24歩-25歩-26歩-27歩成と歩を動かす4手の組み合わせを全部数えればいいことになる。これは8C4=70通り。しかし、最初に玉ばかり3手動かす手は、23地点にまだ歩がいて不可能であるから、その分を除かねばならない。これが5通りあるから、その分を引いて解は70-5=65通りあることが分かる。

もっとうまい考え方があって簡単に計算できるのかもしれないが、とりあえずない知恵を絞って数えてみた。もし間違っていたらご教示いただければ幸いである。しかし、将棋でカタラン数やフィボナッチ数が答えになる図面を創るのはかなり大変そうだ。

トラックバック

このエントリーのトラックバックURL:
http://monsieur.ddo.jp/cgi-bin/mt_3/mt-tb.cgi/383

コメント

初期位置からのシリーズヘルプでは流石に難し過ぎですが、
普通の詰将棋型なら色々できるような気がします。
例えば、数種類の合駒が数回の機会で可能なら、
どの順番で合駒するかでカタラン数になりそうな…
無駄に解が沢山あるので、詰将棋としては全く美しくないのが欠点ですが。

なるほど、そう言われてみればそうですね。
合駒の順番というのは、チェスでは出てこない話ですから面白そうです。

最初は合駒の順番を使えば…と思ったのですが、攻め側の持駒の任意性を使うと
もっと簡単に組み合わせ論の問題ができそうですね。
(例えば、ここは銀打ちでも金打ちでもいい、と言うところが数カ所ある、とか)。
詰将棋で「解の個数が(組み合わせ論的に)面白い」問題はむしろ、
どうやって詰将棋として面白い問題にするか、が味噌と思われます。

その味噌の部分が一番の難関かもしれませんが……。
そもそも詰将棋の面白さというのは、例えば
「ここは金打ちでも銀打ちでもどちらでもよさそうに見えるが、金を打ってしまうと
あとで玉方に絶妙の受けが発生してしまうので、実は銀でなければならない」
というようなことによっていることが少なくないように思います。
もしそれがどちらでもいいとなると、詰将棋に慣れている人はその時点で、
ある程度のマイナスイメージを抱いてしまうのではないかという恐れがあります。
それを覆せるほどのいいアイディアがあるかどうか、でしょうかねえ。

コメントを投稿