Try to solve the N Queens problem with SA of PyQUBO

I tried the N Queens problem to deepen my understanding of PyQUBO during the year-end and New Year holidays.

I think PyQUBO is a very convenient QUBO creation tool for using an annealing machine. "Solve the problem of setting only m to 1 out of n with an annealing machine using PyQUBO" https://qiita.com/morimorijap/items/196e7fc86ecff927bf40 I also use it in such cases, but I will try to solve the N queens problem again using PyQUBO.

What is the N queen problem? Wikipedia's 8 queens have 8x8 squares and 8 queens https://ja.wikipedia.org/wiki/Eight queen On the other hand, the mass says NxN problems.

Since the movement of the queen proceeds in eight directions diagonally up, down, left, and right as long as there is no obstruction, it becomes a problem to arrange the queen so that there is no queen in the column, row, or diagonally. In the form of a cost function to solve this on the annealing machine,

Hamiltonian of N-Queen problem, column column, row row, diagonal diagonal

H = \sum_{col}\left(\sum_{i \in col} x_i - 1\right)^2 + \sum_{row}\left(\sum_{i \in row} x_i - 1\right)^2 + \sum_{diag} \left((\sum_{i \in diag} x_i ) (\sum_{i \in diag} x_i - 1 )\right)

It will be.

The expression of the diagonal cost function is different, but it is an article of T-Wave of Tohoku University "Solving the N-Queen problem with a D-Wave machine" https://qard.is.tohoku.ac.jp/T- Wave /? P = 884 Will also be helpful.

In the case of 4x4,

Screen Shot 2020-01-03 at 17.09.22.png

Considering the expression of squares like, PyQUBO expresses an Array like Binary (q [0]) in QUBO format of 0,1.

from pyqubo import Array, Placeholder, solve_qubo, Sum
from pprint import pprint
import numpy as np

First, import what you need, such as PyQUBO. Suppose you want to make a 4x4 square.

# N-Number of Queen trout
N = 4

#Create 0 and 1 variables with pyQUBO for NxN squares
q = Array.create('q', (N*N), 'BINARY')

q_shape = np.reshape(q,(N,N))
print(q_shape)

Then

[[Binary(q[0]) Binary(q[1]) Binary(q[2]) Binary(q[3])] [Binary(q[4]) Binary(q[5]) Binary(q[6]) Binary(q[7])] [Binary(q[8]) Binary(q[9]) Binary(q[10]) Binary(q[11])] [Binary(q[12]) Binary(q[13]) Binary(q[14]) Binary(q[15])]]

In this way, you can create PyQUBO Binary in 4x4 array format. The line part is as follows in the formula, so

\sum_{row}\left(\sum_{i \in row} x_i - 1\right)^2

Expressing this in PyQUBO, you can slice each row, add them as they are, square them, and finally add them up.

#line
row_const = 0.0
for row in range(N):
    row_const += (sum(i for i in q_shape[row, :]) -1)**2

Also, the columns can be represented as follows.

\sum_{col}\left(\sum_{i \in col} x_i - 1\right)^2
#Column
col_const = 0.0
for col in range(N):
    col_const += (sum(i for i in q_shape[:, col]) -1)**2

It will be.

And the diagonal expression of the problem,

\sum_{diag} \left((\sum_{i \in diag} x_i ) (\sum_{i \in diag} x_i - 1 )\right)

Will be represented by PyQUBO, but it can be divided into two parts, "" and "/", by using Numpy conversion. (If you know a better way, please let me know)

#Diagonal
#\Who
diag_const = 0.0
xi = 0.0
xi_1 = 0.0
for k in range(-N+1,N):
    xi += (sum(i for i in np.diag(q_shape,k=k)))
    xi_1 += (sum(i for i in np.diag(q_shape,k=k))) -1 
    diag_const += xi * xi_1

When

#Diagonal
# /Replace for those who,\ do.
diag_const_f = 0.0
xi = 0.0
xi_1 = 0.0
for k in range(-N+1,N):
    xi += (sum(i for i in np.diag(np.fliplr(q_shape),k=k)))
    xi_1 += (sum(i for i in np.diag(np.fliplr(q_shape),k=k))) -1 
    diag_const_f += xi * xi_1

It will be.

By adding all of these, we can express the Hamiltonian of the energy function. Also, use PyQUBO's Placeholder to adjust the parameters and add alpha, beta, and gamma.

#energy(Hamiltonian)Build

alpha = Placeholder("alpha")
beta = Placeholder("beta")
gamma = Placeholder("gamma")

#Parameters
feed_dict = {'alpha': 1.0, 'beta': 1.0, 'gamma': 1.0}

H = alpha * col_const + beta * row_const  + gamma *(diag_const + diag_const_f)

Next, convert to QUBO.

#Compiling QUBO
model = H.compile()
qubo, offset = model.to_qubo(feed_dict=feed_dict)

pprint(qubo)

Just by itself, it will make QUBO.

{('q[0]', 'q[0]'): -11.0, ('q[0]', 'q[10]'): 6.0, ('q[0]', 'q[11]'): 4.0, ('q[0]', 'q[12]'): 2.0, ('q[0]', 'q[13]'): 6.0, ('q[0]', 'q[14]'): 6.0, ('q[0]', 'q[15]'): 6.0, ('q[0]', 'q[1]'): 6.0, ('q[0]', 'q[2]'): 4.0,

・ ・ ・ Because it is long, it is omitted on the way ...

('q[8]', 'q[8]'): -19.0, ('q[8]', 'q[9]'): 14.0, ('q[9]', 'q[9]'): -21.0}

is. This can be calculated as it is with SA of PyQUBO.

#Calculated by SA of PyQUBO
solution = solve_qubo(qubo)

#Decoding calculation results with SA of pyQUBO
decoded_solution, broken, energy = model.decode_solution(solution, vartype="BINARY", 
feed_dict=feed_dict)

pprint(solution)

Result is,

{'q[0]': 0, 'q[10]': 0, 'q[11]': 0, 'q[12]': 0, 'q[13]': 0, 'q[14]': 1, 'q[15]': 0, 'q[1]': 1, 'q[2]': 0, 'q[3]': 0, 'q[4]': 0, 'q[5]': 0, 'q[6]': 0, 'q[7]': 1, 'q[8]': 1, 'q[9]': 0}

Screen Shot 2020-01-03 at 21.16.39.png

It becomes ~~, and the conditions are met for the time being, but since Queen may be included in 13, I feel that it is necessary to adjust the parameters. ~~ Postscript: It seems that the optimum solution was not found because the diagonal corner was missing. This time, the solution came out properly.

Extra: Experiment with the chess board attached to Lego's Harry Potter Advent Calendar 2019 (laughs) IMG_6770.JPG

For PyQUBO, refer to the official document. https://pyqubo.readthedocs.io/

that's all.

Postscript: 2020/1/3 9:20pm I edited it because the diagonal condition was wrong.

Recommended Posts

Try to solve the N Queens problem with SA of PyQUBO
Try to solve the fizzbuzz problem with Keras
Try to solve the internship assignment problem with Python
Try to solve the Python class inheritance problem
Try to solve the man-machine chart with Python
Solving the N Queens problem with combinatorial optimization
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
Try to solve a set problem of high school math with Python
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
Try to solve the programming challenge book with python3
Try to solve the traveling salesman problem with a genetic algorithm (execution result)
Try to solve the problems / problems of "Matrix Programmer" (Chapter 1)
Try to get the contents of Word with Golang
I tried to solve the problem with Python Vol.1
The 15th offline real-time I tried to solve the problem of how to write with python
Try to solve the problems / problems of "Matrix Programmer" (Chapter 0 Functions)
Try to automate the operation of network devices with Python
Try to extract the features of the sensor data with CNN
How to write offline real time I tried to solve the problem of F02 with Python
I wanted to solve the ABC164 A ~ D problem with Python
Solve the initial value problem of ordinary differential equations with JModelica
Try to solve the shortest path with Python + NetworkX + social data
Try to solve the function minimization problem using particle swarm optimization
How to solve the bin packing problem
Solve the traveling salesman problem with OR-Tools
Use Raspberry Pi to solve the problem of insufficient mobile Wi-Fi connection
The 16th offline real-time how to write reference problem to solve with Python
Try to image the elevation data of the Geographical Survey Institute with Python
Try using n to downgrade the version of Node.js you have installed
Try to react only the carbon at the end of the chain with SMARTS
The 19th offline real-time how to write reference problem to solve with Python
Try to separate the background and moving object of the video with OpenCV
I want to solve the problem of memory leak when outputting a large number of images with Matplotlib
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
How to try the friends-of-friends algorithm with pyfof
Solving the N Queen problem with combinatorial optimization
[At Coder] Solve the problem of binary search
Try to simulate the movement of the solar system
[Verification] Try to align the point cloud with the optimization function of pytorch Part 1
[Python] Try to read the cool answer to the FizzBuzz problem
Add information to the bottom of the figure with Matplotlib
Try to create a battle record table with matplotlib from the data of "Schedule-kun"
Try to visualize the room with Raspberry Pi, part 1
The first algorithm to learn with Python: FizzBuzz problem
I tried to solve the soma cube with python
I tried to solve the virtual machine placement optimization problem (simple version) with blueqat
Try to estimate the number of likes on Twitter
[Neo4J] ④ Try to handle the graph structure with Cypher
It's Christmas, so I'll try to draw the genealogy of Jesus Christ with Cabocha
A memo on how to overcome the difficult problem of capturing FX with AI
Try to specify the axis with PyTorch's Softmax function
Try to import to the database by manipulating ShapeFile of national land numerical information with Python
Try to visualize the nutrients of corn flakes that M-1 champion Milkboy said with Python
A person who wants to clear the D problem with ABC of AtCoder tried to scratch
I tried to find the entropy of the image with python
Try scraping the data of COVID-19 in Tokyo with Python
Try to get the function list of Python> os package
Try to play with the uprobe that supports Systemtap directly
I wanted to solve the Panasonic Programming Contest 2020 with Python
I tried to find the average of the sequence with TensorFlow
Finding a solution to the N-Queen problem with a genetic algorithm (2)