ホームページへ戻る  書き込みリストへ戻る
プログラミングパズル雑談コーナー

プログラミングパズルに関心のある人は雑談しましょう!


Nクイーンの記事面白いですね 投稿者: 投稿日:05月29日(火)16時41分59秒


Nクイーンのアルゴリズム読みました。
ビット演算がなかなか渋い処理ですね。

無駄のないビット演算に少ししびれました。
サイト掲載の方法だと手作業を効率化していますよね。

行列とか高度な数学を使ってもっと効率よく求めたりとかないものですか?
ルールの線形性や隣の列の制約の伝播の単純さを考えた時何か賢い方法とかありそうに思えます。

私この分野素人なのですが、やはりこの手の高速化はNP困難問題とかがあって無理とかでしょうか?

http://ailinksh.lolipop.jp/yossii/yossii.html


プログラマー入門 投稿者:プログラマー入門 投稿日:04月25日(水)15時16分13秒


http://1c-job.net
このサイトにはプログラマーとして必要だと思うことが載っています。
これをとっかかりにしてプログラムに興味が出てくること間違いないです。


re:NQueens問題 ( GPU ) 投稿者:deepgreen 投稿日:03月24日(土)21時03分02秒


高橋さん、こんばんは。deepgreenです。

GPUのプログラミングは、deepgreenも今回が初めてです。keiさんに教えていただいて
基本的な処理はできるようになりました。GPUプログラミングも初歩的なものは難しくありません。
(keiさんのように誰か相談できる人がいるとより簡単に入れるでしょう)
nq_symGもカーネル関数は簡単です。PC側はスレッド制御が入っているのでちょっと面倒ですけど。
(これはGPUの知識ではないので必須ではありません)QJHに較べれば、易しいとおもいます。

価格面でいうと、GPUボード1枚は数万円(GTX580)ですので、これをPCIexpressバスに接続して、
ドライバとCUDAのSDKをインストールすればできます。ただし、deepgreenはハードが全くダメなので、
Built-inのゲームパソコンを買いました。それでも、十数万円です。一昔前のPCの値段というところでしょう。
それだけの準備(投資)で、うまくすれば1ケタ性能が上がりますから、おいしい選択枝と考えています。

そもそもの発端は、2010年の7月にkeiさんからQJHのソース公開の依頼から始まりました。
keiさんはGPUを使った並列処理の研究をしていて、その題材にQJHを選んだのです。
しかし、QJHはメモリシステムの負荷が高く、簡単にGPUに乗せることは困難なようです。
(実は、deepgreenは今この問題で悩んでいます。なんとかしたいのですが。。。)
昨年の6月末にGI-26の発表に行く途中でkeiさんとお会いして、Somers(GPU)版にQJHの(I,J)フィルタ
を取り込めば、今より3〜4倍高速になるかもしれませんねという話をしました。その後、keiさんと
その実装を行い、今回のような予想以上の成果となりました。

QJHをどう変えたらGPU向けの構造にできるのかが目下の課題です。


re:NQueens問題 ( GPU ) 投稿者:高橋謙一郎 投稿日:03月24日(土)16時24分49秒


deepgreenさん、こんちには。

N=23を約12時間で処理したとは、ただただ唖然とするのみです。

概要はなんとなく理解しましたが、ソースコードは全く理解不能です。
GPUをソルバーに利用するという新しい試みには大いに興味が沸いたのですが、
GPUを理解するのに時間とお金がかかりそう、という高い敷居も感じます。
とはいうものの、新しい風を感じます。今はチンプンカンプンですが。


NQueens問題 ( GPU ) 投稿者:deepgreen 投稿日:03月23日(金)19時50分50秒

こんばんは。 deepgreenです。

2012年3月2日に行われた第27回ゲーム情報学研究会(GI-27)に、GPU(グラフィックアクセラレータ)
を使った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/


GPCC:最小公倍図形の問題の探索結果 投稿者:deepgreen 投稿日:12月02日(金)08時58分23秒

こんにちは。deepgreenです。

今年の始めに、GPCCの最小公倍図形の問題に挑戦すると書いてしまったので、
その結果をお知らせします。

今回の探索の結果、Tペントミノ68個の解があることをみつけました。結果は、
下記のdeepgreenのHPにUpしましたので、お時間がありましたらどうぞ。

    http://deepgreen.game.coocan.jp/
    


エアリアル! 投稿者:breathe 投稿日:11月11日(金)23時50分00秒


・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
◎・・・・・・・・・・・・・・・・★・・・・・・・・・・∩
※・・・・・・・・・・・・・・・・□・・・・・・・・・・∪
・・・・・・・・・・・・・・∩・・・・・・・・・・・・・□
・・・・・・・・□・・☆・・∪・・・・・・・□・・□・・・
□・・・・・・・・・・☆・・□・・・・・・・・・・・・・□
・・・□・・・・・・☆★・・◎・・□・・・・・・・・・・・
□・・・・・・・・・※※・・※・・・・・・・・・★★・・□
・・・・・・★・・・・・・・・・・・・・・・・・※※・・・
・・・・・・※・・・・・・・・・・・・・★・・・・・・・□
・・・・・・・・・・・・・・・・・・・・※・・・・・回田・
・・・・・・・・・・・・・・・・・・・・・・・・・・田田□
・☆・・・・・・・・・・☆・☆・☆・・・・・・・・・田田・
※※≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡※※※※


殺すことだけを考えた 投稿者:ababa 投稿日:10月27日(木)21時09分40秒


★⊂⊃⊂⊃★☆⊂⊃⊂⊃★⊂⊃☆⊂⊃☆⊂⊃☆★☆⊂⊃☆⊂⊃★
☆☆・★・⊂⊃・★★・⊂⊃☆☆・★⊂⊃⊂⊃⊂⊃・⊂⊃・⊂⊃
⊂⊃⊂⊃★・★☆⊂⊃☆☆・⊂⊃☆⊂⊃☆・★☆・☆★・☆☆・
・★・★⊂⊃⊂⊃・★⊂⊃・★⊂⊃・★⊂⊃⊂⊃⊂⊃⊂⊃⊂⊃☆
◎⊂⊃⊂⊃☆★・・⊂⊃★⊂⊃★⊂⊃⊂⊃★・☆★・・☆★・☆
☆・★・☆⊂⊃⊂⊃・★※★⊂⊃★⊂⊃★⊂⊃⊂⊃⊂⊃⊂⊃⊂⊃
☆・⊂⊃※★・・★・⊂⊃※★・※・★⊂⊃☆★・・☆・☆☆・
☆・・★⊂⊃★⊂⊃☆・★⊂⊃⊂⊃⊂⊃☆★⊂⊃⊂⊃⊂⊃⊂⊃☆
☆・・⊂⊃⊂⊃☆⊂⊃☆⊂⊃☆・☆★・☆⊂⊃・☆☆☆★・★☆
☆・・・☆・⊂⊃☆⊂⊃・★⊂⊃⊂⊃⊂⊃・☆⊂⊃⊂⊃⊂⊃⊂⊃
☆回田・※・☆・※・☆・※★・・☆・★・※☆・★・・☆・★
☆田田●・⊂⊃・●・⊂⊃・●・⊂⊃・●・⊂⊃・●・⊂⊃・★
☆田田※≡≡≡≡※≡≡≡≡※≡≡≡≡※≡≡≡≡※≡≡≡≡≡
≡※※※※※※※※※※※※※※※※※※※※※※※※※※※※


箸休めに(まだ迷宮の途中) 投稿者:ramimama 投稿日:10月11日(火)10時33分18秒


・・・・・・・・・・・・・・・・・・・・・・・・・・・●・
・・・・・・・・・・・・・・・・・・・・・・・・・・・□□
・・・・・・・・・・・・・・・・・・・・・・回田・・・□□
・◎・◎・・・●・・・・・・・・・・・・∩∩田田・・・□□
・□・□・・□□・・・・・・・・・・・・∪∪田田・・・□□
・□・□・・・・・・・・・・・・・・・□□□□□□・・□□
・・・・・・・・・・・・・・∩・・・・□□□□□□・・・□
・・・・・・・・・・・・・・∪・・・・□・・・・・・・・□
・・・・・・・・・・・・□□□□□□□□・・・・・・・・□
・・・・・・・・・・・・・・・・・・・・・・・・・・・・□
・・・・・・・・・・・・・・・・・・・・・・・・※・・・・
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
・・・・・・・・・・・※※※・・・・・・・・・・※∩・・・
≡≡≡≡≡≡≡≡≡≡≡※※※・・・・・・・・・◎※∪●・・


迷宮のアンドローラ! 投稿者:breathe 投稿日:09月13日(火)19時12分20秒


・・・・・・・・・・☆・・・・・・・・◎・・・・・・・◎・
∩・・・・・・・・・※・・・・・・・・※・・・・・・・●・
∪・・・・・・・・・・・・・・◎・・・・・・・・・・・□・
□・・・・・・・・・・・・・・□・・・・・・・□・・・□・
・・・□・・□・・・・・・・・・・・・・・・・・・・・・◎
・・・・・・・・・・□・・・□・・・・・・□・・□・・・□
・・・・・・・・・・・・・・・・・・・●・・・・・・・・・
☆・・・・・・・・・・・□・・・・・・※・・・・・・・・・
※※※・・・・・・・・・□・・・・※・・・・・・※・・・・
※・・□□・・□・・・・□・・□・・・・・・・・・□・・・
※※※・・・・・・・・・・回田・・・・・・・・・・・・・・
※・・・∩・・∩・・・・・田田・・・・・・・・・・・・・・
※・☆・∪・・∪※・※・・田田・・・・・・※・・・・・・※
≡≡≡≡≡≡※※※≡※※※※※※※≡≡≡≡≡≡≡※※≡≡≡


 ホームページへ戻る  書き込みリストへ戻る