/* 

  Random Latin Squares (Rosetta code) in Picat.

  http://rosettacode.org/wiki/Random_Latin_squares
  """
  A Latin square of size n is an arrangement of n symbols in an n-by-n 
  square in such a way that each row and column has each symbol appearing exactly once.

  A randomised Latin square generates random configurations of the symbols for any given n.

  Example n=4 randomised Latin square

    0 2 3 1
    2 1 0 3
    3 0 1 2
    1 3 2 0

  Task

   1. Create a function/routine/procedure/method/... that given n generates a randomised 
      Latin square of size n.
   2. Use the function to generate and show here, two randomly generated squares of size 5.

  Note

  Strict Uniformity in the random generation is a hard problem and not a        
  requirement of the task. 
  """

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp,util.

main => go.

/*
  Using constraint modelling.

  The labeling used is ff,rand_val:
  * ff: selects a variable to label using the first fail strategy
  * rand_val: use a random (valid) value
    Normally a non-random value strategy is preferred such 
    as up, split, or updown, but the task requires random
    solutions.

 5  1  3  4  2 
 1  2  4  3  5 
 4  5  2  1  3 
 2  3  1  5  4 
 3  4  5  2  1 

 5  2  3  4  1 
 3  4  5  1  2 
 2  5  1  3  4 
 4  1  2  5  3 
 1  3  4  2  5 

9PRJhliyKjwkDVt60spfbz3aq8UmLMcSx1ed7nWIogENGr4uXHAvOQBTCYFZ52
CQEAorTdMWiDle2nXNg8YptFxBZwySGzURIPKubhHOJV49jmcqaLkfs06351v7
DEPvH2rfj7AVpyqx1ChMBQUGWsIoXzTedJFn3RL5YkZbK8Ni6cOmw90gauSlt4
wRSKyHhLiZeMztGcaETodVQprFjAvqN56Cmfxklg7UDYnOu1I49s8WPBJ032Xb
SwCqxBOrFsjpYKb360dPzaMDIHgTRefQZNuUk4vV8mytE5GhWXLAno7219Jilc
QcAaj62gZKf8TWPXY9Cv0yphwxDsF7SdkUoN4GtBEJnOMizI3blrume5RLqHV1
gFoxCYAT3U9nVGOEhu0m6WHdJ7wliQpks2atXLIfr4MeqbyzNB8PDj5RcSZv1K
KVnYz1Lh98RGPvI5kQBrjlbqmNeJouMZ7FxOS0H3XCgwcpDTsay4Ut6EiAWf2d
5gFhdwmEWxHR4ziMsl1jZkOXU6JnpfrLoQYebKuctvGIAV29yTq8N3CDBP70aS
RAq6edYJV40OuTctZGsWUXgPC5fiKb87manDIl2xyMB39kovpQr1hFENSzHjwL
1a4SA7XbOpr0IfKitRJke9sYGPxFQhuglj56Z8cLWNTyU2EwH3CnVDmvMBdqzo
zt3LuMpFGYNwcEZUmjABDHRk9JXhri5I4lV7fvySs8xdW0TCO62qogabe1KPnQ
I6Q4sfuxHw8EWX3jryDdoeSiplmBn9bVtvMTFz5KO72JLqk0G1cYAaUhZCgRPN
HSiWqnUKre56ZJfFxOEQuCNIM10p3ws4TY2yLojz9DcmvaXlVht7bG8dPRkAgB
flmnBts7CrL9eUzHMA6XguFVdj13N42TykhcaWoYZwvDpGKPJO5QE8RIxqiSb0
mvN5M4ReuItxGpnBOdLDTAlg3oc92rUwSb1QYsky0Ei8VhCJqZHKPXW6f7azFj
AJwd3WCOx6PmEIjVog7TsN0MQykLztR2Y8BGqXU9SFlciDvHfr1a4pZKnbueh5
LdpikbWDNCSqAOQoBTycR29rheaUjY4PHMG3vtw6fIu5Zxls1g0EFJXn78VmKz
pTzjrI52oMXWa0H4f6K1Owi7Lk38GUdNRgtmsFZJuQeBDnAEPCVcqv9SylbxYh
XnYwNpyzbgua1A4CI3F9MvTElhLj05J8QdsVmcOHqiPWfR627UZBrSotKGxDke
2kHX4ujthGZb89vwpDPzxqcOBIKEsVo6AeJLN3QnUTa70FmyrfdMSYg15iRWCl
uLGMfyksUS35CaRWqBHhtnIc7D4bAoVmXZ6j01ivJrQzPTFgKNExYd2Owelp98
MOh76z1k8tbYFcXeWvRxLomByU5dJjArnT4luI0PVG9HNgqpasDSCiwf3K2QEZ
qUaEgXd47vQz0isyuFt6nLDmofhGe81cPpSwlNxT3RkrjCHYA5K29IbJVWOBZM
iMeZtNKHwosU9npbDPGgC873SqWkOX6xzVyaTBAujdrE51IFYvRfQhlL024cmJ
YW7fDeN8vcMAqbUpQHVlGxazi4SKPBZn9OCr5wF013dTJ6gjEokymLtX2IshuR
l1vFmOP5Qy2TnBgYLKwCAGVHstbxIRe90Eqk8pfN6oU4ajrdMWShZcu7zJX3Di
hYkRQKGiXFBCbu97y58w3djsnLHVSxvD2cgM6ePOpf40zZJqlEWta1IoArUTNm
xbKrWQBl0AY3L2hzJt4naPECFus5TGqfV7NRgD8micwZ1SMekdIjpHv9X6oOyU
yNrzODlnauKFsCoQ7U92fSdJcvTMbIthgmHpGPBiA05Lk4eR8VX61ZxqjEYwW3
TeLGwhFSRqV725rNUxuJ8MCA0Xza6WIEpibYDd4jvKmPlf1oQkBgHy3c9ZtnOs
oXTOamVG6zUtg4Suv7Iih3WZEKR1fFl0rqjby9spwA8n2eckDLNJ5CHPdMBYQx
ZmOliR6CfkTy5DJ83Io72c104MvWBKPjhArStqEFaHX9bwpQeYgzLsdVUnNuxG
6Gub5keN1dnvSYLqPcxtW0JoD98HlZziMIU2EA34TsKgryBOF7mwRVhjpQCXfa
U0jeX8M1s5zuJZdICSvV7fYNtA9ycgEqaK3xnQDW4hboHBLrmRPOT2iFlwpkG6
J3fg1SnUcHCoyNTPzb5Y9OrKjQV786BsWDvqimaZdX0RIlwtu2MGexFAkhE4Lp
v8soEP7At1WeBwC9VJnpc6LUKaM4qd3Y5ufZhOTGI2NQgH0xbzilXRjrFDmySk
jZ5kpLJR4ByX3SuO2MUqibfn80NrtAFlEWw9chm7C1YvosPKdeGV6zDagxQITH
BsymbGQvgnhcdHDZAaluVF6LzwiI9JOtCXkWrE1R2YjqSU3Mxp7Tf0KeoN854P
35687jzIYDxZKdVrHnOsSTX1NClvUkWMBfpuJ2qwe9FamEbALGQo04yihcPtRg
nfJtv94jyL71HklsEerAQhPRXmq2ZNKow3z0MxCdbpVUYWia5SFDcuG8TgI6BO
Vhb2FcEmk9GIMgNa4LiylRZ6uOCPdvwp8rAJjSKszWoft35BTxeH7qnQDX1U0Y
ED2U8xtuIQO4rL51jkqFPYybVgAfHlCJNwKsRMpXBa76hzZS0iv3WecmGT9don
W4Zy9gaw50mPUqYfRVNEX7vjbitDMnx3cBLKQHeolzS1CuOG2I6dJArk8FhspT
G7xQSUgopacrN8w0bYM4kseW2dOXuCiAftEv95J1nPqKymh6ZljRBTLzHVDF3I
NiWTIsSBPE4HfjALFzb01mKQaG2cY39UvxO8eJnC5yphXotDRuwZl7kMqdrg6V
7Ht1G5cWnJaBhl6dK2zNpIkufroewELb3yDAVCMUxZOFQXR4SmT0gPqYsvj8i9
0pXPcT9Mdlks6xWAGwaRKEo4vVYO5DyuqnigHrh2QS1jeJ7NtF3IzBfZmULb8C
8o9ulV3Qeb6fjM7giWXHNt4TZRyqDaYvF0P12UGkK5sxOcSLBAhCInzprmwJdE
FjMVJoqYzRdgkPeKN1cGmi8v5pnux0XaIHThOfStDBCl7LWZ49sU2bQ3Ey6rAw
OrVsKA0qLTg2tQkJlXZI5UneH3ENmpay1h9zBb78P6fSRvdciDuFxM4wYoGCjW
kIc0TibaAfEKm1xG9Z2O4D58RSughsjBJPQozyVqLn6XdtU7vwYN3lpCWHeMrF
Pq0CnEZVS2DJxm8hTfQ3yKAw1zBRgOkXe9ciU6daFltMuIsWojpbGNYH45vL7r
axd9Yqw6DVJNRo0kc8eKI1hfgTpS72HFu4ZBPirAmLWs3MQXCnb5yEOlvjzGUt
rKBcVCxplNFSOs1v5hmeEZq2TbPtky0HLo7XWaYDGjRiwAn3g8zud6JUQ4M9If
tuUBLvDcmPIQw6aRnqYSFj2lAZr041gCisWEdVzbMx3p8N95hJoeKkTGOfy7HX
bzgIZav0J3lhXFB2doSLr4wxkc6QEPmRD58CpT9MNuHGs7YfUynijK1WtOAVeq
c9lpP0HXqOoLi3ESemjbJ5ByYWdZCT71GzRFAg6rhtI2xQa8nKUkvwV4usfNMD
sB830FI92ipdv7MmgrfZwJGSOnQCaHDKb6l41jXERehATYVUzPxWt5NyLkcoqu
dy1DU3fZTmqiorFlw4kaHBx5e2GYVLhWKSXIC7RQgbzu6P8njtJ9MOAsNp0Ecv
e2INRZoPBX1jQhmD8i35vrut6E7zWcnGOL0HwYglkqACFdfV9M4psUSxbaTKJy
4CDH2J83Ehvl7RyTSpWUqgz9PYF61mQOjGd5oZNecVLkBKxbw0fXirMuItnasA


CPU time 0.048 seconds. Backtracks: 0


*/

go =>
  _ = random2(), % random seed
  N = 5,
  foreach(_ in 1..2)
    latin_square(N, X),
    pretty_print(X)
  end,
  % A larger random instance
  latin_square(62,X),
  pretty_print(X),
  nl.
go => true.

/*

https://oeis.org/A002860 "Number of Latin squares of order n; or labeled quasigroups"

1 = 1
2 = 2
3 = 12
4 = 576
5 = 161280
6 = 812851200

CPU time 1134.36 seconds. Backtracks: 0

picat_run random_latin_square.pi go2  1134,38s user 0,01s system 99% cpu 18:54,40 total


*/
go2 =>
  foreach(N in 1..6)
    Count = count_all(latin_square(N,_)),
    println(N=Count)
  end,
  nl.

% Latin square
latin_square(N, X) =>
  X = new_array(N,N),
  X :: 1..N,
  foreach(I in 1..N)
    all_different([X[I,J] : J in 1..N]),
    all_different([X[J,I] : J in 1..N])
  end,
  % rand_val for randomness
  solve($[ff,rand_val],X).

pretty_print(X) =>
  N = X.len,
  Alpha = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ",
  foreach(I in 1..N)
    foreach(J in 1..N)
      if N > 20 then
        printf("%w",Alpha[X[I,J]])
      else
        printf("%2w ",X[I,J])      
      end
    end,
    nl
  end,
  nl.