CODEWITHSUNDEEP
pythonoptimizationmathematical-optimizationn-queenscvxpy
Binyamin Even
Binyamin Even

Reputation: 3382

How to solve the 8 queens problem with CVXPY?

I am really new to CVXPY. I am trying to solve the 8 queens problem, i.e., the problem of placing 8 chess queens on an 8 x 8 chessboard so that no two queens threaten each other. As I understand it, the constrainsts should be:

  1. sum of each row equals to 1.
  2. sum of each column equals to 1.
  3. sum of each diagonal equals to 1.
  4. all variables should be larger than 0.

Moreover, the objective function should be: maximize the 2-norm of the matrix (so that we get only 1's and 0's, because we can get a sum of 1 also with floats, but norm of 1 with zeros is larger than norm of floats between 0 to 1 that also sum up to 1 (for example: 0.8^2+0.2^2 < 1^2+0^2).

Is it possible to solve this kind of problem in CVXPY? I am pretty clueless on how to form the constraints and the objective function in CVXPY, but here are my initial initial attempts (I immediately got a "DCP Error" so I had no reason to continue, but still):

from cvxpy import *
x=Variable(shape=(9,9), name='board')
obj = Maximize(norm(x))
const = [sum(x, axis=1)==1]
prob=Problem(objective=obj,constraints=const)
prob.solve()

Any help will be appreciated!!!

Upvotes: 4

Views: 629

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16742

As I already said in the comments:

Maximize(norm(x)) causes the problem to be non-convex. CVXPY is for convex problems only.

8-queens problems are typically modeled with binary variables (link). You try to use a non-convex objective to bypass this. In general this does not work:

  • Convex solvers will not accept your problem
  • Local NLP solvers will end up in a local optimum
  • So a global NLP solver is required (e.g. Baron, Antigone, or Couenne). But that is not easier than using a linear MIP solver.

An essentially difficult, discrete problem can, in general, not be made "easy-to-solve" using tricks. Another such trick is to use the constraint x(1-x)=0. This suffers from the same problem: you need a global solver for a difficult non-convex problem. So it is better to stick with a linear formulation with binary variables. If there would be an easy way to make this convex and continuous, basically, MIP solver developers would be out of business. On the other hand, if you find such a transformation, I am sure a Nobel prize will be waiting for you.

Also, as mentioned in the comments, note that

3. sum of each diagonal equals to 1.

should read

3. sum of each diagonal <= 1.

Upvotes: 5

Related Questions