/*
Non dominating queens in Picat.
From Martin Chlond Integer Programming Puzzles:
http://www.chlond.demon.co.uk/puzzles/puzzles4.html, puzzle nr. 6.
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt
"""
Place N queens on an order N chessboard to leave a maximum number of
unattacked vacant squares.
(Velucchi)
"""
This model was inspired by the XPress Mosel model created by Martin Chlond.
http://www.chlond.demon.co.uk/puzzles/sol4s6.html
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
% import util.
% import sat. % 1.64s
% import mip. % 0.092s
import cp. % 0.01s / 0 backtracks
main => go.
go =>
Size = 5,
% x(i,j) = 1 if square (i,j) occupied, 0 otherwise
X = new_array(Size,Size),
X :: 0..1,
% a(i,j) = 1 if square (i,j) attacked, 0 otherwise
A = new_array(Size,Size),
A :: 0..1,
NumA #= sum(A.vars()),
% number of pieces placed equals size of board
sum(X.vars()) #= Size,
% a[i,j) = 1 if square (i,j) attacked or occupied
% a[i,j) = 0 if square (i,j) not attacked or occupied
foreach(I in 1..Size, J in 1..Size)
T #=
(sum([X[M,M-I+J] : M in 1..Size, M != I, M-I+J >= 1, M-I+J <= Size]) +
sum([X[M,I+J-M] : M in 1..Size, M != I, I+J-M >= 1, I+J-M <= Size]) +
sum([X[M,J] : M in 1..Size]) +
sum([X[I,M] : M in 1..Size, M != J]) +
X[I,J]
),
T #<= Size*A[I,J],
T #>= A[I,J]
end,
% minimize number of squares attacked or occupied
Vars = A ++ X,
solve($[ff,split,min(NumA)], Vars),
println(numA=NumA),
print_matrix("X:",X),
print_matrix("A:",A),
nl.
print_matrix(Name,X) =>
println(Name),
foreach(Row in X) println(Row.to_list()) end,
nl.