N-QueensパズルのQUBOをnealのシミュレーティド・アニーリングで解く

ポイント

• D-Waveのnealを使って，シミュレーティド・アニーリングでN-Queenパズルを解きます．

D-Wave neal

シミュレーティド・アニーリングは，最適化問題を解くためのすぐれた近似解法です．QUBOをシミュレーティド・アニーリングで解くツールであるnealがD-Waveから提供されています．そのnealを使ってN-Queensパズルを解きます．N-QueensパズルのQUBOへの変換は，N-QueensパズルのQUBOを高速生成し，Gurobiで解くの方法を用いています．この方法はバイナリ変数$X=(x_{i,j))$を使用してボードを表現し，次のルールでN-QueensパズルのQUBOを求めます．

• 全ての1次項$x_{i,j}$の係数を$-1$と設定することで，$x_{i,j}=1$となるバイナリ変数の個数を最大化します
• 座標$(i,j)$と$(i',j')$が同一行、同一列、または同一斜めライン上にある場合、2次項$x_{i,j}x_{i',j'}$の係数を$+1$と設定し，Queenが衝突することをペナルティとします

Pythonプログラム

辞書quboにQUBOの係数を設定します．タプル(i,j)は$x_{i,j}$に対応します．辞書quboのキーは，このようなタプルのタプルであり，キー((i,j),(i',j'))には$x_{i,j}x_{i',j'}$の係数が設定されます．この辞書quboを引数としてnealのサンプラー使用してシミュレーティド・アニーリングを実行します．シミュレーティド・アニーリングは指定した回数実行され，ベストの解が表示しています．

#!/usr/bin/env python3

import argparse
import neal

parser = argparse.ArgumentParser(
    description="Solve N-Queens puzzle through PyQUBO using D-Wave neal"
)
parser.add_argument(
    "-n", default=32, type=int, help="Value of N of N-QUEENS (default:32)"
)
parser.add_argument(
    "-t", default=10, type=int, help="Simulated annealing count (default:10)"
)
args = parser.parse_args()

qubo = {}
for x in range(args.n):
    for y in range(args.n):
        # Reward for placing a queen
        qubo[((x, y), (x, y))] = -1
        for i in range(x + 1, args.n):
            # Penalty for placing two queens in the same row
            qubo[((x, y), (i, y))] = 1
        for j in range(y + 1, args.n):
            # Penalty for placing two queens in the same column
            qubo[((x, y), (x, j))] = 1
        for d in range(1, args.n - x):
            if y - d >= 0:
                # Penalty for placing two queens on the same anti-diagonal
                qubo[((x, y), (x + d, y - d))] = 1
            if y + d < args.n:
                # Penalty for placing two queens on the same diagonal
                qubo[((x, y), (x + d, y + d))] = 1

# Initialize the simulated annealing sampler
sa_sampler = neal.SimulatedAnnealingSampler()
# Execute simulated annealing to find a solution
response = sa_sampler.sample_qubo(qubo, num_reads=args.t)
# Extract the best solution found during the simulated annealing
solution = response.first.sample
# Obtain the energy (objective value) of the best solution
energy = int(response.first.energy)

# Print the best solution
for i in range(args.n):
    for j in range(args.n):
        print(solution[(i, j)], end="")
    print()
print(f"optimal={-args.n} obtained={energy} trials={args.t}")

実行結果

32-Queensパズルの最適解が得られています．

00000010000000000000000000000000
00000000000000000000010000000000
00000000000000000100000000000000
10000000000000000000000000000000
00001000000000000000000000000000
00000000000000000000000000100000
00000001000000000000000000000000
00000000000000001000000000000000
00000000000001000000000000000000
00000000000100000000000000000000
00000000100000000000000000000000
00000000000000010000000000000000
00100000000000000000000000000000
00000000000000000000000000000100
01000000000000000000000000000000
00000000000000000000000100000000
00000000000000000000000000000010
00000000000000000000000000001000
00000000001000000000000000000000
00000000000000000000001000000000
00000000000000000000000000010000
00000000000000000000000000000001
00010000000000000000000000000000
00000000000000100000000000000000
00000000000000000001000000000000
00000000000000000000000010000000
00000000010000000000000000000000
00000000000010000000000000000000
00000100000000000000000000000000
00000000000000000000000001000000
00000000000000000010000000000000
00000000000000000000100000000000
optimal=-32 obtained=-32 trials=10