ODLK
}}
[[File:{{#setmainimage:Default water.jpg}}|alt=image|center|frameless]]
ODLK is a BOINC based volunteer computing project that needs your help to research 10th order diagonal Latin squares.
Why ODLK?
Continue the work of the scientific BOINC project SAT@home, in which new orthogonal pairs of 10th order DLKs were searched.
The history of searching for orthogonal pairs of diagonal Latin squares (DLS) of order 10 stretches back decades. The first three orthogonal pairs were found in 1992 and published in the landmark paper "Completion of the Spectrum of Orthogonal Diagonal Latin Squares" by J. W. Brown et al.[1] The problem then lay largely dormant until the advent of volunteer computing gave researchers the raw computational power to search more thoroughly.
Between 2012 and 2016, the scientific BOINC project SAT@home took up the challenge, reducing the search for orthogonal pairs to instances of the Boolean satisfiability problem (SAT) and distributing the work across volunteer computers worldwide. During a 10-month computational experiment alone, SAT@home discovered 29 previously unknown orthogonal pairs.[2] By the time the project concluded, it had unearthed 77 unique orthogonal pairs of order-10 DLS, yielding 154 unique canonical forms (CF) of ODLS.[3]
With SAT@home finished, the baton passed to ODLK. Launched on 19 May 2017 by mathematician Natalia Makarova and developer Progger, ODLK took a new approach: rather than merely finding more pairs, it set out to compile a complete database of all canonical forms of order-10 diagonal Latin squares that possess at least one orthogonal mate. The project celebrated its seventh anniversary on 19 May 2024.[4]
Goal
This project compiles a database of canonical forms (CF) of 10th order diagonal Latin squares (DLS) having orthogonal diagonal Latin squares (ODLS).
A Latin square of order n is an n×n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. A diagonal Latin square (DLS) additionally requires that both the main diagonal and the back diagonal of the square each contain every symbol exactly once — making it a far more constrained structure. Two DLS are orthogonal (ODLS) if, when superimposed, every possible ordered pair of symbols appears exactly once across all n² cells.
The name "Latin square" itself was inspired by the mathematical papers of Leonhard Euler (1707–1783), who used Latin characters as symbols when he initiated the general theory of Latin squares in the 18th century.[5]
Finding DLS of order 10 that have any orthogonal partner at all is a computationally intensive problem. The goal of ODLK is therefore not just to find individual solutions, but to produce a complete, enumerated canonical database so that mathematicians worldwide can study the structural properties of these objects — symmetries, transversal counts, clique sizes, and more.
Background: Latin squares and their orthogonal pairs
In combinatorics and experimental design, Latin squares have been studied since Euler's time. They are closely related to magic squares, Sudoku puzzles, error-correcting codes, and the design of statistical experiments. A particularly important open question for much of the 20th century was the "36 officers problem" posed by Euler: do orthogonal Latin squares of order 6 exist? The answer (no) was not proven until 1901. Euler's broader conjecture — that orthogonal pairs fail to exist for orders n ≡ 2 (mod 4) — was spectacularly refuted in 1960 when Bose, Shrikhande, and Parker demonstrated that orthogonal pairs exist for all orders n ≥ 3 except n = 2 and n = 6.[6]
For diagonal Latin squares the landscape is more restrictive. It has been proven that ODLS(n) exist for all n except 2, 3, 6, 10, 14, 15, 18, and 26 — with ODLS(10) being the most computationally challenging case for which solutions exist, and where ODLK does its work.[7]
Applications
The construction and enumeration of orthogonal diagonal Latin squares has applications in:
- Experimental design: Latin squares underpin balanced experimental layouts in agriculture, medicine, and engineering. Diagonal constraints yield designs with additional balance properties along diagonals.
- Coding theory: ODLS constructions relate to classes of error-correcting codes and are connected to the theory of finite projective planes.
- Combinatorial mathematics: The database of canonical forms allows researchers to study the spectrum of diagonal transversals, symmetry classes, and clique structure among ODLS — properties that bear on longstanding open problems in combinatorics.
- Algorithm benchmarking: Searching for ODLS of order 10 provides a natural, difficult benchmark for SAT solvers and other combinatorial search methods.
Project team / Sponsors
Natalia Makarova, Progger
The project was conceived and launched by Natalia Makarova, a Russian mathematician who has been active in Latin square research and the Russian-language volunteer computing community (including the boinc.ru forums) for many years. The technical infrastructure is maintained by Progger, who hosts the project server at boinc.progger.info. The related spin-off project ODLK1 also credits Stefano Tognon (ice00) as a contributor.[8]
Applications and work units
The ODLK server runs three distinct computing applications simultaneously, each tackling a different aspect of the search:[9]
| Application | Description | Avg. runtime (hours) |
|---|---|---|
| odlk3@home | Main brute-force search for new CF ODLK | 0.31 (range 0.01–13.12) |
| odlkmin@home | Search optimised for finding DLS with minimum orthogonal mates | 0.31 (range 0.01–13.46) |
| odlkmax@home | Search optimised for finding DLS with maximum orthogonal mates | 0.30 (range 0.01–13.16) |
Work units are generated server-side and sent to volunteer computers running BOINC. Results are validated by majority consensus before being assimilated into the database.
How to participate
- Download and install the BOINC client from boinc.berkeley.edu.
- Create a free account at the ODLK project website.
- In the BOINC client, add the project URL:
https://boinc.progger.info/odlk/ - BOINC will automatically download work units and return results when complete.
The project currently supports Windows and Linux. Tasks run on standard CPU hardware; no GPU is required.
Scientific results
By January 2022, the project had produced a complete canonical-form database for the period 2017–2021, published by Natalia Makarova on the project forum. The database contained 3,078,504 canonical forms of ODLK of order 10 (plus a supplementary 6,370 CF found in earlier symmetry-search sub-applications, bringing the full total to over 3,084,874 CF).[10]
Among the highlights of the 2017–2021 database analysis, carried out by volunteer contributor Demis using software by Alexey Belyshev:
- The database was organised across 67 "rows" (classes of DLS), with the largest row (Row 65) containing 327,753 CF.
- 17 triplets of mutually orthogonal DLS were identified — meaning a single DLS has at least two distinct orthogonal mates — as well as 2 quadruplets (a DLS with at least three distinct orthogonal mates).
- 5,806 doublets (DLS with exactly two orthogonal mates in the database) were found.
- Analysis of diagonal transversals across all 3,078,504 CF revealed only 97 distinct values, ranging from 68 to 165.
- One especially remarkable quadruplet DLS was found to have 866 diagonal transversals — the highest known count for a DLS of order 10 — and exhibits multiple rare symmetry types.
The 2017–2021 database is available for download from Yandex Disk (47 MB archive).[11]
Related projects
- SAT@home (2012–2016) — the predecessor project that found the first 77 unique orthogonal pairs of order-10 DLS using SAT-solving techniques. Run by the Institute for System Analysis of the Russian Academy of Sciences.[12]
- ODLK1 — a parallel BOINC project hosted at
boinc.multi-pool.info/latinsquares, run by the same scientific team with technical support from Stefano Tognon (ice00). ODLK1 continues to expand the database beyond what ODLK alone covers. - Gerasim@home — a related Russian volunteer computing project that studied transversal properties of diagonal Latin squares of small order (up to order 8).
- ODLK2025 — a newer project by Natalia Makarova launched in January 2025, continuing the line of ODLK research.[13]
Scientific papers
The following peer-reviewed and conference papers are directly associated with the research program underpinning ODLK:
- E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, "Using Volunteer Computing to Study Some Features of Diagonal Latin Squares," Open Engineering, vol. 7, no. 1, pp. 453–460, 2017. doi:10.1515/eng-2017-0052}[14]
- E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, "Enumerating the Transversals for Diagonal Latin Squares of Small Order," CEUR Workshop Proceedings, BOINC:FAST 2017, vol. 1973, pp. 6–14, 2017.
- O. S. Zaikin, S. E. Kochemazov, "The Search for Systems of Diagonal Latin Squares Using the SAT@home Project," International Journal of Open Information Technologies, 2015.[15]
- O. Zaikin, A. Zhuravlev, S. Kochemazov, E. Vatutin, "On the Construction of Triples of Diagonal Latin Squares of Order 10," Electronic Notes in Discrete Mathematics, vol. 54, pp. 307–312, 2016. doi:10.1016/j.endm.2016.09.053}
- E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, M. O. Manzuk, N. N. Nikitina, V. S. Titov, "Central Symmetry Properties for Diagonal Latin Squares," Problems of Information Technology, 2019, no. 2, pp. 3–8.[16]
- Eduard Vatutin, Alexey Belyshev, Natalia Nikitina, Maxim Manzuk, Alexander Albertian, Ilya Kurochkin, Alexander Kripachev, Alexey Pykhtin, "Diagonalization and Canonization of Latin Squares," Supercomputing — Russian Supercomputing Days (RuSCDays 2023), LNCS vol. 14389, Springer, Cham, pp. 48–61.
- J. W. Brown, F. Cherry, L. Most, E. Parker, W. Wallis, "Completion of the Spectrum of Orthogonal Diagonal Latin Squares," Lecture Notes in Pure and Applied Mathematics, vol. 139, pp. 43–49 (1992/1993). [Foundational paper finding the first three orthogonal pairs.]
Current statistics
Template:As of, the ODLK server reports the following statistics:[17]
| Metric | Value |
|---|---|
| Users with credit | 2,750 |
| Users with recent credit | 347 |
| Computers with credit | 28,018 |
| Computers with recent credit | 1,759 |
| Current performance | 3,885.86 GigaFLOPS |
| Tasks ready to send | 40,894 |
| Tasks in progress | 44,505 |
External links
References
- ↑ J. W. Brown, F. Cherry, L. Most, E. Parker, W. Wallis, Completion of the Spectrum of Orthogonal Diagonal Latin Squares, Lecture Notes in Pure and Applied Mathematics, vol. 139, pp. 43–49 (1992/1993).
- ↑ O. S. Zaikin, S. E. Kochemazov, The Search for Systems of Diagonal Latin Squares Using the SAT@home Project, International Journal of Open Information Technologies, 2015. [1]
- ↑ ODLK project home page
- ↑ ODLK news, May 2024
- ↑ Latin square — Wikipedia
- ↑ Mutually orthogonal Latin squares — Wikipedia
- ↑ B. Du, Orthogonal Diagonal Latin Squares of Order 14, cited at Wikipedia.
- ↑ ODLK1 — BOINC Synergy wiki
- ↑ ODLK server status, 22 May 2026
- ↑ ODLK forum, "Complete database of CF ODLK for 2017–2021", January 2022
- ↑ ODLK forum thread 213
- ↑ O. S. Zaikin, S. E. Kochemazov, SAT-based Search for Systems of Diagonal Latin Squares in Volunteer Computing Project SAT@home, IEEE FRUCT Conference, 2016. [2]
- ↑ BOINC forum: New project ODLK2025, January 2025
- ↑ De Gruyter: Using Volunteer Computing to Study Some Features of Diagonal Latin Squares
- ↑ INJOIT: The Search for Systems of Diagonal Latin Squares Using the SAT@home Project
- ↑ ResearchGate: Central Symmetry Properties for Diagonal Latin Squares
- ↑ ODLK Server Status, 22 May 2026