{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,14]],"date-time":"2026-01-14T17:11:46Z","timestamp":1768410706854,"version":"3.49.0"},"reference-count":29,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T00:00:00Z","timestamp":1613952000000},"content-version":"vor","delay-in-days":52,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672123"],"award-info":[{"award-number":["61672123"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The N\u2010Queens problem plays an important role in academic research and practical application. Heuristic algorithm is often used to solve variant 2 of the N\u2010Queens problem. In the process of solving, evaluation of the candidate solution, namely, fitness function, often occupies the vast majority of running time and becomes the key to improve speed. In this paper, three parallel schemes based on CPU and four parallel schemes based on GPU are proposed, and a serial scheme is implemented at the baseline. The experimental results show that, for a large\u2010scale N\u2010Queens problem, the coarse\u2010grained GPU scheme achieved a maximum 307\u2010fold speedup over a single\u2010threaded CPU counterpart in evaluating a candidate solution. When the coarse\u2010grained GPU scheme is applied to simulated annealing in solving N\u2010Queens problem variant 2 with a problem size no more than 3000, the speedup is up to 9.3.<\/jats:p>","DOI":"10.1155\/2021\/6694944","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T03:20:09Z","timestamp":1614050409000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parallel Implementations of Candidate Solution Evaluation Algorithm for N\u2010Queens Problem"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4011-1509","authenticated-orcid":false,"given":"Jianli","family":"Cao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9209-2189","authenticated-orcid":false,"given":"Zhikui","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5133-3978","authenticated-orcid":false,"given":"Yuxin","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0955-7692","authenticated-orcid":false,"given":"He","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_9_1_2","article-title":"Proposal of eight queens problem","volume":"3","author":"Bezzel F. W. M.","year":"1848","journal-title":"Berliner Schachzeitung"},{"key":"e_1_2_9_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.12.043"},{"key":"e_1_2_9_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/2689192"},{"key":"e_1_2_9_4_2","unstructured":"SomersJ. The n-queens problem - a study in optimization. [EB\/OL] 2019 http:\/\/jsomers.com\/nqueendemo\/nqueens."},{"key":"e_1_2_9_5_2","unstructured":"KiseK. KatagiriT. HondaH. andYubaT. Solving the 24-queens problem using Mpi on a Pc cluster 2004 Graduate School of Information Systems The University of Electro-Communications Tokyo Japan Technical Report."},{"key":"e_1_2_9_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2007.02.011"},{"key":"e_1_2_9_7_2","unstructured":"Preu\u00dferT. B. NagelB. andSpallekR. G. Putting queens in carry chains 2009 Technische Universit\u00e4t Dresden Dresden Germany Technical Report."},{"key":"e_1_2_9_8_2","doi-asserted-by":"crossref","unstructured":"CarneiroT. MuritibaA. E. NegreirosM. andLima De CamposG. A. A new parallel schema for branch-and-bound algorithms using gpgpu Proceedings of the 2011 23rd International Symposium on Computer Architecture and High Performance Computing October 2011 Washington DC USA 41\u201347.","DOI":"10.1109\/SBAC-PAD.2011.20"},{"key":"e_1_2_9_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/tpds.2014.2345054"},{"key":"e_1_2_9_10_2","doi-asserted-by":"crossref","unstructured":"FeinbubeF. RabeB. Von L\u00f6wisM. andPolzeA. Nqueens on cuda: optimization issues Proceedings of the 2010 Ninth International Symposium on Parallel and Distributed Computing July 2010 Istanbul Turkey.","DOI":"10.1109\/ISPDC.2010.22"},{"key":"e_1_2_9_11_2","unstructured":"AmrasingheD. N-queens problem with gpgpu (presentation) 2007 University of North Texas Denton TX USA Technical Report."},{"key":"e_1_2_9_12_2","unstructured":"PamplonaV. N-queens problem: a comparison between cpu and gpu using c++ and cuda (presentation) 2008 Universidade Federal do Rio Grande do Sul Porto Alegre Brazil Technical Report."},{"key":"e_1_2_9_13_2","doi-asserted-by":"crossref","unstructured":"ZhangT. ShuW. andWuM. Y. Optimization of N-queens solvers on graphics processors Proceedings of the 9th International Conference on Advanced Parallel Processing Technologies August 2011 Berlin Heidelberg.","DOI":"10.1007\/978-3-642-24151-2_11"},{"key":"e_1_2_9_14_2","doi-asserted-by":"crossref","unstructured":"ThoutiK.andSatheS. R. Solving N-queens problem on gpu architecture using opencl with special reference to synchronization issues Proceedings of the 2012 2nd IEEE International Conference on Parallel Distributed and Grid Computing December 2012 Himachal Pradesh India.","DOI":"10.1109\/PDGC.2012.6449926"},{"key":"e_1_2_9_15_2","doi-asserted-by":"crossref","unstructured":"PlauthM. FeinbubeF. SchlegelF. andPolzeA. Using dynamic parallelism for fine-grained irregular workloads: a case study of the n-queens problem Proceedings of the 2015 Third International Symposium on Computing and Networking (CANDAR) December 2015 Hokkaido Japan.","DOI":"10.1109\/CANDAR.2015.26"},{"key":"e_1_2_9_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4374"},{"key":"e_1_2_9_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-15996-2_2"},{"key":"e_1_2_9_18_2","unstructured":"HuX. EberhartR. C. andShiY. Swarm intelligence for permutation optimization: a case study of n-queens problem Proceedings of the 2003 IEEE Swarm Intelligence Symposium. SIS\u201903 (Cat. No.03EX706) April 2003 Indianapolis IN. USA 243\u2013246."},{"key":"e_1_2_9_19_2","doi-asserted-by":"publisher","DOI":"10.7763\/ijcee.2014.v6.828"},{"key":"e_1_2_9_20_2","first-page":"109","article-title":"On chemical reaction optimization for eight queens problem","volume":"35","author":"Guang-Yong X. Y. M.","year":"2014","journal-title":"Journal of Hengyang Normal University"},{"key":"e_1_2_9_21_2","first-page":"123","article-title":"A global optimization algorithms with integer encoding","volume":"24","author":"Nengfa H.","year":"2002","journal-title":"Journal of Hubei University"},{"key":"e_1_2_9_22_2","first-page":"123","article-title":"On-chip multi-core parallel hybrid genetic algorithm for solving n-queens problem","volume":"41","author":"Buzhong C. Y.","year":"2015","journal-title":"Computer Engineering"},{"key":"e_1_2_9_23_2","doi-asserted-by":"crossref","unstructured":"TurkyA. M.andAhmadM. S. Using genetic algorithm for solving n-queens problem Proceedings of the 2010 International Symposium on Information Technology 2010 International Symposium on Information Technology June 2010 Kuala Lumpur Malaysia.","DOI":"10.1109\/ITSIM.2010.5561604"},{"key":"e_1_2_9_24_2","doi-asserted-by":"crossref","unstructured":"WangK. JiZ. andZhouY. A parallel genetic algorithm based on Mpi for N-queen Proceedings of the 2017 2nd International Conference on Control Automation and Artificial Intelligence (CAAI 2017) June 2017 Sanya China.","DOI":"10.2991\/caai-17.2017.85"},{"key":"e_1_2_9_25_2","doi-asserted-by":"publisher","DOI":"10.1111\/coin.12300"},{"key":"e_1_2_9_26_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_9_27_2","unstructured":"NVIDIA CUDAC Programming Guide NVIDIA 2016."},{"key":"e_1_2_9_28_2","volume-title":"The World\u2019s Fastest GPU Accelerator","author":"NVIDIA, NVIDIA TESLA K80","year":"2014"},{"key":"e_1_2_9_29_2","unstructured":"NVIDIA CUDA Profiler Users Guide NVIDIA 2016."}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2021\/6694944.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2021\/6694944.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2021\/6694944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T23:07:01Z","timestamp":1723244821000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2021\/6694944"}},"subtitle":[],"editor":[{"given":"Leo Y.","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1155\/2021\/6694944"],"URL":"https:\/\/doi.org\/10.1155\/2021\/6694944","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"value":"1076-2787","type":"print"},{"value":"1099-0526","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"2020-11-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"6694944"}}