|
Place 5 queens as follows:
0 0 1 1 0
1 0 0 1 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Attacked squares as follows:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
1 0 1 1 0
Leaving 3 squares not attacked.
Solutions up to and including board of order 17 are reproduced in a paper by Mario Velucchi to be found at http://anduin.eldar.org/~problemi/papers.html Xpress-Mosel Model
model 'nondomq'
! Description : Non-dominating queens problem
! Source : http://www.cli.di.unipi.it/~velucchi/queens.txt
! Date written : Xpress-MP 8/4/2000, Mosel 19/4/03
! Written by : M J Chlond
uses 'mmxprs'
parameters
size = 5
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 or occupied
numa:= sum(i in S,j in S) a(i,j)
! number of pieces placed equals size of board
nump:= sum(i in S,j in S) x(i,j) = size
! a(i,j) = 1 if square {i,j} attacked or occupied
forall(i in S,j in S)
atta(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) x(m,j) + sum(m in S | m <> j) x(i,m) +x(i,j)<= size*a(i,j)
! a(i,j) = 0 if square {i,j} not attacked or occupied
forall(i in S,j in S)
attb(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) x(m,j) + sum(m in S | m <> j) x(i,m) +x(i,j) >= a(i,j)
forall(i in S,j in S) do
x(i,j) is_binary
a(i,j) is_binary
end-do
minimise(numa)
write(getsol(numa))
writeln
forall(i in S) do
forall(j in S)
write(getsol(x(i,j)),' ')
writeln
end-do
end-model
|