OKlibrary  0.2.1.6
BasicNotions.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 30.12.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2011 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/BasicNotions.mac")$
00027 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/Generators/Sudoku.mac")$
00028 
00029 
00030 /* *****************************
00031    * Notions of "latin squares *
00032    *****************************
00033 */
00034 
00035 /* A "combinatorial latin square over H" is a square-sized combinatorial
00036    matrix A such that the size of the row index-set as well as the size of the
00037    column index-set is equal to the size of the set H, and such that every row
00038    and every column is a permutation of H:
00039 */
00040 comlso_p(A,H) := sqscom_p(A,H) and block([n : length(H)],
00041   is(n = length(A[1])) and
00042     every_s(lambda([R],length(unique(R))=n),com2ll_r(A)) and
00043     every_s(lambda([C],length(unique(C))=n),com2ll_c(A)))$
00044 
00045 /* Accordingly, isomorphism of latin squares would be isomorphisms of
00046    combinatorial matrices, and thus treat columns and rows independently.
00047    However this inherited standard notion of isomorphism is not general
00048    enough, since also value permutations must be considered; see below for the
00049    various notions considered.
00050    "comlso" stands for "combinatorial latin square over" (the value set).
00051    "Standardised" means, as usual, that H={1,...,n} for n >= 0.
00052 */
00053 
00054 /* A "combinatorial latin square" is a quasigroup: */
00055 comls_p(A) := qgrp_p(A)$
00056 /*
00057   So here row index set, column index set and value set coincide. We have
00058     comls_p(A) = scom_p(A) and block([B : scom2com(A)], comlso_p(B,B[1])).
00059 
00060   The notion of "isomorphic quasigroups" is not of (high) relevance for latin
00061   squares, but the three more general notions used for quasigroups are
00062   to be used: Isotopism, parastrophism and paratopism (their combination) .
00063 */
00064 
00065 
00066 /* A "latin square" is a square Maxima matrix A such that m2scom(A) is a
00067    combinatorial latin square:
00068 */
00069 ls_p(A) := matrixp(A) and block([s : matrix_size(A)],
00070   is(s[1] = s[2]) and comls_p(m2scom(A)))$
00071 /* Standardised combinatorial latin squares fully correspond to
00072    latin squares (as Maxima matrices). */
00073 
00074 /* A "half-reduced latin square" is a latin square which has i as the
00075    first entry in row i (for all i): */
00076 hrls_p(A) := ls_p(A) and block([s : matrix_size(A)],
00077   is(s[1] = 0) or is(transpose(A)[1] = create_list(i,i,1,s[1])))$
00078 /* A "reduced latin square" is a half-reduced latin square which has i as the
00079    first entry in column i (for all i): */
00080 rls_p(A) := hrls_p(A) and block([s : matrix_size(A)],
00081   is(s[1] = 0) or is(A[1] = create_list(i,i,1,s[1])))$
00082 
00083 /* Reduced non-empty latin squares 1-1 correspond to standardised unital
00084    quasigroups (with element 1 as the unit).
00085    While half-reduced non-empty latin squares 1-1 correspond to standardised
00086    left-unital quasigroups (with element 1 as the unit).
00087 */
00088 
00089 /*
00090    General remark:
00091    In the tests below the latin-square property is not tested, but only
00092    the special ("additional") properties, with the exception of the
00093    combined tests.
00094 */
00095 
00096 
00097 /* *********************
00098    * Various diagonals *
00099    *********************
00100 */
00101 
00102 /* For a natural number n >= 0: */
00103 main_diagonal(n) := create_list([i,i],i,1,n)$
00104 side_diagonal(n) := create_list([i,n-i+1],i,1,n)$
00105 
00106 /* For a natural number n >= 1 and a "difference" 0 <= d < n: */
00107 main_pandiagonal(n,d) := 1+mod(create_list([i+d,i],i,0,n-1),n)$
00108 /* For a natural number n >= 1 and a "sum" 0 <= s < n: */
00109 side_pandiagonal(n,s) := 1+mod(create_list([i,s-i],i,0,n-1),n)$
00110 
00111 /* Whether a square Maxima-matrix is diagonal (all elements on the main
00112    diagonal and on the side diagonal are different):
00113 */
00114 dls_p(A) := block([n:matrix_size(A)[1]],
00115   alldifferent_m_p(A, main_diagonal(n)) and
00116   alldifferent_m_p(A, side_diagonal(n)))$
00117 
00118 /* Whether a non-empty square Maxima-matrix is strictly pandiagonal: */
00119 spls_p(A) := block([n:matrix_size(A)[1]],
00120   every_s(lambda([L], alldifferent_m_p(A,L)),
00121           create_list(main_pandiagonal(n,d), d,0,n-1)) and
00122   every_s(lambda([L], alldifferent_m_p(A,L)),
00123           create_list(side_pandiagonal(n,d), d,0,n-1)))$
00124 
00125 /* Whether a non-empty square Maxima-matrix is pandiagonal: */
00126 pls_p(A) := block([n:matrix_size(A)[1], s],
00127   s : n*(n+1)/2,
00128   every_s(lambda([L], is(sum_m(A,L)=s)),
00129           create_list(main_pandiagonal(n,d), d,0,n-1)) and
00130   every_s(lambda([L], is(sum_m(A,L)=s)),
00131           create_list(side_pandiagonal(n,d), d,0,n-1)))$
00132 
00133 
00134 /* *****************
00135    * Orthogonality *
00136    *****************
00137 */
00138 
00139 /* Whether two combinatorial latin squares are "orthogonal", i.e., whether the
00140    super-imposed values are always different (as pairs): */
00141 /* Prerequisite: A, B are combinatorial latin squares. */
00142 ocomls_p(A,B) := is(A[1] = B[1]) and block([L : listify(A[1])],
00143   is(length(unique(create_list([A[2](i,j), B[2](i,j)], i,L, j,L))) = length(L)^2))$
00144 /* The same for latin squares (square Maxima matrices of order n with entries
00145    in {1,...,n}):
00146 */
00147 ols_p(A,B) := ocomls_p(m2scom(A),m2scom(B))$
00148 
00149 /* Whether a list of combinatorial latin squares is "mutually" (i.e.,
00150    pairwise) orthogonal:
00151 */
00152 mocomls_p(L) := listp(L) and block([n : length(L), is_mols : true],
00153   for i : 1 thru n unless not is_mols do block([A : L[i]],
00154     for j : i+1 thru n unless not is_mols do
00155       is_mols : ocomls_p(A,L[j])),
00156   is_mols)$
00157 /* The same for latin squares: */
00158 mols_p(L) := mocomls_p(map(m2scom,L))$
00159 
00160 /* Whether a combinatorial latin square is "self-orthogonal", i.e., orthogonal
00161    to its transposed:
00162 */
00163 socomls_p(A) := ocomls_p(A,trans_scom(A))$
00164 /* The same for latin squares: */
00165 sols_p(A) := socomls_p(m2scom(A))$
00166 
00167 
00168 /* ************
00169    * Symmetry *
00170    ************
00171 */
00172 
00173 /* Whether a square Maxima-matrix has "strong symmetry": */
00174 ssls_p(A) := block([n : matrix_size(A)[1]],
00175   every_s(lambda([p], is(A[p[1],p[2]]+A[n+1-p[1],n+1-p[2]]=n+1)),
00176           all_tuples(setn(n), 2)))$
00177 
00178 
00179 /* ***************************
00180    * Sudoku-like constraints *
00181    ***************************
00182 */
00183 
00184 /* Whether a square Maxima-matrix fulfils the Sudoku box-constraints (i.e.,
00185    in all boxes of dimension p, where p^2 = n for the dimension n, all
00186    entries are different):
00187 */
00188 sdkbox_p(A) := block([n : matrix_size(A)[1], p],
00189  p : ceiling(sqrt(n)),
00190  if p^2 # n then return(false),
00191  every_s(lambda([P], alldifferent_m_p(A, sdk_positions_box(P[1],P[2],p))),
00192          all_tuples(setn(p), 2)))$
00193 
00194 
00195 /* ****************
00196    * Combinations *
00197    ****************
00198 */
00199 
00200 /* Whether Maxima-matrix A is a (generalised) Sudoku (arbitrary box-dimension
00201    p >= 0):
00202 */
00203 sdk_p(A) := ls_p(A) and sdkbox_p(A)$
00204 
00205 /* Whether Maxima-matrix A is a self-orthogonal diagonal latin square: */
00206 sodls_p(A) := ls_p(A) and dls_p(A) and sols_p(A)$
00207 
00208 sssodls_p(A) := ssls_p(A) and sodls_p(A)$
00209 
00210 psssodls_p(A) := pls_p(A) and sssodls_p(A)$
00211 
00212 
00213 /* ************
00214    * Examples *
00215    ************
00216 */
00217 
00218 /* The (cyclic, unique) reduced latin square of order 3: */
00219 cyc3_rls : matrix(
00220  [1,2,3],
00221  [2,3,1],
00222  [3,1,2]
00223 )$
00224 /* The unique (half-reduced) latin square orthogonal to cyc3_rls: */
00225 cyc3_o_hrls : matrix(
00226  [1,3,2],
00227  [2,1,3],
00228  [3,2,1]
00229 )$
00230 /* The quasigroup corresponding to cyc3_o_hrls is also non-unital (and
00231    thus non-associative).
00232 */
00233 
00234 /* A smallest reduced latin square (corresponding to a unital
00235    quasigroup) which is not a group: */
00236 nassoc_rls : matrix(
00237  [1,2,3,4,5],
00238  [2,1,5,3,4],
00239  [3,4,1,5,2],
00240  [4,5,2,1,3],
00241  [5,3,4,2,1]
00242 )$
00243 
00244 /* The (reduced) latin square of order 10 from
00245    [Knuth, Volume 4, Fascicle 0]: */
00246 dk10_rls : matrix(
00247  [1,2,3,4,5,6,7,8,9,10],
00248  [2,9,4,3,6,5,8,7,10,1],
00249  [3,10,6,7,4,1,9,5,8,2],
00250  [4,8,1,10,9,7,2,6,3,5],
00251  [5,7,8,6,3,10,1,9,2,4],
00252  [6,1,10,5,8,9,4,2,7,3],
00253  [7,6,5,8,2,4,3,10,1,9],
00254  [8,5,2,9,1,3,10,4,6,7],
00255  [9,4,7,1,10,2,6,3,5,8],
00256  [10,3,9,2,7,8,5,1,4,6]
00257 )$
00258 /* The unique (half-reduced) latin square orthogonal to dk10_rls: */
00259 dk10_o_hrls : matrix(
00260  [1,3,9,6,10,5,8,4,7,2],
00261  [2,8,5,10,4,7,6,1,3,9],
00262  [3,6,7,5,9,8,1,2,10,4],
00263  [4,7,10,1,5,6,9,3,2,8],
00264  [5,9,2,8,6,4,7,10,1,3],
00265  [6,2,8,9,1,3,10,5,4,7],
00266  [7,10,1,3,8,2,4,9,5,6],
00267  [8,4,6,2,3,1,5,7,9,10],
00268  [9,1,3,4,7,10,2,8,6,5],
00269  [10,5,4,7,2,9,3,6,8,1]
00270 )$
00271 
00272 /* From [Constructions for pandiagonal strongly symmetric self-orthogonal
00273    diagonal Latin squares, Chen, Li, Zhang].
00274    Standardised (i.e., values in {1,...,4}).
00275 */
00276 sssodls_4_ls : 1+matrix(
00277  [0,1,3,2],
00278  [3,2,0,1],
00279  [2,3,1,0],
00280  [1,0,2,3]
00281 )$
00282 
00283 /* From [Constructions for pandiagonal strongly symmetric self-orthogonal
00284    diagonal Latin squares, Chen, Li, Zhang].
00285    Standardised (i.e., values in {1,...,8}).
00286 */
00287 psssodls_8_ls : 1+matrix(
00288  [0,1,3,2,4,5,7,6],
00289  [5,4,6,7,1,0,2,3],
00290  [6,7,5,4,2,3,1,0],
00291  [3,2,0,1,7,6,4,5],
00292  [2,3,1,0,6,7,5,4],
00293  [7,6,4,5,3,2,0,1],
00294  [4,5,7,6,0,1,3,2],
00295  [1,0,2,3,5,4,6,7]
00296 )$
00297 
00298 /* Discovered by MH via Minion.
00299    Standardised (i.e., values in {1,...,9}).
00300 */
00301 
00302 psssodls_9_ls : 1+matrix(
00303  [0,1,2,6,7,8,3,4,5],
00304  [8,6,7,5,3,4,2,0,1],
00305  [4,5,3,1,2,0,7,8,6],
00306  [1,2,0,7,8,6,4,5,3],
00307  [6,7,8,3,4,5,0,1,2],
00308  [5,3,4,2,0,1,8,6,7],
00309  [2,0,1,8,6,7,5,3,4],
00310  [7,8,6,4,5,3,1,2,0],
00311  [3,4,5,0,1,2,6,7,8]
00312 )$
00313 
00314 /* From [Constructions for pandiagonal strongly symmetric self-orthogonal
00315    diagonal Latin squares, Chen, Li, Zhang].
00316    Standardised (i.e., values in {1,...,20}).
00317 */
00318 psssodls_20_ls : 1+matrix(
00319  [13,18,10,14,16,4,0,7,11,2,9,3,5,6,1,8,15,12,19,17],
00320  [14,16,18,10,13,11,2,0,7,4,6,1,3,5,9,19,17,15,12,8],
00321  [16,10,14,13,18,2,7,11,4,0,1,5,6,9,3,17,12,19,8,15],
00322  [10,13,16,18,14,7,4,2,0,11,5,9,1,3,6,12,8,17,15,19],
00323  [18,14,13,16,10,0,11,4,2,7,3,6,9,1,5,15,19,8,17,12],
00324 
00325  [9,3,6,5,1,12,17,15,8,19,14,18,10,13,16,7,2,11,0,4],
00326  [5,1,3,6,9,8,19,17,15,12,13,16,18,10,14,0,4,2,11,7],
00327  [1,6,5,9,3,19,15,8,12,17,16,10,13,14,18,4,11,0,7,2],
00328  [6,9,1,3,5,15,12,19,17,8,10,14,16,18,13,11,7,4,2,0],
00329  [3,5,9,1,6,17,8,12,19,15,18,13,14,16,10,2,0,7,4,11],
00330 
00331  [8,15,12,19,17,9,3,5,6,1,4,0,7,11,2,13,18,10,14,16],
00332  [19,17,15,12,8,6,1,3,5,9,11,2,0,7,4,14,16,18,10,13],
00333  [17,12,19,8,15,1,5,6,9,3,2,7,11,4,0,16,10,14,13,18],
00334  [12,8,17,15,19,5,9,1,3,6,7,4,2,0,11,10,13,16,18,14],
00335  [15,19,8,17,12,3,6,9,1,5,0,11,4,2,7,18,14,13,16,10],
00336 
00337  [7,2,11,0,4,14,18,10,13,16,12,17,15,8,19,9,3,6,5,1],
00338  [0,4,2,11,7,13,16,18,10,14,8,19,17,15,12,5,1,3,6,9],
00339  [4,11,0,7,2,16,10,13,14,18,19,15,8,12,17,1,6,5,9,3],
00340  [11,7,4,2,0,10,14,16,18,13,15,12,19,17,8,6,9,1,3,5],
00341  [2,0,7,4,11,18,13,14,16,10,17,8,12,19,15,3,5,9,1,6]
00342 )$
00343 
00344 
00345 /* **************
00346    * Generators *
00347    **************
00348 */
00349 
00350 /* Strictly pandiagonal latin squares of order n, for appropriate
00351    parameter a, b (see spdl_abn_ls_p):
00352 */
00353 spdl_abn_ls(n,a,b) := 1+mod(
00354   apply(matrix,
00355         create_list(create_list(i*b+j*a,j,0,n-1), i,0,n-1)),
00356   n)$
00357 /* Checking for correct inputs: */
00358 spdl_abn_ls_p(n,a,b) := integerp(n) and integerp(a) and integerp(b) and
00359  n>a and a>b and
00360  gcd(a,n)=1 and gcd(b,n)=1 and gcd(a+b,n)=1 and gcd(a-b,n)=1$
00361 
00362 /* Remark:
00363    Let SPLS(n) for n>=0 denote the number of strictly pandiagonal latin squares
00364    of order n.
00365    For n in {0,1} trivially SPLS(n) >= 1.
00366    For n=2 obviously SPLS(n) = 0.
00367    Also for n=3 obviously SPLS(n) = 0.
00368    For n > 2 not divisible by 2,3 we can choose a := 2, b := 1, and so
00369    SPLS(n) >= 1.
00370    Leaves open n >= 4 divisible by 2 or 3 (or both) ?
00371 */
00372 
00373 
00374 /* ***************
00375    * Conversions *
00376    ***************
00377 */
00378 
00379 /* Relations to quasigroups: */
00380 
00381 /* Converting a quasigroup into a combinatorial latin square: */
00382 qgrp2comls(Q) := Q$
00383 /* Remark: More general, so a groupoid is "converted" into a
00384    "composition table".
00385 */
00386 /* Converting a unital quasigroup into a reduced latin square: */
00387 uqgrp2rls(Q) := block([L : cons(Q[3],listify(disjoin(Q[3],Q[1]))), h],
00388   h : osm2hm(map("[", L, create_list(i,i,1,length(L)))),
00389   oscom2m([L, lambda([x,y], ev_hm(h,Q[2](x,y)))]))$
00390 
00391 /* See ComputerAlgebra/Algebra/Lisp/Groupoids/Quasigroups/Basics.mac
00392    for the inverse conversions.
00393 */
00394 
00395 
00396 /* ************
00397    * Counting *
00398    ************
00399 */
00400 
00401 /* The number of reduced latin squares of order n (n >= 0): */
00402 num_rls(n) := if n=0 then 1
00403  elseif n<=11 then [1,1,1,4,56,9408,16942080,535281401856,377597570964258816,7580721483160132811489280,5363937773277371298119673540771840][n]
00404  else unknown$
00405 
00406 /* The number of latin squares of order n (n >= 0): */
00407 num_ls(n) := if n=0 then 1 else
00408  num_rls(n) * n! * (n-1)!$
00409