プログラミングパズルに関心のある人は雑談しましょう！
Ｎクイーンのアルゴリズム読みました。 ビット演算がなかなか渋い処理ですね。 無駄のないビット演算に少ししびれました。 サイト掲載の方法だと手作業を効率化していますよね。 行列とか高度な数学を使ってもっと効率よく求めたりとかないものですか？ ルールの線形性や隣の列の制約の伝播の単純さを考えた時何か賢い方法とかありそうに思えます。 私この分野素人なのですが、やはりこの手の高速化はＮＰ困難問題とかがあって無理とかでしょうか？
http://1c-job.net このサイトにはプログラマーとして必要だと思うことが載っています。 これをとっかかりにしてプログラムに興味が出てくること間違いないです。
高橋さん、こんばんは。deepgreenです。 ＧＰＵのプログラミングは、deepgreenも今回が初めてです。keiさんに教えていただいて 基本的な処理はできるようになりました。ＧＰＵプログラミングも初歩的なものは難しくありません。 (keiさんのように誰か相談できる人がいるとより簡単に入れるでしょう) nq_symGもカーネル関数は簡単です。ＰＣ側はスレッド制御が入っているのでちょっと面倒ですけど。 (これはＧＰＵの知識ではないので必須ではありません）ＱＪＨに較べれば、易しいとおもいます。 価格面でいうと、ＧＰＵボード1枚は数万円(GTX580)ですので、これをPCIexpressバスに接続して、 ドライバとＣＵＤＡのＳＤＫをインストールすればできます。ただし、deepgreenはハードが全くダメなので、 Built-inのゲームパソコンを買いました。それでも、十数万円です。一昔前のＰＣの値段というところでしょう。 それだけの準備(投資）で、うまくすれば1ケタ性能が上がりますから、おいしい選択枝と考えています。 そもそもの発端は、2010年の7月にkeiさんからＱＪＨのソース公開の依頼から始まりました。 keiさんはＧＰＵを使った並列処理の研究をしていて、その題材にＱＪＨを選んだのです。 しかし、ＱＪＨはメモリシステムの負荷が高く、簡単にＧＰＵに乗せることは困難なようです。 (実は、deepgreenは今この問題で悩んでいます。なんとかしたいのですが。。。） 昨年の6月末にGI-26の発表に行く途中でkeiさんとお会いして、Somers(GPU)版にＱＪＨの（I,J)フィルタ を取り込めば、今より３〜４倍高速になるかもしれませんねという話をしました。その後、keiさんと その実装を行い、今回のような予想以上の成果となりました。 ＱＪＨをどう変えたらＧＰＵ向けの構造にできるのかが目下の課題です。
deepgreenさん、こんちには。 N=23を約12時間で処理したとは、ただただ唖然とするのみです。 概要はなんとなく理解しましたが、ソースコードは全く理解不能です。 GPUをソルバーに利用するという新しい試みには大いに興味が沸いたのですが、 GPUを理解するのに時間とお金がかかりそう、という高い敷居も感じます。 とはいうものの、新しい風を感じます。今はチンプンカンプンですが。
こんばんは。 deepgreenです。
2012年3月2日に行われた第27回ゲーム情報学研究会(GI-27)に、ＧＰＵ(グラフィックアクセラレータ）
を使ったNQueens問題の高速Solverについて発表しました。
主な成果は、以下のとおりです。
測定環境：ゲームパソコン1台
( Intel CORE i7 2600 3.4GHz CPU と NVIDIA GeForce GTX580)
・N=23の問題の求解時間 12H 09M 43S --> 電通大のPCクラスタの約4.7倍高速
・Somers版(オリジナル版）の約166〜196倍高速
その時の論文とソースを下記のdeepgreenのHPで公開します。
http://deepgreen.game.coocan.jp/
こんにちは。deepgreenです。
今年の始めに、ＧＰＣＣの最小公倍図形の問題に挑戦すると書いてしまったので、
その結果をお知らせします。
今回の探索の結果、Ｔペントミノ６８個の解があることをみつけました。結果は、
下記のdeepgreenのＨＰにＵｐしましたので、お時間がありましたらどうぞ。
http://deepgreen.game.coocan.jp/
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ ◎・・・・・・・・・・・・・・・・★・・・・・・・・・・∩ ※・・・・・・・・・・・・・・・・□・・・・・・・・・・∪ ・・・・・・・・・・・・・・∩・・・・・・・・・・・・・□ ・・・・・・・・□・・☆・・∪・・・・・・・□・・□・・・ □・・・・・・・・・・☆・・□・・・・・・・・・・・・・□ ・・・□・・・・・・☆★・・◎・・□・・・・・・・・・・・ □・・・・・・・・・※※・・※・・・・・・・・・★★・・□ ・・・・・・★・・・・・・・・・・・・・・・・・※※・・・ ・・・・・・※・・・・・・・・・・・・・★・・・・・・・□ ・・・・・・・・・・・・・・・・・・・・※・・・・・回田・ ・・・・・・・・・・・・・・・・・・・・・・・・・・田田□ ・☆・・・・・・・・・・☆・☆・☆・・・・・・・・・田田・ ※※≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡※※※※
★⊂⊃⊂⊃★☆⊂⊃⊂⊃★⊂⊃☆⊂⊃☆⊂⊃☆★☆⊂⊃☆⊂⊃★ ☆☆・★・⊂⊃・★★・⊂⊃☆☆・★⊂⊃⊂⊃⊂⊃・⊂⊃・⊂⊃ ⊂⊃⊂⊃★・★☆⊂⊃☆☆・⊂⊃☆⊂⊃☆・★☆・☆★・☆☆・ ・★・★⊂⊃⊂⊃・★⊂⊃・★⊂⊃・★⊂⊃⊂⊃⊂⊃⊂⊃⊂⊃☆ ◎⊂⊃⊂⊃☆★・・⊂⊃★⊂⊃★⊂⊃⊂⊃★・☆★・・☆★・☆ ☆・★・☆⊂⊃⊂⊃・★※★⊂⊃★⊂⊃★⊂⊃⊂⊃⊂⊃⊂⊃⊂⊃ ☆・⊂⊃※★・・★・⊂⊃※★・※・★⊂⊃☆★・・☆・☆☆・ ☆・・★⊂⊃★⊂⊃☆・★⊂⊃⊂⊃⊂⊃☆★⊂⊃⊂⊃⊂⊃⊂⊃☆ ☆・・⊂⊃⊂⊃☆⊂⊃☆⊂⊃☆・☆★・☆⊂⊃・☆☆☆★・★☆ ☆・・・☆・⊂⊃☆⊂⊃・★⊂⊃⊂⊃⊂⊃・☆⊂⊃⊂⊃⊂⊃⊂⊃ ☆回田・※・☆・※・☆・※★・・☆・★・※☆・★・・☆・★ ☆田田●・⊂⊃・●・⊂⊃・●・⊂⊃・●・⊂⊃・●・⊂⊃・★ ☆田田※≡≡≡≡※≡≡≡≡※≡≡≡≡※≡≡≡≡※≡≡≡≡≡ ≡※※※※※※※※※※※※※※※※※※※※※※※※※※※※
・・・・・・・・・・・・・・・・・・・・・・・・・・・●・ ・・・・・・・・・・・・・・・・・・・・・・・・・・・□□ ・・・・・・・・・・・・・・・・・・・・・・回田・・・□□ ・◎・◎・・・●・・・・・・・・・・・・∩∩田田・・・□□ ・□・□・・□□・・・・・・・・・・・・∪∪田田・・・□□ ・□・□・・・・・・・・・・・・・・・□□□□□□・・□□ ・・・・・・・・・・・・・・∩・・・・□□□□□□・・・□ ・・・・・・・・・・・・・・∪・・・・□・・・・・・・・□ ・・・・・・・・・・・・□□□□□□□□・・・・・・・・□ ・・・・・・・・・・・・・・・・・・・・・・・・・・・・□ ・・・・・・・・・・・・・・・・・・・・・・・・※・・・・ ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ ・・・・・・・・・・・※※※・・・・・・・・・・※∩・・・ ≡≡≡≡≡≡≡≡≡≡≡※※※・・・・・・・・・◎※∪●・・
・・・・・・・・・・☆・・・・・・・・◎・・・・・・・◎・ ∩・・・・・・・・・※・・・・・・・・※・・・・・・・●・ ∪・・・・・・・・・・・・・・◎・・・・・・・・・・・□・ □・・・・・・・・・・・・・・□・・・・・・・□・・・□・ ・・・□・・□・・・・・・・・・・・・・・・・・・・・・◎ ・・・・・・・・・・□・・・□・・・・・・□・・□・・・□ ・・・・・・・・・・・・・・・・・・・●・・・・・・・・・ ☆・・・・・・・・・・・□・・・・・・※・・・・・・・・・ ※※※・・・・・・・・・□・・・・※・・・・・・※・・・・ ※・・□□・・□・・・・□・・□・・・・・・・・・□・・・ ※※※・・・・・・・・・・回田・・・・・・・・・・・・・・ ※・・・∩・・∩・・・・・田田・・・・・・・・・・・・・・ ※・☆・∪・・∪※・※・・田田・・・・・・※・・・・・・※ ≡≡≡≡≡≡※※※≡※※※※※※※≡≡≡≡≡≡≡※※≡≡≡