Diagonal Latin squares of order n>10
Message boards :
Code and Servers :
Diagonal Latin squares of order n>10
Message board moderation
| Author | Message |
|---|---|
|
Tomáš Brada Project administrator Volunteer developer  Send message Joined: 3 Feb 19 Deprecated: Creation of dynamic property BoincUser::$nposts is deprecated in /var/boincadm/prj/html/inc/forum.inc on line 613 Posts: 667 Credit: 432,784 RAC: 0  
|
This thread has my notes about Natalia's topic on dlk>10. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
Diagonal Latin Square converter and normalizer Windows: https://boinc.tbrada.eu/download/dlkconv.exe Source on: https://github.com/tomasbrod/tbboinc dlkconv.exe: (input-spec) [input] [(output-spec) [output]] ** Diagonal Latin Square converter and normalizer ** input-spec: Endoded/compressed (e), Alphanumeric (a), stdin (s) File (f). Encoded input can be passed immediately on command line. Othervise a NxN matrix of decimal numbers, or Alphanumeric (a) must be passed via stdin or file. Multiple orders (N) may be mixed on input. Empty lines and (one) trailing spaces are ignored. output-spec: (e)(a)(f), stdout (s), Compact (c), Diagonal (d) LS normalized on first row are written to stdout by default. Space between output squares are ommited in Compact (c) mode. With (d), output matrix is normalized on main diagonal. Example dlkconv.exe e 7yPG4 dc -- decode 7yPG4 and normalize diagonal Author: Tomas Brada (GPL) 
|
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
Here are sample dlk of orders up to 21. In brackets (n, d-trans count, mates count) 56 (4, 4, 1) 6tC (5, 5, 1) 7yPG4 (6, 6, 0) BCunXGjcgMwnhYJVEoS (10, 115, 1) BJMzz45jMmo1FfZtCjN (10, 126, 1) C1sdn7gj27pcvzhfwwHZ8JE8e12 (11, 4665, 26914) Cb1Cf6QmmZGcaVkPXc9fEN (11, 4523, 19139) DrdVfwmF2ghiNUw45W9NmZr4iDgJwV49 (12, 8760, 41644) DeGkNZGc43qaHWnNUsjfvuQNbREDKc4 (12, 5718, 2199) ECo6MLbQKvcMgoe75GDQemfFT3D1hhkb4T78aU (13, 9840, 45) EUELx2zmrdPHyTGkGJhedf1cuDmJzqhw6hUme293TPB (13, 131106, >>248703) EQPj3ELgR3gSKeFWkMopP6BeAJC7CPjMC4F4Sm9 (13, 9909, 2) Eg9RYwB8b3Z122ZAPc8VaC7TVBVmvVAz1J8fHGY3 (13, 9907, 1) F98aux31EFfDjHASPckbbhZCsweDB7qd3dcgExK6yTQ75FDD3 (14, 53247, ?) FZ6P2fxvxqsd3GrUPmTuqQRE6BCU383vKyutP7TR7G8whx (14, 364252, ?) GM5QVE2X19ffPVZutPTj5ore4DHkPSfWet1fmh9ApZUndySRTh2NyrjC (15, 305408, ?) HJUmgVNZQnTeguW9hVu4wbEppeo5hqYHNDP2hXm3qrnLkfL7mWD3KT8i7nrSmA62pM5 (16, 15456144, ?) HpSJoVM52aeVoeMypj9EmgsuyEdP99g5QgQTsD8eWLQtDkZKgnG9j4P78HbzuYS7ph73 (16, 1879316, ?) J4bx6sxd118jW7dkcsqoP3tfXwi7fXCZmHPFjzHfctpAyHkdZeJuZhQGNxX6xEPU3FfQ9V42YRHqTs9 (17, 12102527, ?) KUwuJ8TaFRKk82ckNomJHbJdRHUUzx413PBL1dq7WqLTqyLPR4paqjGSU2xcuJrfQ6bb4UVn3pVZLYHLLQkd53jhhiwedC (18, 82602438, ?) LhDfWkfWNWsfvUzFYyyvx5AqBgSFywEfyHwEYKZiydespqiN347Rwa971usDASx45jxmGzb8ssC99X3tviY3jb3Sgkr6Sz9jnZcRKLK (19, 631935677, ?) MaSWzZ2ebdm5cAneAkniTEZhST67FA1uZGAPN7FCp8a6aq6VsJNFegrB5zdWknjNnrJLzVWrCpcPmMscBDbucW6gQ29RktaVRMrY5JUMTepS7hsa64fKN3ry N23P8UTDJDB9ycBnRXmpN1NYppx7uHyBKXvyd1tFyML8G3frU64vDXHosqajFDVaQwy5qY9h4kijx9MmsgcMmedTaWoK614jZVarJ8GZrn3bqHrn3eEUXQJs8MXhb53GuDH1xyW The first letter is the order of the DLK: 5->4, B->10, J->17 (base58).
|
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
Dear Natalia. Let's keep the discussion on your forum. I want to keep this thread clean. Thanks about the reminder. |
|
Natalia Makarova Project scientist  Send message Joined: 8 Feb 19 Deprecated: Creation of dynamic property BoincUser::$nposts is deprecated in /var/boincadm/prj/html/inc/forum.inc on line 613 Posts: 423 Credit: 0 RAC: 0 |
Dear Natalia. Let's keep the discussion on your forum. I want to keep this thread clean. Did I litter your thread? Sorry. I remove the trash. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
Proposal for this project. Search for some interesting structures of ODLK 11, 12, at most 13. Searching the full space of DLK11 is impossible. But there are methods for constructing ODLKs and also there are some already found. Let's build their orthogonal mates via the method of disjoint transversal and explore the graph of their orthogonality. There are squares with number of orthogonal mates in the thousands. It should be interesting. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
For this effort to be successful, we need canonizer program to eliminate isotopes of found orthogonal mates. https://books.google.sk/books?id=3_iBDwAAQBAJ&pg=PA580&lpg=PA580&dq=latin+square+m+transform&source=bl&ots=fqYL_pi-k4&sig=ACfU3U3sOBQDhbJ_ZYzJIs691bFbXE1www&hl=sk&sa=X&ved=2ahUKEwid4t7Xw7rqAhWSqaQKHQlXByMQ6AEwDnoECAIQAQ#v=onepage&q=latin%20square%20m%20transform&f=true |
|
Natalia Makarova Project scientist Send message Joined: 8 Feb 19 Posts: 423 Credit: 0 RAC: 0 |
For this effort to be successful, we need canonizer program to eliminate isotopes of found orthogonal mates. Will you let me answer? The canonizator of DLS is easy to create. I know the algorithm. The algorithm is based on M-transformations. This is what you see in the article at your link. See https://oeis.org/A299784 A299784 Maximal size of main class for diagonal Latin squares of order n with first row 1..n. Example for n = 11 let DLS of order 11 0 1 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 0 1 2 6 7 8 9 10 0 1 2 3 4 5 9 10 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 0 4 5 6 7 8 9 10 0 1 2 3 7 8 9 10 0 1 2 3 4 5 6 10 0 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10 0 1 5 6 7 8 9 10 0 1 2 3 4 8 9 10 0 1 2 3 4 5 6 7 Create all 15360 isotop variants of this DLS (including the source one), normalize the received DLSs and select the smallest DLS in lexicographical order. This will be the canonical form of the DLS. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
De1UwzYwL6SS8rz7AjBxKwGjZgHniauF # 1952 d-trans, 373 mates Dz7CjFuppxP2HVM5qWbjKbing1UqHSBC # 2056; 560 DSVRFkvVgwPJpL677mW4DcSaX8PQTHLG # 2156; 559 DSXJawBgzzfp4AaDWeT4BLZxf6YoqxVC # 2124; 955 DYEFA9QfQEgPzyfV77WN5Z3JaVKniauF # 2240; 2148 DrMBdvMCXMsVs7iGrg9j119gSNVqHSBC # 2056; 849 D466p5vpMqqGHXz6xiDEQ2C7YzQQTHLG # 1956; 474 D6qASMdZSEhoRBsZVHZA7eBHgVZoqxVC # 1988; 1496 Dg2fkM4nefmHC6zPhDnBj57qqbnmiauF # 1880; 220 DL2LvgUE8hzgZA9o993gL77qqbnmiauF # 2252; 764 |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
Thank you Natalia for the insight. I implemented kanonizator program using all the combinations of M-transforms and trivial transforms, but it is very slow for DLK(11). Natalia, how to generate 15360 isotopes? Do you have a program? |
|
Natalia Makarova Project scientist Send message Joined: 8 Feb 19 Posts: 423 Credit: 0 RAC: 0 |
Natalia, how to generate 15360 isotopes? Do you have a program? I have the following programs by Belyshev for DLS of order 10 1. isomorfDLK10A.exe generating of 15360 normalized isotopes. No source. 2. kanonizator.exe the canonizator for format 1. No source. 3. kanonizator_dlk_1.03.exe the canonizator for format 2. There is a source. I can send you these programs if they help. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
I implemented canonical form search using M-transform and slightly optimized trivial transform search. It is not very fast, but acceptable. DLK 11 - 32 squares per second DLK 12 - 2.2 seconds per square DeGkNZGc43qaHWnNUsjfvuQNbREDKc4 -> DPtYDbUyptK6u8CzQXwTFTFrAKKnPd2 DLK 13 - 2.5 seconds per square EUELx2zmrdPHyTGkGJhedf1cuDmJzqhw6hUme293TPB -> ESsnovqZRoQ75PfnAq7yBER9peVGaW1rS2qpVt46o2 DLK 14 - 6m2,125s FsUoYuuEJiYXfsxZotxv7tbtPrPioDUsoQPjMqYwy52Kksp -> FsUoYuuEJiYXfsxZotxv7tbtPrPioDUsoQPjMqYwy52Kksp |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
1. isomorfDLK10A.exe I have sources for program 2 and 3 on my repository. I do not have program 1, but if there is no source, it will not help much. Thanks anyway. |
|
Natalia Makarova Project scientist Send message Joined: 8 Feb 19 Posts: 423 Credit: 0 RAC: 0 |
I will send you the program isomorfDLK10A.exe When canonizing, Belyshev uses hash_tabl.bin You probably know that. I don’t know how he uses it. However, this should help in the process. DLS10 and DLS11 have the same number of isotopes. Therefore, the canonizer for DLS10 and DLS11 should work equally fast. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
DLK(11) CBdLXkuMuUsLR2UMw31FGHxG64 forms a system of 31052 canonical forms ODLK. Total of 169389 orthogonal mates have been found. I do not know the tree depth. Top 10 CF-ODLK with most orthogonal mates: C1WSBL9yyhZmMTYSR5Fc8MSFU # 500 dtrans, 38 mates Cxnb7rE3MdxM5afWEXYU41a1D5 # 533 dtrans, 38 mates Cidd7mMU8d6NoGE9AhztKKdA9 # 550 dtrans, 47 mates CAZRkazvwU9Po3vuRuswAgTj4 # 453 dtrans, 127 mates CKm3qs57ahrTHAjZvEdUjyYx # 4603 dtrans, 18530 mates CkWiTnTuCKwKk1AjqYvVT9kme3 # 4523 dtrans, 19139 mates CFcPGHszAkh4MBHsnfDtAJqz5 # 4675 dtrans, 24593 mates CWPTKSidjqhVrXPHRg8fVz9N4W3 # 4665 dtrans, 26914 mates CsRcX7AMxNsp9r9mUwANzrWa # 4813 dtrans, 30198 mates CBdLXkuMuUsLR2UMw31FGHxG64 # 4828 dtrans, 32462 mates |
|
Natalia Makarova Project scientist Send message Joined: 8 Feb 19 Posts: 423 Credit: 0 RAC: 0 |
DLK(11) CBdLXkuMuUsLR2UMw31FGHxG64 forms a system of 31052 canonical forms ODLK. DLS in this set with a normalized main diagonal? If so, please make a list of the different side diagonals from the DLS of this set. This defines the rules. For DLS8 there are 20 rules, for DLS9 there are 20 rules, for DLS10 there are 67 rules. For DLS11 exists ??? rules. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
DLK(11) CBdLXkuMuUsLR2UMw31FGHxG64 forms a system of 31052 canonical forms ODLK. In them, 27410 unique "rules" have been found. A DLK rule is just the main anti-diagonal of a diagonally-normalized DLK. They start with 2, 3, 4, 6, 7, 8 and 9. None start with 1, 5 or 10. |
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
Releasing programs for DLK(N). Source on: https://github.com/tomasbrod/tbboinc dlkconv.exe: https://boinc.tbrada.eu/forum_thread.php?id=3104&postid=4132 https://boinc.tbrada.eu/download/ortogonb.exe ortogonb.exe: [-co] (Input) ** Search for Orthogonal mates of Diagonal Latin Square ** -c print number of transverses and exit -o output orthogonal mates like they are found Input: encoded diagonal latin square (see dlkconv.exe) Output: metadata and orthogonal squares in encoded format Returns 0 if orthogonal mates found, 1 if not. Example ortogonb.exe BJMzz45jMmo1FfZtCjN Author: Tomas Brada (GPL) https://boinc.tbrada.eu/download/isortogon.exe isortogon.exe: <Input >Output ** Check Diagonal Latin Squares for Orthogonality ** In the input set, checks if any LK are orthogonal to themselves and each other. https://boinc.tbrada.eu/download/ortowalk.exe ortowalk.exe: FileName ** Explore the full graph of DLK orthogonality ** Insert the initial CF-DLK into FileName.todo then run "ortowalk.exe FileName" (without the todo) Author: Tomas Brada (GPL) https://boinc.tbrada.eu/download/kanonb.exe kanonb.exe: <input >output ** Diagonal Latin Square Kanonizer ** Input and Output in Encoded form (see dlkconv) Author: Tomas Brada (GPL) https://boinc.tbrada.eu/download/rules.exe rules.exe: <input >output ** Diagonal Latin Square Rule Extractor ** You may want to use kanonb first. Author: Tomas Brada (GPL)
|
|
Tomáš Brada Project administrator Volunteer developer Send message Joined: 3 Feb 19 Posts: 667 Credit: 432,784 RAC: 0
|
EKphoSM6cT6Zkhy1AAJU5F9sZHr31LSAFnggrjPR (cf of ECo6MLbQKvcMgoe75GDQemfFT3D1hhkb4T78aU) orthogonal mates: https://boinc.tbrada.eu/download/EKphoSM6cT6Zkhy1AAJU5F9sZHr31LSAFnggrjPR.txt part of graph: https://boinc.tbrada.eu/download/EKphoSM6cT6Zkhy1AAJU5F9sZHr31LSAFnggrjPR.orto Full graph of CBdLXkuMuUsLR2UMw31FGHxG64 (from Cb1Cf6QmmZGcaVkPXc9fEN) https://boinc.tbrada.eu/download/CBdLXkuMuUsLR2UMw31FGHxG64.orto Co-squares: https://boinc.tbrada.eu/download/CBdLXkuMuUsLR2UMw31FGHxG64.orto.todo Rules: https://boinc.tbrada.eu/download/CBdLXkuMuUsLR2UMw31FGHxG64.rules DPtYDbUyptK6u8CzQXwTFTFrAKKnPd2 (cf of DeGkNZGc43qaHWnNUsjfvuQNbREDKc4) Part of graph: https://boinc.tbrada.eu/download/DPtYDbUyptK6u8CzQXwTFTFrAKKnPd2.orto Mates: https://boinc.tbrada.eu/download/DeGkNZGc43qaHWnNUsjfvuQNbREDKc4.txt
|
|
Natalia Makarova Project scientist Send message Joined: 8 Feb 19 Posts: 423 Credit: 0 RAC: 0 |
DLK(11) CBdLXkuMuUsLR2UMw31FGHxG64 forms a system of 31052 canonical forms ODLK. These are DLSs of order 11 normalized along the main diagonal. But probably this is not CF. 0 5 9 6 10 8 2 3 7 4 1 4 1 10 9 5 3 7 2 6 0 8 6 7 2 1 9 4 10 5 3 8 0 8 0 1 3 7 10 9 6 4 2 5 7 3 5 2 4 1 8 0 10 6 9 3 9 8 0 6 5 4 10 2 1 7 1 4 0 10 2 9 6 8 5 7 3 5 8 6 4 1 0 3 7 9 10 2 10 2 7 5 0 6 1 9 8 3 4 2 10 4 8 3 7 5 1 0 9 6 9 6 3 7 8 2 0 4 1 5 10 0 8 5 10 6 2 9 4 7 3 1 5 1 10 8 3 6 2 9 4 0 7 6 0 2 9 7 1 5 10 3 4 8 4 2 8 3 9 7 10 6 1 5 0 7 3 1 2 4 0 8 5 10 6 9 8 9 4 7 10 5 0 3 6 1 2 1 4 0 5 2 10 6 8 9 7 3 10 5 9 4 0 3 1 7 2 8 6 2 6 7 0 5 9 3 1 8 10 4 3 10 6 1 8 4 7 2 0 9 5 9 7 3 6 1 8 4 0 5 2 10 Please show CF for these DLS. See https://boinc.progger.info/odlk/forum_thread.php?id=162&postid=5978 1 0 3 2 7 5 8 4 10 6 9 1 0 3 2 7 5 8 9 10 4 6 1 0 3 2 7 5 8 9 10 6 4 1 0 3 2 7 5 8 10 6 4 9 1 0 3 2 7 5 9 8 10 4 6 1 0 3 2 7 5 9 10 6 4 8 1 0 3 2 7 5 10 9 4 8 6 1 0 3 2 8 5 7 4 10 6 9 1 0 3 2 8 5 9 4 6 10 7 1 0 3 2 8 5 10 9 7 4 6 1 0 3 2 9 5 8 10 6 4 7 1 0 3 2 9 5 10 4 7 6 8 1 0 3 6 2 5 7 10 4 8 9 1 0 3 6 2 5 8 10 7 4 9 . . . . . . . This is not rules?? |
©2024 Tomáš Brada