Résolution du problème N Queen avec l'optimisation des combinaisons
Quel est le problème de N Queen?
Placez N reines sur le plateau N x N. En ce moment, Aucune pièce ne doit être dans une position où elle peut être prise par une autre pièce.
Ce problème peut également être résolu avec Optimisation de combinaison.
Formulation
| Fonction objectif | Aucun | |
| Variables | $ x_j \ in \ {0, 1 \} ~ ~ \ forall j \ in Each cell $ | S'il faut le placer dans cette cellule td> |
| Contraintes | $ \ sum_ {j \ in Each cell ~~~~~} {\ {x_j | La verticale correspond à i colonnes \}} = 1 ~ ~ \ forall i \ in \ {0, \ cdots, N-1 \} $ | Un par colonne |
| $ \ sum_ {j \ dans chaque cellule ~~~~~} {\ {x_j | side i line \}} = 1 ~ ~ \ forall i \ in \ {0, \ cdots, N -1 \} $ | Un par ligne | |
| $ \ sum_ {j \ in Each cell ~~~~~} {\ {x_j | Vertical + horizontal i \}} \ le 1 ~ ~ \ forall i \ in \ {0, \ cdots , 2 N-2 \} $ | Une diagonale ou moins | |
| $ \ sum_ {j \ in Each cell ~~~~~} {\ {x_j | Vertical-horizontal i-N + 1 \}} \ le 1 ~ ~ \ forall i \ in \ { 0, \ cdots, 2 N-2 \} $ | Une diagonale ou moins |
Essayez de résoudre avec Python
Formulons et résolvons-le.
python3
%matplotlib inline
import pandas as pd, matplotlib.pyplot as plt
from itertools import product
from ortoolpy import addvar
from pulp import *
def NQueen(N):
r = range(N)
m = LpProblem()
a = pd.DataFrame([(i, j, addvar(cat=LpBinary))
for i, j in product(r, r)], columns=['Verticale', 'côté', 'x'])
for i in r:
m += lpSum(a[a.Verticale== i].x) == 1
m += lpSum(a[a.côté== i].x) == 1
for i in range(2*N-1):
m += lpSum(a[a.Verticale+ a.côté== i].x) <= 1
m += lpSum(a[a.Verticale- a.côté== i-N+1].x) <= 1
%time m.solve()
return a.x.apply(value).reshape(N, -1)
for N in [8, 16, 32, 64, 128]:
plt.imshow(NQueen(N), cmap='gray', interpolation='none')
plt.show()
>>>
CPU times: user 4 ms, sys: 4 ms, total: 8 ms
Wall time: 27.5 ms
CPU times: user 16 ms, sys: 4 ms, total: 20 ms
Wall time: 84.4 ms
CPU times: user 48 ms, sys: 4 ms, total: 52 ms
Wall time: 272 ms
CPU times: user 236 ms, sys: 0 ns, total: 236 ms
Wall time: 1.88 s
CPU times: user 956 ms, sys: 20 ms, total: 976 ms
Wall time: 11.3 s
c'est tout
Recommended Posts