Diagonal Latin squares of order n>10

Message boards : Code and Servers : Diagonal Latin squares of order n>10
Message board moderation

To post messages, you must log in.

1 · 2 · 3 · 4 . . . 5 · Next

AuthorMessage
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4131 - Posted: 3 Jul 2020, 8:21:57 UTC

This thread has my notes about Natalia's topic on dlk>10.
ID: 4131 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4132 - Posted: 3 Jul 2020, 8:23:34 UTC

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)

ID: 4132 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4133 - Posted: 3 Jul 2020, 8:27:41 UTC
Last modified: 5 Jul 2020, 21:28:59 UTC

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).
ID: 4133 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4136 - Posted: 4 Jul 2020, 7:41:19 UTC
Last modified: 4 Jul 2020, 7:41:49 UTC

Dear Natalia. Let's keep the discussion on your forum. I want to keep this thread clean.
Thanks about the reminder.
ID: 4136 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Natalia Makarova
Project scientist
Avatar

Send message
Joined: 8 Feb 19
Posts: 365
Credit: 0
RAC: 0
Message 4137 - Posted: 4 Jul 2020, 8:05:15 UTC - in response to Message 4136.  
Last modified: 4 Jul 2020, 8:13:59 UTC

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.
ID: 4137 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4138 - Posted: 5 Jul 2020, 20:48:59 UTC

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.
ID: 4138 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4139 - Posted: 7 Jul 2020, 7:41:49 UTC

ID: 4139 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Natalia Makarova
Project scientist
Avatar

Send message
Joined: 8 Feb 19
Posts: 365
Credit: 0
RAC: 0
Message 4141 - Posted: 8 Jul 2020, 11:13:19 UTC - in response to Message 4139.  
Last modified: 8 Jul 2020, 11:43:34 UTC

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

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.
1, 0, 0, 2, 4, 96, 192, 1536, 1536, 15360, 15360, 184320, 184320, 2580480, 2580480


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.
ID: 4141 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4143 - Posted: 8 Jul 2020, 19:40:06 UTC

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
ID: 4143 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4144 - Posted: 8 Jul 2020, 19:43:03 UTC - in response to Message 4141.  
Last modified: 8 Jul 2020, 19:45:33 UTC

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?
ID: 4144 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Natalia Makarova
Project scientist
Avatar

Send message
Joined: 8 Feb 19
Posts: 365
Credit: 0
RAC: 0
Message 4145 - Posted: 8 Jul 2020, 23:39:17 UTC - in response to Message 4144.  

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.
ID: 4145 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4146 - Posted: 9 Jul 2020, 9:03:48 UTC
Last modified: 9 Jul 2020, 11:59:23 UTC

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
ID: 4146 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4147 - Posted: 9 Jul 2020, 9:36:35 UTC - in response to Message 4145.  
Last modified: 9 Jul 2020, 13:35:53 UTC

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 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.
ID: 4147 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Natalia Makarova
Project scientist
Avatar

Send message
Joined: 8 Feb 19
Posts: 365
Credit: 0
RAC: 0
Message 4148 - Posted: 9 Jul 2020, 10:13:46 UTC

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.
ID: 4148 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4149 - Posted: 9 Jul 2020, 11:13:46 UTC

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
ID: 4149 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Natalia Makarova
Project scientist
Avatar

Send message
Joined: 8 Feb 19
Posts: 365
Credit: 0
RAC: 0
Message 4150 - Posted: 10 Jul 2020, 5:33:28 UTC - in response to Message 4149.  

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.
ID: 4150 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4164 - Posted: 10 Jul 2020, 20:27:17 UTC - in response to Message 4149.  

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.
ID: 4164 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4166 - Posted: 10 Jul 2020, 21:08:40 UTC
Last modified: 11 Jan 2021, 15:08:17 UTC

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)

ID: 4166 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Tomáš Brada
Project administrator
Volunteer developer
Avatar

Send message
Joined: 3 Feb 19
Posts: 655
Credit: 456,868
RAC: 1
Message 4167 - Posted: 10 Jul 2020, 21:14:38 UTC
Last modified: 10 Jul 2020, 21:21:01 UTC

ID: 4167 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Natalia Makarova
Project scientist
Avatar

Send message
Joined: 8 Feb 19
Posts: 365
Credit: 0
RAC: 0
Message 4170 - Posted: 11 Jul 2020, 1:13:06 UTC - in response to Message 4164.  
Last modified: 11 Jul 2020, 1:24:38 UTC

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.

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??
ID: 4170 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · 3 · 4 . . . 5 · Next

Message boards : Code and Servers : Diagonal Latin squares of order n>10

©2021 Tomáš Brada