コグノスケ

C言語でNクイーン問題

目次: ベンチマーク

Nクイーンを解かせるプログラムを組んでみました。結果は15クイーン（解2279184通り）で2分14秒 でした（コンパイラ: Visual C++ 6.0 release build）。Athlon 1.4GHzのくせにこんなです。ええ、ええ、遅々ですよ、わかってますとも(´・ω・｀)
ネット上で見つけた、高橋謙一郎さんという方が作ったプログラムは15クイーンが1秒12でした。いやはや速すぎます。高橋さんのページを読むに、ユニーク解を用いると無駄な検索を省けるようですが、よくわからなかったので組み込めそうにありません。悲しい限りです。
注: Nクイーン問題とはn x nの大きさのチェスの盤にn個のクイーンを互いに取られない位置に置くパターンがいくつあるかを求める問題のこと。

追記です。15クイーンは左右対称性を利用して検索を半分カットし、動的配列の使用を止め、静的配列にしたところ21秒になりました。これだけで7倍も速くなるんですねえ。でもまだ2ケタ秒かかっていて遅い事に変わりはないですがね。
大西洋単独横断で英雄となったリンドバーグ（Charles Augustus Lindbergh 1902-1974アメリカ）の「The Spirit of St.Louis」の邦題「翼よ、あれがパリの灯だ」がカッコイイなーと思いました。意訳しすぎと思う方もいるかな、私は訳者のセンスが感じられて良いなーと思ってます。少なくとももろにカタカナ英語にするよりは良いでしょ。