# Linear constraints to placing N queens on an N x N chessboard?

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?

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

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\}$$

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