4
$\begingroup$

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal.

I managed to define my decision variable as x[n][n], a binary variable indicating if the location is used or not. But I couldn't find a way to write any linear constraints.

Any ideas how to proceed?

$\endgroup$
  • $\begingroup$ $x[1][1]+x[1][2]+x[1][3]+...+x[1][8]\leq1$,x[3][1]+x[4][2]+x[5][3]+...etc $\endgroup$ – Empy2 Nov 19 '15 at 22:49
0
$\begingroup$

I will use the following convention :

Any space is refered to by its coordinate (i,j). The bottom left space is (1,1), The bottom right space is (1,8), the top right is (8,1) and top left is (8,8).

Variables

$x_{ij} = 1$ if a queen is on the space (i,j), 0 otherwise

Problem

$$\max \sum\limits_{i,j} x_{ij}$$

(All the spaces in an increasing diagonal have the same value for $i-j$) $$ \sum\limits_{i,j|j-i = k} x_{ij} \leq 1 \mbox{ for } k\in \{-6, -5, ..., 5, 6\}$$

(all the spaces in a decreasing diagonal have the same value for $i+j$) $$ \sum\limits_{i,j|i+j = k} x_{ij} \leq 1 \mbox{ for } k\in \{2, 3, ..., 14\}$$

$$x_{ij}\in \{0,1\}$$

$\endgroup$
  • 2
    $\begingroup$ shouldn't you also handle the horizontal and vertical cases? $\endgroup$ – AlexanderJ93 Dec 19 '18 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.