コグノスケ

C言語でNクイーン問題

目次: ベンチマーク

Nクイーン（※）を解かせるプログラムを組んでみました。結果は15クイーン（解2279184通り）で2分14秒 でした（コンパイラ: Visual C++ 6.0 release build）。Athlon 1.4GHzのくせにこんなです。うーん、遅い。
ネット上で見つけた、高橋謙一郎さんという方が作ったプログラムは15クイーンが1秒12でした。いやはや速すぎます。高橋さんのページを読むに、ユニーク解を用いると無駄な検索を省けるようですが、よくわからなかったので組み込めそうにありません。悲しい限りです。

追記です。15クイーンは左右対称性を利用して検索を半分カットし、動的配列の使用を止め、静的配列にしたところ21秒になりました。これだけで7倍も速くなるんですねえ。でもまだ2ケタ秒かかっていて遅い事に変わりはないです。

（※）Nクイーン問題はn x nの大きさのチェスの盤にn個のクイーンを互いに取られない位置に置くパターンがいくつあるかを求める問題のこと。

大西洋単独横断で英雄となったリンドバーグ（Charles Augustus Lindbergh 1902-1974アメリカ）の「The Spirit of St.Louis」の邦題「翼よ、あれがパリの灯だ」がカッコイイなーと思いました。意訳しすぎと思う方もいるかな、私は訳者のセンスが感じられて良いなーと思ってます。少なくとももろにカタカナ英語にするよりは良いでしょ。

午前を寝過ごしました。ああ゛ー。
午後の実験もうまくいかない。ネットワーク関連のシステムコールはぐちゃぐちゃしすぎててよくわかりません。とりあえず動けばいいんですが、それも叶わずじまいで困りました。どうしたものか…。

プログラミング言語処理のテストは何を見ても良いですが、隣の人の回答は見ないで下さいという先生の言葉により、難なく解けました。講義資料をちゃんと印刷してて良かった。

ベクトル解析が全然できなくて悲しい。塚田氏は龍ヶ崎のサイゼで粘ると言っていましたが、俺は粘っても無理っぽいので寝ました。

園芸の畑で焼き芋をしました。途中で雨が降るわ、通報されたのか管理事務所のおやじが来るわで、ギリギリでした。あまり焼けていなかったのか甘くなかったです。
家に帰って焚き火の煙くささを落とそうと、風呂に入ろうとしたらガスが停まってました。ガスメーターを見ると地震か衝撃で止まったと出てる。地震って15日だっけ？16、17と一度もガスを使わなかった…わけないですね。でもガスメーターぶん殴った覚えもないんですがね。
松宮さんのマツタケを食す会＠山下邸に参加しました。マツタケにおぞましいほど虫が付く事にショックを受けつつ。。秋刀魚とお吸い物、炊き込み御飯を食べました。おいしかったです。

山下さんが手伝いをした学会で弁当が大量に余ったと聞き、塚田氏と共にもらいに行きました。なんでも、前日足りなかったから次の日は倍注文したせいらしいです。注文した人は余ったら捨てるつもりだったんでしょうか？もったいない。
ジョーにそろそろヴァイオの音を直してくれと言われ、もらった弁当をおみやげに向かいました。といっても、わかってることはSiSチップというだけ、適当にSiS 630/730系のサウンドチップ（SiS 7018）のドライバを入れてみたら音が出ました。ノイズも乗ってないし、これで正解でしょう。
ついでにWinampの日本語表示だとかMSN Messenger、Winny2のインストールなどもしました。存分にネットを満喫してくださいましー。

16時半頃、震度3の地震がありました。昔、小地震が頻発すれば大地震用のエネルギーが散って安心だと思っていました。M4（ショボ地震）2回 = M8（大地震） と思っていたんですねえ。今となっては笑い話ですが。
ミーティングの直前に塚田氏から宇都宮にいるから行けないというメールがきました。急いでいて超そっけない返事をしてしまい、後でシマッター！と思ったが既に遅かった。
ミーティングの後、定例の食事に行こうと思い、いつもは来ない人々を色々誘ったのですが、つれない返事ばかりでつまんなくなったので一人で帰りました。感じ悪いですね、自分。山下さんは暖かく見守っていて偉いと思いました。自分はだめです。

学園祭3日目。いきなり雨が降り始め、午後には豪雨となりました。客足は雨宿りが居たため見かけ上は増えていました。売上はどうなんだろう。とりあえず植物が完売してよかった。
せっかく見に行ったダイノジが満員で、入り口が学実委に封鎖され見られませんでした。定員がどうのこうの言っていたが、消防法上の問題だろうか。
今日はハングアップした上、記録の書き戻しをミスって履歴が3〜4個消える。補填して計算だけは合わせました。
軽い打ち上げをスタミナ太郎で行いましたが、さみしいことに功労者の2年生女子が誰も来ません。ちかふみさんが食欲なさそうでした（※次の日ダウンしてました）。

学園祭2日目。曇り時々雨がちらつきシケた天気です。昨日より人通りが少ないのは明らかで、喫茶、植物ともに低迷していました。
今日も引き続きPOSシステムを運用しました。自分が見ている分には不都合はなかったように思います。
OB会ではミチタロウが飛ばしてました。OBの方々に就職の相談をしたら、気にしすぎと言われました。

学園祭1日目。天候は曇、喫茶、植物ともに売れ行きは好調です。
POSシステムは時刻の保存を書き忘れていて、序盤の販売履歴の時刻が不明になりました。

学園祭前日。植物を運び、椅子、机を並べるなどし、明日に備えます。二年生が頑張っているお陰であまりバタバタしないで済みますね。感心です。
そうそう簡易POSを明日、仮運用してみようという事になりました。未だにタブの切り替えでハングアップする大問題があるのですが、デバッガで追ってもuser32.dllの中に入っていて良くわからない。デフォルトメッセージ処理でぶっ飛んでるのかなー…？逐次テンポラリファイルに記録をするようにし、一応の安定性は保ちますが、対処療法は好きじゃないよー。でも原因わかんねー。
夕方から喫茶班で販売するパウンドケーキを焼きました。紅茶ケーキがパリッと仕上がっていたのに対し、バナナケーキは妙にフカフカになってかなり崩れていました。バナナの入れすぎかね。おいしいからイイか。