-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgpcc11.htm
83 lines (52 loc) · 5.38 KB
/
gpcc11.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
<HTML>
<HEAD>
<TITLE>GPCC2011問題</TITLE>
</HEAD>
<BODY>
<H1>GPCC2011問題</H1>
<HR>
<H2><A NAME="g1">ついたて碁(Phantom Go)</A></H2>
<P>囲碁と似ているが、以下のような違いがある
<UL>
<LI>中国ルールをベースとする(2013-1-20追記)
<LI>9×9の盤を使い、コミは7.5目
<LI>相手の手は見えない
<LI>禁手かどうか(禁手の場合は指し直す)、取った石の数、取られた石の座標を、審判に教えてもらえる
<LI>どのような理由で禁手かは教えてもらえない
</UL>
<P>すでにいくつかプログラムがあるので、プログラムを作られた方はお送りくだされば、こちらで対戦させることができます。
<HR>
<H2><A NAME="g2">コリドール(Quoridor)(継続)</A></H2>
<P>2人で行うボードゲームである(4人で行うルールもある)。9×9の盤の自分側の辺の中央に自分の駒を置いて始め、先にゴール(相手側の辺のどこか)に着いたほうが勝ちである。2人で交互に、駒を1マス進めるか、長さ2の壁をマスの境界に置く。壁はそれぞれが10枚ずつ持っている。
<UL>
<LI>自分の駒が相手の駒と隣接しているときは、飛び越すことができる。ただし、相手の駒の後ろが壁か盤外の場合は、相手の駒の横に移動できる。
<LI>壁を置くときは、盤からはみ出したり、他の壁と重なったり、交わったりしてはいけない。
<LI>ゴールにどうしても着けないように壁を置いてはいけない。
</UL>
<P>日本での実物の入手は簡単ではないが、<A HREF="http://www.vector.co.jp/soft/winnt/game/se476678.html">ARiAdoNE</A>というフリーソフトがある(ルール説明も含まれている)ので、遊んでみることができる。
<P>昨年のコンピュータオリンピアード(<A HREF="http://www.grappa.univ-lille3.fr/icga/event.php?id=42&lang=3">ICGA トーナメント</A>)に参加した人によると、壁を置くことにより最短経路が大きく変化するゲームであり、まだ人間のほうが強いということである。
<P>プログラムを作られた方はお知らせください。
<HR>
<H2><A NAME="p1">数独のヒント最少問題</A></H2>
<P>数独はペンシルパズルの一つで、9×9の正方形に並んだマスに1から9までの数字を入れて、各行、各列、各3×3のブロックに、各数字が1回ずつ現れるようにするものである(<A HREF="http://www.nikoli.co.jp/ja/puzzles/sudoku/">「数独(Sudoku)」のニコリ公式パズルガイド</A>)。「数独」はニコリの登録商標なので、「ナンバープレース（ナンプレ）」と呼ばれることも多い。
<P>数独には試行錯誤が不要という暗黙のルールがあるが、試行錯誤とは何かは議論の元となるため、ここでは解が一つだけであればよいとしておく。
<UL>
<LI>最初にヒントとして配置する数字の数は、現在知られている問題では17個以上である。16個では問題を作れないと予想されており、それを示そうという試みは以前からあるが、そろそろ可能なのではないか。[2012年1月に、GPCCと関係なく解かれた。<A HREF="http://www.math.ie/checker.html">Gary McGuire's Minimum Sudoku Page, Sudoku Checker</A>に論文とプログラムがある。]
<LI>数独には、16×16のマス(4×4のブロックに分かれている)に1から16までの数字を入れるものもある。その場合に必要なヒント数の予想はまだないようである。手始めとして、なるべくヒントの少ない問題を作ってみよう(<A HREF="http://www2.ic-net.or.jp/~takaken/auto/guest/bbs59.html">プログラミングパズル雑談コーナー</A>の「16x16の場合」のところに、ヒント62個の問題がある)。[解答あり 最新は2011-4-9]
</UL>
<P><A HREF="11p1.htm">解答へ</A>
<P><A HREF="11p1a.htm">25×25の数独についての報告</A>(2012-8-19追加)
<HR>
<H2><A NAME="p2">最小公倍図形(復活)</A></H2>
<P>2005年の問題の<A HREF="gpcc05.htm#p4">最小公倍図形</A>と同じである。当時は解がもっと小さい問題しか計算できなかった。
<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氏による問題)[2011-12-2解答あり]
<P>現在見つかっている最小の図形は以下のTペントミノ120個=Oテトロミノ150個(600単位)のものです(河原哲郎氏による)。初出時には「Tペントミノ150個(750単位)」としていましたが、訂正します(2011-2-27訂正追記)。
<P><CENTER><IMG SRC="images/LCM.gif" WIDTH=444 HEIGHT=418></CENTER>
<P><A HREF="11p2.htm">解答へ</A>
<P style="height:1000px">以下余白</P>
</BODY>
</HTML>