/*
The Riddle of the Pilgrims puzzle in Picat.
From Martin Chlond Integer Programming Puzzles:
http://www.chlond.demon.co.uk/puzzles/puzzles4.html, puzzle nr. 2.
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.
"""
The Riddle of the Pilgrims
The Abbott of Riddlewell announced that a messenger had that morning brought news that a number of pilgrims
were on the road and would require their hospitality.
"You will put them," he said, "in the square dormitory that has two floors with eight rooms on each floor.
There must be at least eleven persons sleeping on each side of the building, and twice as many on the upper
floor as the lower floor. Of course every room must be occupied, and you know my rule that not more than
three persons may occupy the same room."
I give a plan of the two floors, from which it will be seen that the sixteen rooms are approached by a well
staircase in the centre.
After the monks had solved this little problem of accomodation, the pilgrims arrived, when it was found
that they were three more in number than was at first stated. This necessitated a reconsideration of the
question, but the wily monks succeeded in getting over the new difficulty without breaking the Abbott's
rules.
The curious point of this puzzle is to discover the total number of pilgrims.
(Dudeney 1949)
"""
This model was inspired by the XPress Mosel model created by Martin Chlond.
http://www.chlond.demon.co.uk/puzzles/sol4s2.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 cp.
main => go.
go ?=>
N = 2, % solutions
F = 2, % floors
R = 3, % rows
C = 3, % columns
X = new_array(N,F,R,C),
foreach(I in 1..N, J in 1..F, K in 1..R, L in 1..C)
X[I,J,K,L] #>= 0
end,
% difference between solutions is 3 pilgrims
sum([X[1,J,K,M] : J in 1..F,K in 1..R,M in 1..C]) + 3 #=
sum([X[2,J,K,M] : J in 1..F,K in 1..R,M in 1..C]),
% twice as many pilgrims on second floor as first floor
foreach(I in 1..N)
sum([2*X[I,1,K,M] : K in 1..R,M in 1..C]) #= sum([X[I,2,K,M] : K in 1..R,M in 1..C])
end,
% eleven on first and third rows (i.e. front and back sides]
foreach(I in 1..N,K in 1..R, K != 2)
sum([X[I,J,K,M] : J in 1..F,M in 1..C]) #= 11
end,
% eleven on first and third columnss (i.e. left and right sides]
foreach(I in 1..N,M in 1..C, M != 2)
sum([X[I,J,K,M] : J in 1..F,K in 1..R]) #= 11
end,
% at least one pilgrim to a room
foreach (I in 1..N,J in 1..F,K in 1..R,M in 1..C, (K != 2 ; M != 2))
X[I,J,K,M] #>= 1
end,
% at most three pilgrims to a room
foreach (I in 1..N,J in 1..F,K in 1..R,M in 1..C, (K != 2 ; M != 2))
X[I,J,K,M] #<= 3
end,
% no pilgrims allocated to central celsl
foreach(I in 1..N,J in 1..F)
X[I,J,2,2] #= 0
end,
solve(X),
X2 = array_matrix_to_list_matrix(X),
% println(x2=X2),
First = [[J.to_list() : J in I.to_list()] : I in X2[1]],
println("First allocation"),
println("Lower floor:"),
print_matrix(First[1]),
println("Upper floor:"),
print_matrix(First[2]),
Second = [[J.to_list(): J in I.to_list()] : I in X2[2]],
println("Second allocation"),
println("Lower floor:"),
print_matrix(Second[1]),
println("Upper floor:"),
print_matrix(Second[2]),
nl,
fail,
nl.
go => true.
print_matrix(M) =>
foreach(Row in M) println(Row) end.