part1.eprime

language ESSENCE' 1.0

$ Constraint solving model for M-queens problem clas taking in the board size as the parameter.
given BOARD_SIZE : int

letting RANGE be domain int(1..BOARD_SIZE)

$ Want to find an M*M board of {0,1}, where 1 denotes the cell containing a queen.
find result : matrix indexed by [RANGE, RANGE] of int(0,1)

$ Want to find the smallest possible solution.
minimising sum(flatten(result))

such that

$ Queens do not attack each other.
$ No more than one queen in each row.
forAll row : RANGE . sum(result[row,..]) <= 1,

$ And no more than one queen in each column.
forAll col : RANGE . sum(result[..,col]) <= 1,

$ Constraints for the number of queens in / diagonals.
forAll diagSum : int(2..BOARD_SIZE*2) .
	(sum row, col : RANGE . (row + col = diagSum) * result[row,col]) <=1,

$ Constraint for the number of queens in bottom \ diagonals.
forAll row : RANGE .
	(sum col : int(1..BOARD_SIZE-row+1) . result[row+col-1,col]) <= 1,

$ Constraints for the number of queens in the top \ diagonals.
forAll col : RANGE .
	(sum row : int(1..BOARD_SIZE-col+1) . result[row,row+col-1]) <= 1,


$ All fields must be under attack.
forAll row : RANGE .
	forAll col : RANGE .
		(sum(result[row,..]) + sum(result[..,col]) + (sum  row2,col2 : RANGE . (result[row2,col2] != 0) /\ (|row2 - row| = |col2 - col|))) >= 1