プログラミングコンテスト

NAGASAKA Yasunori

2003/10/01

http://edu.isc.chubu.ac.jp/naga/index.html で公開中


　Table of Contents


http://edu.isc.chubu.ac.jp/naga/index.html で公開中 1 　 はじめに

2 　 N-Queen
　2.1 　 N-Queen のルール
　2.2 　 コンテストのルール
　2.3 　 現在の記録
　2.4 　 応募方法

3 　 大富豪
　3.1 　 更新履歴
　3.2 　 コンテストのルール
　3.3 　 プログラミングキットの配布
　3.4 　 コンテストの日程


1 　 はじめに

プログラミングの練習のために、対戦型のゲームやパズルを題材として プログラミングコンテストを開催することにしました。 自分のプログラミングの能力を知るために挑戦してみて下さい。

電子工学科３年生の人は、 冬になるとそろそろ来年の研究室をどこにしようかと考えると思います。 もし、私の研究室を希望するのなら、以下の課題に挑戦してみてもよいと思います。 どの課題もプログラム作成の技術が要求され、 アルゴリズムを工夫する必要があります。 よってこの中の一つでもきちんと作ることができれば、 優れたプログラム作成能力があると認められます。 過去の卒研生でも、 これらの課題ができた人の多くは卒業研究でも優れた成果を挙げています。

2 　 N-Queen

このページは卒業生の鈴村君が作成したページをもとにして、 一部変更しています。 オリジナルページを提供してくれた鈴村君に感謝します。

2.1 　 N-Queen のルール

皆さんは、チェスの Queen の駒の動き方を知っていますか？ 知らないよ〜という人のために説明します。 Queen は将棋でいう飛車と角を合わせた動きのできる駒です。 下の図のようになります。



Queen の動ける範囲

矢印の届く範囲のマス目(利き筋といいます)に他の駒がいた場合、 その駒は Queen に取られてしまいます。
さて、この Queen という駒を盤上に複数配置する場合 1 つもお互いにぶつからない (他の Queen の利き筋に入らない)ようにするにはどのように並べればよいでしょうか ？ 例として ５×５ のマス目に 5 個の Queen を配置する場合で考えてみましょう。 下の図を見てください。



5 Queen

このように並べると、それぞれの Queen は互いにぶつかりません。 ここでは一つの配置パターンだけを示しましたが他にもいくつか存在します。 このようにして、N×Nのマス目に N 個の Queen を配置する場合に、 すべての可能な配置パターンを求めるのが N-Queen 問題です。 そしてこのコンテストでは、何通りの配置ができるかを数え上げるプログラムを C 言語で作成することにします。 配置パターンの中には上下対称、左右対称、回転対称など、 一見すると別の解なんだけど本質は同じものが多く存在します。 ここでは、そのような配置パターンはすべて "別の解" としてカウントします。 別の表現をするなら対称性のチェックは必要ありません。


2.2 　 コンテストのルール

コンテストは 2 段階あります。 標準レベルができないうちは上級レベルに取り組んではいけません。

標準レベル : N が指定された時に解の総数を数え上げるプログラムを作成する。 計算速度はここでは問題ではなく、正しく動作することが必要である。 アルゴリズムは自分で考えなくてはならず、 アルゴリズムの参考書などを見てはいけない。

参考データ：8-Queen（8×8のマス目で Queen 8 個) のとき、 92 通りの配置ができます。

上級レベル : 作成したプログラムをなるべく高速化する。 アルゴリズムの参考書など、何を見て改良してもよい。 現在は N＝13 のときの解の総数を何秒で求められるかを競っている。 最新のコンピュータなら 5 秒、少し前の古いコンピュータなら 10 秒を切ることができればまずまずでしょう。


2.3 　 現在の記録

いずれも CPU : Pentium4 2GHz を使用した場合の記録です。

N=13 の場合、解の総数は 73712 で 0.30 秒

N=14 の場合、解の総数は 365596 で 1.61 秒

N=15 の場合、解の総数は 2279184 で 10.90 秒

2.4 　 応募方法

完成したプログラムのソースファイルを持って (FD, CD-R, USB メモリなど) 研究室に来るとか、メール（添付ファイルではなく、 テキスト形式でメールの本文に埋め込んで下さい）で送るなどなど・・・。 とにかく、ソースさえあればなんとでもなります。 速度の測定はこちらでなるべく公正に行います。 速度の比較では、 同一のマシンで同一のコンパイルオプションでコンパイルした実行ファイルを使って比較します。 通常は、UNIX 上で以下のように gcc に最適化オプションを指定してコンパイルします。
% gcc -O -o file file.c
このコンテストは年中やっていますので、完成したらいつでもどうぞ。


3 　 大富豪


3.1 　 更新履歴

更新履歴はパッケージの README.txt にも同様の記述があります。


3.2 　 コンテストのルール



3.3 　 プログラミングキットの配布

プログラミングキットは、以下の [ダウンロード] からリンクされているファイルをダウンロードして使って下さい。 プログラミングキットの実行環境は UNIX を想定しています。プログラミングキットは tgz (tar + gzip) という形式で、圧縮して固めてありますので FreeBSD, Linux その他多くの UNIX の場合は、
% tar zxvf fugokit.tgz
として展開して下さい。
tgz 形式は Windows 用の圧縮・解凍ツールでも対応しているものがありますので、 Windows 上でも展開することは可能です。ただし Windows ではコンパイル時に必要となる ツールが標準では用意されていないのでそのままではコンパイルできません。UNIX と互換の 環境を用意すれば Windows 上でもコンパイル、実行できたという報告を受けています。
[ダウンロード]

3.4 　 コンテストの日程

2003 年度の研究室内の大会を11/26 (水) 15:10 から開催することが決まりました。 研究室の学生は上記の日時までにプログラムを完成させておくように。 研究室外の人のオープン参加も歓迎しますので、 興味のある方は上記の日時に研究室までお越し下さい。