-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgpcc05.htm
121 lines (74 loc) · 6.93 KB
/
gpcc05.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
<HTML>
<HEAD>
<TITLE>GPCC2005問題</TITLE>
</HEAD>
<BODY>
<H1>GPCC2005問題</H1>
<HR>
<H2><A NAME="g1">50手を超える詰め将棋問題を作成するプログラム</A></H2>
<P>20～30手までの詰め将棋の問題はコンピュータで作られたことがあるが、50手以上のものはまだない。
<P>人間の作成した最長手数の詰め将棋は 1525手詰。 (橋本孝治氏「ミクロコスモス」「詰将棋パラダイス」1986年6月号）
<HR>
<H2><A NAME="g2">ARIMAA</A></H2>
<P>人間のArimaa王者に勝つコンピュータプログラムを書いて賞金10000ドルを得よう。(arimaa.com: <A HREF="http://arimaa.com/arimaa/challenge/2005/">The 2005 Arimaa Challenge</A>)。
<P>ARIMAAは、2002年に発表された新しいゲームで、チェスに似ているが人間に有利であると言われている。(参考: <A HREF="http://arimaa.com/arimaa/">arimaa.com</A>、
<A HREF="http://hotwired.goo.ne.jp/news/culture/story/20021125205.html">HotWiredJapanの解説</A>(要JavaScript)、<A HREF="http://slashdot.jp/articles/02/11/25/2238249.shtml">スラッシュドット ジャパンの簡単な解説</A>)
<P>Arimaa.commによると、2005年のコンピュータ王者のレーティングは1900程度。2200ぐらいになれば人間に勝てるのではないだろうか。
<P>毎年人間とコンピュータそれぞれの大会が開かれており、コンピュータ部門での優勝賞金は500ドル。今年の大会は2月に終わっているが、人間の王者に勝ったものはおらず、10000ドルの賞金はまだ有効。
<HR>
<H2><A NAME="p1">裁ちあわせパズルの全解探索</A></H2>
<P>6×7の長方形を点線に沿って5片に切り分けて並べかえ、右のような酉の字にしてください。片は裏返さないとします(植松峰幸氏の年賀パズルより)。全解を求めてください。人手で2解知られています。
<P><CENTER><IMG SRC="images/tori05.gif" WIDTH=486 HEIGHT=225></CENTER>
<P><B>類題:</B> 下図を3片で。条件は同じく、点線に沿って切り分けること、片は裏返さないこと(植松峰幸氏による問題)。全解を求めてください。人手で88解が知られています。
<P><IMG SRC="images/345.gif" WIDTH=333 HEIGHT=142>
<P>解の数え方の注意(類題について例示します)
<UL>
<LI>下図のように、切り分けて同じ片の集合ができたとしても、切り分け方が異なれば別の解として数えます。
<P>例:<IMG SRC="images/345_1.gif" WIDTH=438 HEIGHT=135 align=top>
<LI>下図のように、同じ片の集合を組み合わせていても、組み合わせ方が異なれば別の解として数えます。(正方形を回転して同じになる場合は同じ解とします。正方形全体の裏返しは別の解とします。)
<P>例:<IMG SRC="images/345_2.gif" WIDTH=442 HEIGHT=110 align=top>
</UL>
<P><A HREF="gpcc05s.htm#p1">解答へ</A>
<HR>
<H2><A NAME="p2">ペントミノパズルの解の分類</A></H2>
<P>ペントミノ12種を6ｘ10に箱詰めする問題の解は、対称性を排除して、2339通りあります。
<P>解のなかには2片を置きかえただけで別の解を作ることができるものがあります。それらを同じグループとみなしたとき、解はいくつかのグループに分けられます。
<P>グループは2片を置きかえるという関係による連結な集まりです。例えば、下図の解Aの2片を置きかえると解Bとなり、解Bの2片を置きかえると解Cとなりますが、解Aから解Cへは4片を置きかえなければなりません。しかし、A、Cは同一のグループに属します。
<P><CENTER><IMG SRC="images/pentomino.gif" WIDTH=735 HEIGHT=185></CENTER>
<P>2片ではなく、3片までの置きかえを許すと、グループの数は少なくなります。
<P>それでは、何片までの置きかえを許した時に、2339通りの解が全て一つのグループに属すようになるでしょうか。最小の片数を求めてください。
<P><A HREF="gpcc05s.htm#p2">解答へ</A>
<HR>
<H2><A NAME="p3">数独の数え上げ</A></H2>
<P>3x3ごとに区切られた9x9の桝目に、以下の制約を満たすよう1～9の数字を配置する仕方が何通りあるか求めてください。
<UL>
<LI>制約1. 同じ行に同じ数字は無い
<LI>制約2. 同じ列に同じ数字は無い
<LI>制約3. 同じブロックに同じ数字は無い(ブロックとは太線で区切られた3x3のかたまりのこと)
</UL>
<P><CENTER><IMG SRC="images/suudoku.gif" WIDTH=284 HEIGHT=282></CENTER>
<P>以下の対称性はすべて考慮してください。つまり、対称なものは全て同じ配置とします。
<UL>
<LI>対称性1. 全体の回転、反転
<LI>対称性2. 数字の置き換え
<LI>対称性3. 行の入れ替え<BR>
制約3のため、任意に入れ替えることはできない。<BR>
ブロック内での入れ替えと、ブロック単位での入れ替えがあり、その組み合わせが許される。
<P>ブロック内の入れ替えの例:<IMG SRC="images/s1.gif" WIDTH=462 HEIGHT=203 align=top><BR>
<P>ブロック単位での入れ替えの例:<IMG SRC="images/s2.gif" WIDTH=463 HEIGHT=210 align=top><BR>
<LI>対称性4. 列の入れ替え<BR>
行と同様の制限がある。
</UL>
<P><B>参考:</B> 数独(「数字は独身に限る」の略)というペンシルパズルがあり、それは既に配置されているいくつかの数字を手がかりにして、この制約を満たすように残りの数字をあてはめていくものです。(本来の数独の遊び方については<A HREF="http://www.nikoli.co.jp/puzzles/1/index_text.htm">ニコリのサイトの説明</A>を参照。上記の配置例もそこから引用しました。)
<P><A HREF="05p3.htm">この問題の現状</A>
<HR>
<H2><A NAME="p4">最小公倍図形</A></H2>
<P>図形Aがいくつかの図形Bでできているとき「図形Aは図形Bで割りきれる」と定義します。ここで、図形としては単位正方形からなるもののみを考えています。
<P>注意: 図形の演算を定義したわけではありません。
<P>Tペントミノで割りきれる図形の例:<IMG SRC="images/LCM1.gif" WIDTH=410 HEIGHT=167 align=top>
<P>Oテトロミノ(4単位の正方形)で割りきれる図形の例:<IMG SRC="images/LCM2.gif" WIDTH=404 HEIGHT=166 align=top>
<P>TペントミノとOテトロミノの両方で割りきれるなるべく小さい図形を見つけてください。(Robert Wainright氏による問題)
<P>現在見つかっている最小の図形は以下のTペントミノ120個=Oテトロミノ150個(600単位)のものです(河原哲郎氏による)。初出時には「Tペントミノ150個(750単位)」としていましたが、訂正します(2011-2-27訂正追記)。
<P><CENTER><IMG SRC="images/LCM.gif" WIDTH=444 HEIGHT=418></CENTER>
</BODY>
</HTML>