WORHP Kata of July 2023: Queens puzzle ⌚ 2023-07-01

A kata (in the context of programming) is a small training unit to practise coding. In this series of WORHP Katas we present standard problems of optimization which you can use to get familiar with optimization (and our optimization software WORHP).

Kata: The queens puzzle is the problem of placing $n$ queens on an $n\times n$ chessboard.
As an NLP, this could be formulated as follows:

1. The optimization variables are the entries of a matrix $M\in\mathbb{R}^{n\times n}$, where for $i,j\in\{1,\dots,n\}$
   1. $M_{ij}=1$ means, there is a queen on position $(i,j)$ on the checkboard, and
   2. $M_{ij}=0$ means, there is no queen on that position.
2. The first set of constraints has to make sure, that in each column and in each row
   1. the sum of the entries is 1,
   2. (at least) one of the entries is 1.
3. The second set of constraints has to make sure, that in each diagonal and subdiagonal
   1. the sum of the entries is not larger than 1.
   Of course we need a differentiable formulation of the constraints.
   

Formulate the queens puzzle as an NLP and solve it for $n=4$, (and with a non-trivial initial guess) for $n=6$, and $n=8$.

A solution will be provided with the next WORHP Kata.

Solution of last WORHP Kata: The common approximations of the partial derivatives simplify on the given grid with spacing 1: $\begin{array}{rcl} f_{xx}(x,y) &\approx& f(x+1, y)- 2f(x, y) + f(x-1, y) \\ f_{yy}(x,y) &\approx& f(x, y+1)- 2f(x, y) + f(x, y-1) \\ f_{xy}(x,y) &\approx& \frac{ \frac{f(x+1, y+1) - f(x-1, y+1)}{2} - \frac{f(x+1, y-1) - f(x-1, y-1)}{2} }{2} \\ \end{array}$ The discretized optimization problem is now with the data points $(x_i,y_i,z_i)$: $\min\limits_{f(x,y)} \sum\limits_{i=1}^{6} (z_i - f(x_i, y_i))^2 + \lambda \sum\limits_{x=0}^{20} \sum\limits_{y=0}^{20} f_{xx}^2(x,y) + 2f_{xy}^2(x,y) + f_{yy}^2(x,y)$ For $\lambda = 0.01$ we found this solution:

• Blog index