|
Occupied squares have value 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 Squares not under attack have value 0: 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Xpress-Mosel Model
model 'dqueens'
! Description : Dudeney's queen placement problem
! Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
! Date written : Xpress-MP 24/10/99, Mosel 17/4/03
! Written by : M J Chlond
uses 'mmxprs'
parameters
size = 8
end-parameters
declarations
S = 1..size
x: array(S,S) of mpvar ! x(i,j) = 1 if square {I,J} occupied, 0 otherwise
a: array(S,S) of mpvar ! a(i,j) = 1 if square {I,J} attacked, 0 otherwise
end-declarations
! minimise number of squares attacked
attack:= sum(i in S,j in S) a(i,j)
! all eight queens used
numq:= sum(i in S,j in S) x(i,j) = 8
! five of original queens untouched
sl:= sum(j in 3..size) x(8,j) + x(7,size) + x(6,size) = 5
! a(i,j) = 1 if square {i,j} attacked
forall(i in S,j in S)
att(i,j):= sum(m in S | m <> i and m-i+j >= 1 and m-i+j <= size) x(m,m-i+j)+
sum(m in S | m <> i and i+j-m >= 1 and i+j-m <= size) x(m,i+j-m)+
sum(m in S | m <> i) x(m,j) + sum(n in S | n <> j) x(i,n) <= 99*a(i,j)
forall(i in S, j in S) do
x(i,j) is_binary
a(i,j) is_binary
end-do
minimise(attack)
forall(i in S) do
forall(j in S)
write(getsol(x(i,j)),' ')
writeln
end-do
end-model
|