High-Performance N-Queens Solver on GPU: Iterative DFS with Zero Bank Conflicts
The counting of solutions to the N-Queens problem is a classic NP-complete problem with extremely high computational complexity. As of now, the academic communi...
Abstract
The counting of solutions to the N-Queens problem is a classic NP-complete problem with extremely high computational complexity. As of now, the academic community has rigorously verified the number of solutions only up to N <= 26. In 2016, the research team led by PreuBer solved the 27-Queens problem using FPGA hardware, which took approximately one year, though the result remains unverified independently. Recent studies on GPU parallel computing suggest that verifying the 27-Queens solution would still require about 17 months, indicating excessively high time and computational resource costs. To address this challenge, we propose an innovative parallel computing method on NVIDIA GPU platform, with the following core contributions: (1) An iterative depth-first search (DFS) algorithm for solving the N-Queens problem; (2) Complete mapping of the required stack structure to GPU shared memory; (3) Effective avoidance of bank conflicts through meticulously designed memory access patterns; (4) Various optimization techniques are employed to achieve optimal performance. Under the proposed optimization framework, we successfully verified the 27-Queens problem in just 28.4 days using eight RTX 5090 GPUs, thereby confirming the correctness of PreuBer's computational results. Moreover, we have reduced the projected solving time for the next open case-the 28-Queens problem-to approximately 11 months, making its resolution computationally feasible. Compared to the state-of-the-art GPU methods, our method achieves over 10x speedup on identical hardware configurations (8 A100), while delivering over 26x acceleration when utilizing 8 RTX 5090 GPUs, and brings fresh perspectives to this long-stagnant problem.
Access Full Paper
This research paper is available on arXiv, an open-access archive for academic preprints.
Citation
Guangchao Yao. "High-Performance N-Queens Solver on GPU: Iterative DFS with Zero Bank Conflicts." arXiv preprint. 2025-11-15. http://arxiv.org/abs/2511.12009v1
About arXiv
arXiv is a free distribution service and open-access archive for scholarly articles in physics, mathematics, computer science, quantitative biology, quantitative finance, statistics, electrical engineering, systems science, and economics.
Disclaimer: This article is for informational purposes only and does not constitute financial advice. Consult a licensed financial advisor before making investment decisions.
Related Articles
Disclaimer
This article is for informational purposes only and does not constitute financial, legal, or tax advice. SwissFinanceAI is not a licensed financial services provider. Always consult a qualified professional before making financial decisions.
References
- [1]ResearchCredibility: 9/10Guangchao Yao. "High-Performance N-Queens Solver on GPU: Iterative DFS with Zero Bank Conflicts." arXiv.org. November 15, 2025. Accessed November 18, 2025.
Transparency Notice: This article may contain AI-assisted content. All citations link to verified sources. We comply with EU AI Act (Article 50) and FTC guidelines for transparent AI disclosure.
Original Source
This article is based on High-Performance N-Queens Solver on GPU: Iterative DFS with Zero Bank Conflicts (arXiv.org)
