Was ist das N Queen Problem?

Platziere N Königinnen auf dem N x N Brett. In diesem Moment, Kein Stück sollte sich in einer Position befinden, in der es von einem anderen Stück aufgenommen werden kann.

Dieses Problem kann auch mit Kombinationsoptimierung gelöst werden.

Formulierung

Zielfunktion	Keine
Variablen	$ x_j \ in \ {0, 1 \} ~ ~ \ forall j \ in jeder Zelle $	Gibt an, ob sie in diese Zelle eingefügt werden sollen td>
Einschränkungen	$ \ sum_ {j \ in jeder Zelle ~~~~~} {\ {x_j \| Vertikal ist i Spalten \}} = 1 ~ ~ \ forall i \ in \ {0, \ cdots, N-1 \} $	Eine pro Spalte weniger -1 \} $	Eine pro Zeile
	$ \ sum_ {j \ in jeder Zelle ~~~~~} {\ {x_j \| Vertikal + horizontal i \}} \ le 1 ~ ~ \ forall i \ in \ {0, \ cdots , 2 N-2 \} $	Eine oder weniger Diagonale
	$ \ sum_ {j \ in jeder Zelle ~~~~~} {\ {x_j \| Vertikal-horizontal i-N + 1 \}} \ le 1 ~ ~ \ forall i \ in \ { 0, \ cdots, 2 N-2 \} $	Eine oder weniger Diagonale

Versuchen Sie mit Python zu lösen

Formulieren und lösen wir es.

`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=['Vertikal', 'Seite', 'x'])
    for i in r:
        m += lpSum(a[a.Vertikal== i].x) == 1
        m += lpSum(a[a.Seite== i].x) == 1
    for i in range(2*N-1):
        m += lpSum(a[a.Vertikal+ a.Seite== i].x) <= 1
        m += lpSum(a[a.Vertikal- a.Seite== 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