ODLK

ODLK
Project
Status	Active
Category	Mathematics / Combinatorics
Compute	CPU
Development
Developer	Progger
Author	Natalia Makarova, Progger
Initial release	May 19, 2017  (9 years ago)
Software
Operating system	Windows, Linux
BOINC statistics
Stats as of	22 May 2026
Performance	3885.86 GigaFLOPS
Active users	347
Total users	2,750
Active hosts	1,759
Total hosts	28,018
Metadata
Website	https://boinc.progger.info/odlk/

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. 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. 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.

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.

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.

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

Construction of Ramanujan's birthday magic square from a 4×4 Latin square with distinct diagonals and day (D), month (M), century (C) and year (Y) values, and Ramanujan's birthday example

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.

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.

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.

Applications and work units

The ODLK server runs three distinct computing applications simultaneously, each tackling a different aspect of the search:

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

1. Download and install the BOINC client from boinc.berkeley.edu.
2. Create a free account at the ODLK project website.
3. In the BOINC client, add the project URL: https://boinc.progger.info/odlk/
4. 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

• Complete database of the CF ODLC BOINC-project ODLC for 2017-2021

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).

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).

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.
• 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.

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}

• 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.

• 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.

• 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:

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

• ODLK official website
• ODLK server status
• ODLK credit statistics
• Complete CF ODLK database for 2017–2021 (forum thread)
• Latin square — Wikipedia
• Volunteer computing — Wikipedia
• SAT@home (predecessor project)