GPCC2005問題


50手を超える詰め将棋問題を作成するプログラム

20〜30手までの詰め将棋の問題はコンピュータで作られたことがあるが、50手以上のものはまだない。

人間の作成した最長手数の詰め将棋は 1525手詰。 (橋本孝治氏「ミクロコスモス」「詰将棋パラダイス」1986年6月号)


ARIMAA

人間のArimaa王者に勝つコンピュータプログラムを書いて賞金10000ドルを得よう。(arimaa.com: The 2005 Arimaa Challenge)。

ARIMAAは、2002年に発表された新しいゲームで、チェスに似ているが人間に有利であると言われている。(参考: arimaa.comHotWiredJapanの解説(要JavaScript)、スラッシュドット ジャパンの簡単な解説)

Arimaa.commによると、2005年のコンピュータ王者のレーティングは1900程度。2200ぐらいになれば人間に勝てるのではないだろうか。

毎年人間とコンピュータそれぞれの大会が開かれており、コンピュータ部門での優勝賞金は500ドル。今年の大会は2月に終わっているが、人間の王者に勝ったものはおらず、10000ドルの賞金はまだ有効。


裁ちあわせパズルの全解探索

6×7の長方形を点線に沿って5片に切り分けて並べかえ、右のような酉の字にしてください。片は裏返さないとします(植松峰幸氏の年賀パズルより)。全解を求めてください。人手で2解知られています。

類題: 下図を3片で。条件は同じく、点線に沿って切り分けること、片は裏返さないこと(植松峰幸氏による問題)。全解を求めてください。人手で88解が知られています。

解の数え方の注意(類題について例示します)

解答へ


ペントミノパズルの解の分類

ペントミノ12種を6x10に箱詰めする問題の解は、対称性を排除して、2339通りあります。

解のなかには2片を置きかえただけで別の解を作ることができるものがあります。それらを同じグループとみなしたとき、解はいくつかのグループに分けられます。

グループは2片を置きかえるという関係による連結な集まりです。例えば、下図の解Aの2片を置きかえると解Bとなり、解Bの2片を置きかえると解Cとなりますが、解Aから解Cへは4片を置きかえなければなりません。しかし、A、Cは同一のグループに属します。

2片ではなく、3片までの置きかえを許すと、グループの数は少なくなります。

それでは、何片までの置きかえを許した時に、2339通りの解が全て一つのグループに属すようになるでしょうか。最小の片数を求めてください。

解答へ


数独の数え上げ

3x3ごとに区切られた9x9の桝目に、以下の制約を満たすよう1〜9の数字を配置する仕方が何通りあるか求めてください。

以下の対称性はすべて考慮してください。つまり、対称なものは全て同じ配置とします。

参考: 数独(「数字は独身に限る」の略)というペンシルパズルがあり、それは既に配置されているいくつかの数字を手がかりにして、この制約を満たすように残りの数字をあてはめていくものです。(本来の数独の遊び方についてはニコリのサイトの説明を参照。上記の配置例もそこから引用しました。)

この問題の現状


最小公倍図形

図形Aがいくつかの図形Bでできているとき「図形Aは図形Bで割りきれる」と定義します。ここで、図形としては単位正方形からなるもののみを考えています。

注意: 図形の演算を定義したわけではありません。

Tペントミノで割りきれる図形の例:

Oテトロミノ(4単位の正方形)で割りきれる図形の例:

TペントミノとOテトロミノの両方で割りきれるなるべく小さい図形を見つけてください。(Robert Wainright氏による問題)

現在見つかっている最小の図形は以下のTペントミノ120個=Oテトロミノ150個(600単位)のものです(河原哲郎氏による)。初出時には「Tペントミノ150個(750単位)」としていましたが、訂正します(2011-2-27訂正追記)。