駒を飛び越え，取り除けジャンプスナッチゲーム：日経サイエンス

	日経サイエンスは米国の科学雑誌「SCIENTIFIC AMERICAN」の日本版です。
	HOME

HOME ＞パズリング・アドベンチャー＞駒を飛び越え，取り除けジャンプスナッチゲーム

ご購入のご案内

検索方法はこちら

サイト内検索結果に戻る

駒を飛び越え，取り除け
ジャンプスナッチゲーム

デニス・シャシャ

　３×３のマス目に丸い駒を置いた盤面を考えてもらいたい。次のような簡単なルールを考える。駒は，縦，横，斜めのどの方向でも隣に別の駒があり，その先が空きマスであれば，隣の駒を飛び越して空きマスに移動できる。そのとき，チェッカーの場合と同じように，飛び越された駒は盤面から取り除く。
　このゲームの１人遊び版の場合，目標はジャンプを繰り返すことで，盤上の駒を１個だけにすることだ。図Aに示した盤面から始めて，ゲームが終わったとき，盤面に駒が１つだけ残るようにするにはどうジャンプをしていけばよいだろうか？その解の１つを図B，C，Dに示す。

　では，読者の皆さんへの今月の第１問だ。駒をただ１つにするという目標を達成するには，ゲームを始める前の盤面に空きマスは最低で何マス必要で，それを盤面のどこに配置すればよいだろうか？また，３×３ではなく，４×４の盤面だったら空きは何マス必要で，どこに置けばいいだろうか？
　
　次は，２人でゲームをする場合を考える。このゲームを「ジャンプスナッチ」と呼ぼう。ジャンプスナッチでは，最初，３×３の全部のマス目に駒を置く。先手のプレーヤーをスナッチャーと呼び，後手をジャンパーと呼ぶ。最初にスナッチャーがどこのマス目からでもよいから，駒を１つ取り除く。次にジャンパーが，可能であればジャンプする。さらに可能であれば，続けてジャンプしてもよい（しなくてもよい）。ジャンパーの手番が終われば，スナッチャーがジャンプを試みる。このようにして，交互にプレーを進め，盤上の駒がただ１つになったとき，最後のジャンプをしたプレーヤーを勝ちとする。
　もし，自分の手番で，ジャンプがまったく不可能な盤面になっていたら，ジャンプの代わりに，駒の１つを真ん中のマスにずらすというプレーをしなければならない。真ん中のマス目がふさがっていて，それも不可能だったなら，真ん中以外の駒をどこか隣のマス目にずらさねばならない。駒をずらしたら，それで手番は終わりとなる。

　今月の第２問は，この２人のゲーム版についてだ。図E，F，Gにジャンプスナッチゲームの最初の３手の例を示す。この後を続けるとして，両プレーヤーが最善を尽くしたとすると，勝者はどちらになるだろうか？

	坂井公（さかい・こう）

	筑波大学数学系助教授，理学博士。専門は計算機科学。

	Dennis E. Shasha

	ニューヨーク大学クーラント研究所教授。専門は計算機科学。　原題名 Jump Snatch （SCIENTIFIC AMERICAN May 2004）


会社案内　\| 「日経サイエンス」はこんな雑誌　\|　個人情報の取り扱いについて　\|	Copyright 2005 NIKKEI SCIENCE Inc., all rights reserved