@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00078257,
 author = {田中, 慶悟 and 藤本, 典幸 and Keigo, Tanaka and Noriyuki, Fujimoto},
 book = {ゲームプログラミングワークショップ2011論文集},
 issue = {6},
 month = {Oct},
 note = {近年，汎用計算ができるようになったGPU上でCUDAを用いて，Somersの高速なN-Queens問題求解アルゴリズムをさらに高速化する手法を提案する．提案手法はN-Queens問題をSomersのアルゴリズムで計算可能かつ独立な部分問題の集合にCPU上で分割し，生成した部分問題をGPUのVRAM上へと転送し，各スレッドへ動的に割り当て，効率よく並列計算を行う．評価実験を行ったところ，NVIDIA GeForce GTX480と2.93 GHz Intel Core i3 CPUを用いた場合，提案手法はSomersのアルゴリズムと比べN＝19で24.5倍高速であった．また，GPUを用いたFeinbubeらの既存手法に比べ，提案手法は2倍高速であった．, In recent years, GPUs have acquired the ability to perform general purpose computation. In this paper, for CUDA GPUs, we propose a method to parallelize Somers' fast sequential algorithm to solve the N-Queens problem. The proposed method partitions a given instance of the N-Queens problem into sub-problems which can be computed in parallel. Then, the sub-problems are sent to VRAM on a GPU so that each sub-problem is dynamically allocated to a thread. Experimental results on an NVIDIA GeForce GTX480 and a 2.93 GHz Intel Core i3 CPU show that the proposed method solves the 19-Queens problem 24.5 times faster than Somers' sequential algorithm and that the proposed method is twice faster than Feinbube et al.'s existing method for CUDA GPUs.},
 pages = {76--83},
 publisher = {情報処理学会},
 title = {GPUを用いたN-Queens問題の求解},
 volume = {2011},
 year = {2011}
}