Putting Queens in Carry Chains, No̱27

摘要: The N-Queens Puzzle is a fascinating combinatorial problem. Up to now, the number of distinct valid placements N non-attacking queens on generalized × chessboard cannot be computed by formula. computation these numbers instead based an exhaustive search whose complexity grows dramatically with problem size N. Solutions counts are currently known for all up 26. parallelization solutions embarrassingly simple. It achieved pre-placing within certain board region. These pre-placements partition space. chosen extent pre-placement allows wide range partitioning granularity. This ease makes great show-off case tremendously parallel approaches and flexible benchmark compute resources. article presents Q27 Project, open-source effort targeting solution count 27-Queens Puzzle. first undertaking pushing frontier that exploits complete symmetry group D4 square. reduces overall computational already eighth in comparison naive exploration whole details coronal enables under this approach. With respect physical implementation computation, it describes hardware structure explores resulting subproblems efficiently exploiting bit-level operations their mapping FPGA devices as well infrastructure organizes contributing distributed computation. performance several platforms evaluated using benchmark, some intriguing observations obtained from available partial presented. Finally, estimate remaining run time expected magnitude final result dared.