/*
Kraitchik's queen placement problem in Picat.
From Martin Chlond Integer Programming Puzzles:
http://www.chlond.demon.co.uk/puzzles/puzzles2.html, puzzle nr. 9.
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.
"""
How many queens are needed, and in what position, so that every unoccupied square of the chessboard is
under direct attack from some queen?
(Kraitchik)
"""
This model was inspired by the XPress Mosel model created by Martin Chlond.
http://www.chlond.demon.co.uk/puzzles/sol2s9.html
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import mip. % 0.95s
% import cp. % 11.9s
% import sat. % 31.7s
main => go.
go =>
Size = 8,
% decision variables
% x(i,j) = 1 if occupied, 0 otherwise
X = new_array(Size, Size),
X :: 0..1,
% a(i,j) = 1 if attacked, 0 otherwise
A = new_array(Size, Size),
A :: 0..1,
NumQ #= sum([X[I,J] : I in 1..Size, J in 1..Size]),
% a[i,j] = 0 if square (i,j) not attacked
foreach(I in 1..Size, J in 1..Size)
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,N] : N in 1..Size, N != J]) #>= A[I,J]
end,
% each square either attacked or occupied
foreach(I in 1..Size,J in 1..Size)
A[I,J]+X[I,J] #= 1
end,
solve($[ff,split, min(NumQ)], X ++ A),
println(numQ=NumQ),
print_matrix("X:", X),
print_matrix("A:", A),
nl.
print_matrix(Name,M) =>
println(Name),
foreach(Row in M)
println(Row.to_list())
end,
nl.