/*
Dudeney's queen placement problem in Picat.
From Martin Chlond Integer Programming Puzzles:
http://www.chlond.demon.co.uk/puzzles/puzzles2.html, puzzle nr. 11
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.
"""
11. The Amazons.
Remove three of the queens to other squares so that there shall be eleven squares on the board that are not
attacked. The removal of the three queens need not be by "queen moves". You may take them up and place them
anywhere. There is only one solution.
(Dudeney)
"""
This model was inspired by the XPress Mosel model created by Martin Chlond.
http://www.chlond.demon.co.uk/puzzles/sol2s11.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.
import cp.
main => go.
go =>
Size = 8,
X = new_array(Size,Size), % 1 if square {I,J} occupied, 0 otherwise
X :: 0..1,
A = new_array(Size,Size), % 1 if square {I,J} attacked, 0 otherwise
A :: 0..1,
SumA :: 0..100,
SumA #= sum([A[I,J] : I in 1..Size, J in 1..Size]),
% all eight queens used
sum([X[I,J] : I in 1..Size, J in 1..Size]) #= 8,
% five of original queens untouched
sum([(X[8,J] + X[7,Size] + X[6,Size]) : J in 3..Size]) #= 5,
% a(i,j) = 1 if square (i,j) attacked
% (Yes, it's an IP approach.)
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, M != I]) +
sum([X[I,N] : N in 1..Size, N != J])
) #<= 99*A[I,J]
end,
Vars = A.to_list() ++ X.to_list(),
solve($[min(SumA),ff],Vars),
println(sumA=SumA),
println('X'),
foreach(Row in X) println(Row.to_list()) end,
println('A'),
foreach(Row in A) println(Row.to_list()) end,
nl.