Lock-Free Atomic Multithreading and Branchless Bitboards for High-Performance Combinatorial Search: A 77x Speedup on the N-Queens Problem

AbstractThe N-Queens problem is a classical combinatorial benchmark characterized by a non-polynomial (NP-hard) search space. Traditional backtracking solvers suffer from severe control-flow divergence and high memory latency during board-state validation. In this work, we propose a three-layer architectural optimization stack targeting ARM processors.First, we replace array-based board representations with branchless bitboards (bitmasks), eliminating spatial conditional checks and yielding a 7× empirical speedup. Second, we apply geometric symmetry pruning, effectively doubling throughput and achieving a 14× cumulative acceleration. Finally, we introduce an 8-thread lock-free atomic fetch_add work queue, enabling dynamic, zero-overhead load balancing across asymmetric ARM big.LITTLE cores.Evaluated on a consumer-grade ARM Snapdragon mobile processor, the proposed architecture solves the N = 16 instance in 1.71 seconds, representing a 77× speedup over the 132.3 s classical baseline. For the N = 17 instance—yielding exactly 95,815,104 valid solutions—the solver completes in 14.9 seconds, fully saturating the thermal envelope of the mobile silicon.This ablation study demonstrates that stacking data-oriented bitwise design with lock-free concurrency produces massive, multiplicative performance gains in deep combinatorial search problems