Solving N-Queens Puzzle with Q#
This is a project in the Intro to Quantum Computing course instructed by Professor Mariia Mykhailova at Northeastern University.
This post is part of the Q# Holiday Calendar 2022. Check out the calendar for more great posts!
What’s the puzzle we are going to solve?
In the rules of chess, a queen can move horizontally, vertically, or diagonally to any vacant square on the board. The N-Queens puzzle applies this same rule and challenges players to place N queens on an N x N chessboard without allowing any two queens to attack each other.
This puzzle was first introduced in the 19th century, and it is NP-complete.
The project also introduced a variation of the N-Queens puzzle called the N-Queens² puzzle. In this version, every square on the board is occupied by a queen, but there are N different colors of queens, and queens of the same color cannot attack each other.
Traditional Solution
A backtracking algorithm is used to solve the puzzle, and the highest order that has been solved is 27. The time complexity is O(N!), and the space complexity is O(N). A list of solutions is the following:
Quantum solution
Grover’s search algorithm is used to solve the two puzzles, and the steps are described below. Most of the steps are referred from [1].
N-Queens Puzzle
The solutions to the puzzle are specific permutations of a N x N chessboard. They can be described with three constraints. First, each row has only one queen. Second, each column has only one queen. Last, each diagonal has either zero or one queen.
To prepare for the initial state, N x N qubits are allocated to represent a chessboard. A ⎸0⟩ state indicates an empty square, and a ⎸1⟩ state indicates a queen is placed on the square. The initial state of a chessboard when N = 4 can be represented as,
Then, the row constraint can be prepared to a W state, which guarantees a row has only one queen. For example, when N = 4, a queen could be in one of the four positions in a row as,
The preparation of the W state can be found in QuantumKatas [5].
There are 4 rows, and the state of the chessboard can be represented as,
After the row constraint state is prepared, an oracle is created to apply the restrictions. The results of the column and diagonal checks are stored in the auxiliary qubits. The target qubit will be flipped when the restrictions are fulfilled, which means the auxiliary qubits are all in the ⎸1⟩ state.
The column constraint is checked by applying a controlled X gate on each square in the same column. The auxiliary qubits will be in the ⎸1⟩ state if the sum of the queens is odd. Since each row state ensures that there are a total of N queens on the board, if any one of the columns has an odd number of queens greater than one, then there must be two or more columns with no queens, and the corresponding auxiliary qubits will be in the ⎸0⟩ state.
Furthermore, only N-1 columns need to be examined, that is, only N-1 auxiliary qubits need to be allocated. If N 1s add up to N and 0 exists among them, then there must have an even number of 0s. It is impossible that the first N-1 column satisfies the requirement, but the last column has no queen or two more queens. So, only N-1 columns need to be checked. The following figures show how column checks are performed and an example that the column constraint is not satisfied.
Next, diagonal verifications proceeded between each pair of rows. There are N ⨉ (N-1) / 2 such checks that need to be performed, and the results are stored in auxiliary qubits. The auxiliary qubits are initialized in the ⎸1⟩ states. If two queens are in the same diagonal pair, the corresponding auxiliary qubit will be flipped to the ⎸0⟩ state by a CCNOT gate. If all the auxiliary qubits remain in the ⎸1⟩ state, it means that the diagonal requirement is satisfied. Because each row has only one queen, it is impossible to have more than one diagonal pair of queens, so the auxiliary qubits will not be flipped more than once. The following animation shows examples of diagonal checks.
Finally, the two auxiliary qubit arrays for the column and diagonal checks are concatenated and used to control the target qubit in the oracle. The target qubit will be flipped if all the requirements are satisfied, which indicates that a valid solution to the N-Queens puzzle has been found.
// psuedo code
operation OracleNQueensConstraint (register: Qubit[], target: Qubit) : Unit is Adj{
use auxQCol = Qubit[nQueens - 1];
use auxQDia = Qubit[(nQueens * (nQueens - 1)) / 2];
within {
checkColumn();
ApplyToEachA(X, auxQDia);
checkDiagonal();
} apply {
Controlled X(auxQCol + auxQDia, target);
}
}N-Queens² Puzzle
The solutions to the N-Queens² puzzle are also particular permutations of the N ⨉ N chessboard. It requires that each row, column, and diagonal on the chessboard contain queens of different colors.
To represent the different colors of the queens, multiple qubits are used to represent one queen. For example, when N = 5, three qubits are used to represent the 5 different colors from 0 to 4 using little-endian notation.
The first step is to allocate N by N by M-color-bit qubits to represent each square on a chessboard. Where N is the number of queens, and M is the number of qubits needed to represent a color.
Then, each row can be prepared as a combination of different colors of queens. For example, when N = 3, one of the possible row combinations can be represented as,
As a result, each row has only one queen per color.
The preparation of the row state can be found in QuantumKatas [5].
There are 3 rows on a chessboard, so the chessboard can be represented as,
Similar to the N-Queens puzzle, auxiliary qubits are used in the oracle to store the results of column and diagonal checks. However, this expands to include each color per column. An auxiliary qubit is flipped to ⎸1⟩ when the number of queens of the same color on a column is even. Each column requires N auxiliary qubits to perform the check, and a total of N ⨉ (N-1) qubits are needed for all columns.
The row state preparation ensures that the colors on each row are different. If one of the columns has an odd number of queens of the same color, there must be at least two columns with no queens of that color. Therefore, only N-1 columns need to be examined, and only N ⨉ (N-1) auxiliary qubits need to be allocated. It is impossible for N-1 columns to have no repeated colors but for the last column to have repeated colors of queens. Figure 6 shows how column checks are performed when N = 3.
Next, diagonal verifications are performed between each pair of rows per color. There are N ⨉ N ⨉ (N-1) / 2 such checks that need to be performed, and the results are stored in auxiliary qubits. These qubits are initialized in the ⎸1⟩ state. If two queens of the same color are on the same diagonal, the corresponding auxiliary qubit is flipped to the ⎸0⟩ state using a controlled bit string gate. If all auxiliary qubits remain in the ⎸1⟩ state, it means that the diagonal requirement has been satisfied. Because each row and column has only one queen per color, it is impossible to have more than one diagonal pair of queens with the same color, so the auxiliary qubits will not be flipped more than once. The following videos are the process of diagonal checks.
To finish, the two arrays of auxiliary qubits for the column and diagonal checks are combined and used to control the target qubit in the oracle. If all requirements are satisfied, the target qubit will be flipped, indicating that a valid solution to the N-Queens² puzzle has been found.
// psuedo code
operation OracleNQueensSquareConstraint (register: Qubit[], target: Qubit) : Unit is Adj{
use auxQCol = Qubit[nQueens * (nQueens - 1)];
use auxQDia = Qubit[nQueens * (nQueens * (nQueens - 1)) / 2];
within {
checkColumn();
ApplyToEachA(X, auxQDia);
checkDiagonal();
} apply {
Controlled X(auxQCol + auxQDia, target);
}
}Analysis
N-Queens
- The search space size is Nᴺ while each row has N possible combinations, and there are N rows.
- The qubits allocated explicitly are:
- The operations needed for columns: N ⨉ (N-1)
- The operations needed for diagonal:
N-Queens²
- The search space size is N!ᴺ while each row has N! possible combinations, and there are N rows.
- The qubits allocated explicitly are:
- The operations needed for columns: N ⨉ N ⨉ (N-1)
- The operations needed for diagonal:
Comparison
According to the analysis, the qubits needed for N-Queens² are too many for the local environment, so a modified version without the diagonal restriction is executed in the experiments. The following tables show a comparison between different parameters before the experiments.
Experiments
I implement the algorithm with Q# and Quantum Development Kit (QDK), and execute it on Azure Quantum. The full codes is here.
There are three methods used in the experiments.
Results
N-Queens in Local Environment with Sparse Simulator
N-Queens on Azure Resource Estimator
The full results of N=4 and N=5 are linked.
N-Queens² without diagonal restriction in Local Environment with Sparse Simulator
Real Hardware (Rigetti Provider)
The resources estimator shows that only the Rigetti provider has enough qubits to execute the algorithm. However, the code cannot be executed on the Rigetti provider due to some limitations.
Discussions
The full-state simulator consumed too many memories for the local environment when N = 4 for the N-Queens solution. The sparse simulator can compute N = 6 without exhausting the hardware. The N-Queens² needed even more computing power, and the result of N-Queens² with diagonal restriction never be acquired running for days. A modified version without diagonal restriction is executed to verify the algorithm. The sparse simulator can compute N = 3 and N = 4 successfully.
The resources estimator showed an evaluation before submitting algorithms to real hardware. However, it cannot be verified this time while the algorithm has not been executed on a real quantum computer.
Conclusions
The time complexity of N-Queens is O(N³), and the space complexity is O(N²). Both of the complexity of N-Queens² increased by one, where the time complexity is O(N⁴), and the space complexity is O(N³).
The quantum algorithm showed theoretically faster than traditional computing, which reduces the time complexity from O(N!) to O(N³). However, more qubits are required to execute the algorithm to verify it. Also, a quantum counting method will be required when there is no solution number from the traditional computing method when N is greater than 27.
The N-Queens problem can be applied in load balancing, deadlock prevention, and satellite communication. For satellite communication, the queens can be replaced with satellites, and the configuration of the solution of the N-Queens puzzle will maximize the transmit area.
References
[1] Jha, R., Das, D., Dash, A., Jayaraman, S., Behera, B. K., & Panigrahi, P. K. (2018). A novel quantum N-Queens solver algorithm and its simulation and application to satellite communication using IBM quantum experience. arXiv preprint arXiv:1806.10221.
[2] Torggler, V., Aumann, P., Ritsch, H., & Lechner, W. (2019). A quantum n-queens solver. Quantum, 3, 149.
[3] Del Manzano, H. A., & Echevarıa, C. (2002). Quantum algorithm for n-queens problem. In Computing Research Conference, Mayagüez, Puerto Rico.
[5] QuantumKatas
