[PYTHON] Solving the N Queen problem with combinatorial optimization

what is this

Tips for solving combinatorial optimization based on the N Queen problem.

Original article: Solving N Queen problem with combinatorial optimization

Conclusion

Changing the order of the constraints may change the calculation time. Let's verify with 4 patterns.

Solve the N Queen problem

First, check that you can actually solve it with 8x8.

from ortoolpy import pd, addbinvars, model_min, lpSum, addvals
n = 8
df = pd.DataFrame([(i, j) for i in range(n) for j in range(n)],
                  columns=['X', 'Y'])
addbinvars(df);
m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%time m.solve()
addvals(df)
cc = df.Val.astype(int).map('.O'.__getitem__).values.reshape(n, n)
print('\n'.join(''.join(c) for c in cc))

output

Wall time: 27 ms
..O.....
O.......
......O.
....O...
.......O
.O......
...O....
.....O..

Next, check the execution time with four formulas with a size of 100 x 100.

Pattern 1 (4.0 seconds)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

3.97 s ± 702 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Pattern 2 (4.7 seconds)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

4.7 s ± 423 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Pattern 3 (2.2 seconds)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
for i in range(n):
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

2.24 s ± 36.5 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

Pattern 4 (6.4 seconds)

m = model_min()
for i in range(n):
    m += lpSum(df[df.X == i].Var) == 1
for i in range(n):
    m += lpSum(df[df.Y == i].Var) == 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X + Y == {i + 1}').Var) <= 1
for i in range(2 * n - 3):
    m += lpSum(df.query(f'X - Y == {i - n + 2}').Var) <= 1
%timeit -r 3 -n 3 m.solve()

6.44 s ± 129 ms per loop (mean ± std. dev. of 3 runs, 3 loops each)

What should i do

The four patterns have the same formulation, only the order of the constraints is different. However, the calculation time has changed nearly three times. Moreover, the tendency is different depending on n.

In such a case, it may be better to prepare multiple patterns and execute them at the same time like this time, and stop all if even one answer is found.

Supplement

The calculation was done on a ThinkPad X280. The library installation is pip install or toolpy.

The 100 x 100 N Queens problem has 10,000 0-1 variables. The combination is $ 10 ^ {3010} $. It's a tremendous number of combinations, but it's amazing that you can solve it in just over 2 seconds with free software (PuLP).