Random Latin squares: Difference between revisions
Content deleted Content added
No edit summary |
|||
Line 2,159: | Line 2,159: | ||
ZL6K5NFVMCYbXfA8Oe43g7dUcDa9JTEQGSWB1PR2IH |
ZL6K5NFVMCYbXfA8Oe43g7dUcDa9JTEQGSWB1PR2IH |
||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
Using constraint modelling. |
|||
The used labeling (search strategy) is: |
|||
* <code>ff</code>: select a variable to label using the first fail strategy |
|||
* <code>rand_val</code>: select a random (but valid) value. |
|||
Normally a non-random value strategy is preferred such as <code>up</code>, <code>split</code>, or <code>updown</code>, but the task requires random solutions. |
|||
<lang Picat>main => |
|||
_ = 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). |
|||
% 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.</lang> |
|||
{{out}} |
|||
<pre> 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.</pre> |
|||
===Number of solutions=== |
|||
The number of solutions for a Latin square of size N is the OEIS sequence [https://oeis.org/A002860 A002860: Number of Latin squares of order n; or labeled quasigroups]. Here we check N = 1..6 which took 18min54s. |
|||
<lang Picat>main => |
|||
foreach(N in 1..6) |
|||
Count = count_all(latin_square(N,_)), |
|||
println(N=Count) |
|||
end.</lang> |
|||
{{out}} |
|||
<pre>1 = 1 |
|||
2 = 2 |
|||
3 = 12 |
|||
4 = 576 |
|||
5 = 161280 |
|||
6 = 812851200 |
|||
CPU time 1134.36 seconds. |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |