Solving the N-Queens Puzzle by a QUBO Model with Quadratic Size
Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito, Takashi Yazane, Junko Yano, Takumi Kato, Shiro Ozaki, Rie Mori, Ryota Katsuki · 2023
A quadratic unconstrained binary optimization (QUBO) model is defined by an objective function that consists of a quadratic formula involving multiple binary variables. The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the objective function. One of the most well-known problems that can be reduced to a QUBO problem is the N-Queens problem. The N-Queens problem seeks to find a configuration of n queens on an $n\times n$ chessboard such that no two queens can attack each other. It is widely recognized that a conventional technique can be used to design a QUBO model with an $n\times n$ matrix of binary variables representing the chessboard, where a queen is placed in a particular position if and only if the corresponding binary variable is set to 1. This technique involves incorporating terms in the objective function to ensure that the sum of each row and column is 1, and the sum of each diagonal and anti-diagonal is either 0 or 1. The resulting reduced QUBO model contains $\displaystyle \frac{5}{3}n^{3}-2n^{2}+\frac{1}{3}n$ quadratic terms. Due to the simplicity and straightforwardness of designing such a QUBO model, there are numerous resources available that explain this model as an easy example of QUBO models. However, to the best of our knowledge, no fundamentally different approach to designing a QUBO model for the N-Queens problem has been discovered. The prevailing view within the community is that this approach is the only method for designing a QUBO model for the N-Queens problem, and no superior alternative has been found. In this paper, we will present a counterintuitive result that demonstrates a more efficient QUBO model for the N-Queens problem, requiring fewer quadratic terms. Surprisingly, this alternative model involves only $12n^{2}-24n+12$ quadratic terms, which is smaller than the conventional QUBO model whenever n is greater than or equal to 7. This discovery marks a significant breakthrough in the theoretical challenge of minimizing a QUBO model for solving the N-Queens problem.