/*
Latin square card puzzle in Picat.
Problem from Mario Livio's book about group theory
"The Equation that couldn't be solved",
page 22
"""
"... Incidentally, you may get a kick out of solving this
eighteenth century card puzzle: Arrange all the jacks,
queens, kings, and aces from a deck of cards in a square so that
no suit or value would appear twice in any row, column, or the
two main diagonals.
"""
Also see
- http://en.wikipedia.org/wiki/Graeco-Latin_square
- http://en.wikipedia.org/wiki/Thirty-six_officers_problem
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
% import mip.
main => go.
go =>
N = 4,
All = findall(X,card_puzzle(N, X)),
foreach(X in All)
print_matrix(N,X)
end,
println(sols=All.length),
nl.
go2 =>
foreach(N in 2..20)
println(n=N),
( card_puzzle(N,X), print_matrix(N,X) ; true),
nl
end,
nl.
print_matrix(N,X) =>
% println(x=X),
M = (N*(N+1)) div 2,
foreach(I in 1..N)
foreach(J in 1..N)
printf("%2d/%2d ", X[I,J] div M, X[I,J] mod M)
end,
nl
end,
nl.
% for n=4 (and m = 10)
% cards =
% values: i mod 10
% 0, 1, 2, 3, % suite 1: 0 div 10
% 10,11,12,13, % suite 2: 1 div 10
% 20,21,22,23, % suite 3: 2 div 10
% 30,31,32,33 % suite 4: 3 div 10
%
card_puzzle(N, X) =>
M = (N*(N+1)) div 2,
Cards = [I + M*J : I in 0..N-1, J in 0..N-1],
% println(cards=Cards),
% decision variables
X = new_array(N,N),
X :: Cards,
% all values must be different
all_different(X.vars()),
% all_different($[X[I,J] : I in 1..N, J in 1..N]),
% diagonals1
all_different($[X[I,I] div M : I in 1..N ]),
all_different($[X[I,I] mod M : I in 1..N ]),
% diagonal2
all_different($[X[I,N-I+1] div M : I in 1..N ]),
all_different($[X[I,N-I+1] mod M : I in 1..N ]),
% rows, columns,
foreach(I in 1..N)
all_different($[X[I,J] div M : J in 1..N ]),
all_different($[X[J,I] div M : J in 1..N ]),
all_different($[X[I,J] mod M : J in 1..N ]),
all_different($[X[J,I] mod M : J in 1..N ])
end,
% symmetry breaking
X[1,1] #= 0,
solve([ff,updown], X).