Rakesearch

RakeSearch
RakeSearch project logo
Project
Status	Active
Category	Mathematics
Compute	CPU
Development
Developer	Natalia Nikitina, hoarfrost
Author	Natalia Nikitina
Sponsor	Karelian Research Center of the Russian Academy of Sciences
Maintainer	The searchers team, Karelian Research Center of the Russian Academy of Sciences
Initial release	September 8, 2017  (9 years ago)
Repository	GitHub (community-optimized client)
Software
Written in	C++
Operating system	Windows, Linux
BOINC statistics
Stats as of	May 23, 2026  (0 years ago)
Performance	12,351 GigaFLOPS
Active users	522
Total users	2,528
Active hosts	1,661
Total hosts	13,104
Metadata
Website	https://rake.boincfast.ru/rakesearch/

RakeSearch is a BOINC based volunteer computing project that needs your help to process diagonal Latin squares.

Background: Latin squares and their diagonals

A Latin square of order <math>n</math> is an <math>n \times n</math> array filled with <math>n</math> different symbols, each occurring exactly once in every row and exactly once in every column. Formally, it is a set of <math>n^2</math> triples <math>(r, c, s)</math> such that all ordered pairs <math>(r, c)</math>, <math>(r, s)</math>, and <math>(c, s)</math> are distinct.

A diagonal Latin square (DLS) of order <math>n</math> is a Latin square in which both the main diagonal and the main antidiagonal also contain each of the <math>n</math> symbols exactly once. This additional constraint makes diagonal Latin squares considerably rarer and more difficult to enumerate than ordinary Latin squares. They are closely related to magic squares and have applications in experimental design and combinatorics.

Two Latin squares <math>A</math> and <math>B</math> of the same order <math>n</math> are said to be orthogonal if, when superimposed, every ordered pair of symbols appears exactly once across the <math>n^2</math> cells. A pair of mutually orthogonal diagonal Latin squares is abbreviated ODLS. It has been proved that ODLS of order <math>n</math> exist for all <math>n</math> except <math>n \in \{2, 3, 6, 10, 14, 15, 18, 26\}</math>, with the first three being provably impossible.

The orthogonality graph of a set of diagonal Latin squares has one node per DLS and an edge between any two squares that are mutually orthogonal. Characterizing these graphs for squares of increasing order is a central goal of RakeSearch.

Why RakeSearch?

The total number of diagonal Latin squares grows super-exponentially with order. The number of reduced DLS of order 9 alone runs into the billions, making brute-force enumeration of all objects impractical on any single machine or even on conventional HPC clusters within a reasonable timeframe. Volunteer distributed computing provides the only viable path to exhaustively probe the structure of the space for orders 9 and above.

Beyond sheer scale, many key quantities — such as the number of transversals, the spectrum of intercalates, and the structure of orthogonality graphs — were either entirely unknown or known only approximately before the project began. Several of these have since been confirmed or newly computed by RakeSearch and submitted to the On-Line Encyclopedia of Integer Sequences (OEIS).

Goal

Investigate the diagonal Latin squares space. Specifically, the project aims to:

• Enumerate and characterize the orthogonality graphs of diagonal Latin squares of orders 9, 10, and beyond.
• Determine exact values for numerical characteristics of DLS such as the number of transversals, diagonal transversals, and intercalates.
• Confirm, extend, or newly establish integer sequences in the OEIS related to DLS.
• Support joint experiments with the related Gerasim@home project on the BOINC platform.

Methods

Penyelesaian Sudoku

The enormous size of the diagonal Latin squares space makes it unfeasible to enumerate all its objects in reasonable time. Sophisticated search methods and the BOINC platform are essential to meet the computational requirements.

RakeSearch implements an application that picks up separate pairs of mutually orthogonal DLS, which allows reconstruction of full graphs of their orthogonality.

The core strategy is a rake search: starting from a single DLS, the application systematically searches for all squares that are row-permutational ODLS partners to it, building up the local neighborhood in the orthogonality graph. A work unit corresponds to one such search rooted at a particular base square. The full set of work units covers the entire space at the current order.

For order 9, the complete space comprised approximately 23.3 million work units. As of January 2018, after roughly five months of operation, over 1.2 million units had been processed.

A community-developed optimized application, maintained separately on GitHub, provides substantially faster runtimes on both x86 and x86_64 hardware using SSE2 and SSSE3 instruction sets.

Active applications

As of May 2026, the project runs four application streams:

• Joint search of ODLS12 with Gerasim project — searching for orthogonal pairs of diagonal Latin squares of order 12 in collaboration with the Gerasim@home project.
• Joint search of DLS spectra with Gerasim project — computing spectra of numerical characteristics in collaboration.
• Generalized symmetries in parastrophic slices for DLS of order 10 — studying structural symmetries in the order-10 space.
• Spectra of Latin squares — constructing spectra of numerical characteristics (transversals, intercalates, etc.) for Latin squares of higher orders.

Source code

• Diagonal Latin squares of Rank 9 (R9)
• Diagonal Latin squares of Rank 10 (R10)

History

RakeSearch was launched on 8 September 2017, initially as a Linux-only CPU project hosted on the BOINC infrastructure operated by the boincfast.ru community. Windows application support was added in the months following launch. The project was presented at the BOINC:FAST 2017 conference, where two presentations on ODLS generated by row permutation were given.

In its first phase, the project focused on exhaustive characterization of the DLS space of order 9 (R9). The R9 search was formally completed and archived, with all results, workunits, graphs, and source code published.

The project subsequently moved to order 10 (R10), and later to higher-order experiments including searches for spectra of transversals and intercalates for orders up to 25 and beyond. Following a period of inactivity and a hardware failure (loss of both mirror SSD discs), the project was relaunched with new hardware and updated BOINC server software.

The project is a collaboration with Gerasim@home, also operated by Eduard Vatutin and colleagues, which handles related enumeration tasks on the BOINC platform at gerasim.boinc.ru.

Project team / Sponsors

The project is developed and maintained by Natalia Nikitina (Institute of Applied Mathematical Research, Karelian Research Center of the Russian Academy of Sciences, Petrozavodsk) and the volunteer known as hoarfrost, with the broader The searchers team at the Karelian Research Center of the Russian Academy of Sciences.

Scientific co-authors on published results include Eduard Vatutin (Southwest State University, Kursk), Maxim Manzyuk (Internet portal BOINC.RU, Moscow), Oleg Zaikin, Stepan Kochemazov, Alexey Belyshev, Alexander Albertian, Ilya Kurochkin, Alexander Kripachev, Alexey Pykhtin, Ilya Chernov, and Evgeny Ivashko, among others.

The project received financial support from the Russian Foundation for Basic Research under grant numbers 18-07-00628_a, 18-37-00094_mol_a, and 17-07-00317_a.

Scientific results

The BOINC platform, on which RakeSearch runs.

RakeSearch has produced a range of verified mathematical results since its launch. Completed search archives and the discovered orthogonality graphs are published on the project graphs page.

OEIS sequences confirmed, updated, or newly discovered

The following sequences in the On-Line Encyclopedia of Integer Sequences (OEIS) have been confirmed, updated (values corrected), rechecked (independently re-derived), or newly established based on RakeSearch experiments:

Sequence	Description	Status
A287644	Maximal number of transversals in a diagonal Latin square of order <math>n</math>	Confirmed
A287645	Minimal number of transversals in a diagonal Latin square of order <math>n</math>	Confirmed
A287647	Minimal number of diagonal transversals in a diagonal Latin square of order <math>n</math>	Confirmed
A287648	Maximal number of diagonal transversals in a diagonal Latin square of order <math>n</math>	Confirmed
A287651	Number of reduced pairs of orthogonal diagonal Latin squares of order <math>n</math>	Updated
A287695	Maximal number of normalized DLS that can be orthogonal to the same DLS of order <math>n</math>	Confirmed
A287764	Number of main classes of diagonal Latin squares of order <math>n</math>	Rechecked
A307163	Minimal number of intercalates in a diagonal Latin square of order <math>n</math>	Confirmed
A307164	Maximal number of intercalates in a diagonal Latin square of order <math>n</math>	Confirmed
A309210	Number of main classes of extended self-orthogonal DLS of order <math>n</math>	Updated
A329685	Number of main classes of self-orthogonal DLS of order <math>n</math>	Confirmed
A330391	Number of main classes of DLS of order <math>n</math> with at least one orthogonal diagonal mate	Updated
A333366	Number of main classes of doubly self-orthogonal DLS of order <math>n</math>	Confirmed
A338250	Number of isomorphism classes of pairs of orthogonal DLS of order <math>n</math>	New
A339926	Number of pairs of orthogonal DLS of order <math>n</math>	New

SAT-based search

RakeSearch has also hosted a SAT-CMS-based (cube-and-conquer) experiment to search for orthogonal diagonal Latin squares of order 10, with found pairs published on the project site. This method was described formally in a 2021 paper.

Scientific publications

The following is a list of conference papers with results arising from RakeSearch. Source: BOINC Publications list and the project publications page.

Conference papers

• "Diagonalization and Canonization of Latin Squares". In:(2023}).Supercomputing. RuSCDays 2023. Springer. DOI: 10.1007/978-3-031-49435-2_4.

• "Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-and-Conquer". In:(2021}).Supercomputing. RuSCDays 2021. Springer. DOI: 10.1007/978-3-030-92864-3_38.

• "Enumerating the Orthogonal Diagonal Latin Squares of Small Order for Different Types of Orthogonality". In:(2020}).Supercomputing. RuSCDays 2020. Springer. DOI: 10.1007/978-3-030-64616-5_50.

• "Replication of "Tail" Computations in a Desktop Grid Project". In:(2020}).Supercomputing. RuSCDays 2020. Springer. DOI: 10.1007/978-3-030-64616-5_52.

• Vatutin, Eduard.(2020})."Second International Conference Information, Computation, and Control Systems for Distributed Environments 2020 (ICCS-DE 2020)".link.

• "Start-up and the Results of the Volunteer Computing Project RakeSearch". In:(2019}).Supercomputing. RuSCDays 2019. Springer. pp. 725–734. DOI: 10.1007/978-3-030-36592-9_59.(Communications in Computer and Information Science, vol. 1129).

• "On Sharing Workload in Desktop Grids". In:(2018}).Supercomputing. RuSCDays 2018. Springer. DOI: 10.1007/978-3-030-05807-4_51. (uses statistics from RakeSearch)

Papers in press / recent

• Vatutin, E. et al. Simulation of Volunteer Computing in a Desktop Grid System, Russian Supercomputing Days 2024. DOI: 10.1007/978-3-031-78462-0_9 (uses statistics from RakeSearch)

• Vatutin, E. et al. Construction of heuristic approximations of the spectra of the number of intercalates in diagonal Latin squares of orders 10-25, National Supercomputing Forum 2024 (NSCF-2024). (in press)

• Vatutin, E. et al. Construction of the spectra of intercalates number in the Latin squares of orders 18-28 using volunteer distributed computing in the BOINC platform, Recognition 2025. (in press)

• Vatutin, E. et al. Using spectra of numerical characteristics of Latin squares during getting spectra of diagonal Latin squares, Science and Education in the Development of Industrial, Social and Economic Spheres of Russian Regions. Murom, 2025. (in press)

Presentations

• Modification of the load balancing method in a desktop grid for solving problems of constructing Latin square spectra, GRID'2025, 2025.
• Start-up and the results of the volunteer computing project RakeSearch, Russian Supercomputing Days 2019.
• Petrozavodsk Desktop Grid Community, BOINC Workshop 2018.
• Characterizing orthogonal diagonal Latin squares of order 9 discovered in a distributed computing project, Recognition-2018.
• ODLS generated by rows permutation, BOINC:FAST 2017.

Server status

As of 23 May 2026, the project server reports the following statistics:

Metric	Value
Current GigaFLOPS	12,351.63
Users with credit	2,528
Users with recent credit	522
Computers with credit	13,104
Computers with recent credit	1,661
Tasks ready to send	15,463
Tasks in progress	16,012

Research progress on current enumeration targets (percentage of space explored):

Target	Progress (%)
E0043	6.315
E1056	1.391
E1067	5.670
E1076	0.065
E1079	2.037

Contributing

To participate, download and install the BOINC client and attach to the project at https://rake.boincfast.ru/rakesearch/. The project currently supports Windows (x86_64) and Linux platforms, with CPU-only computation. Account creation requires either registration through the project website (an invitation code from Crunch_4Science is needed for web registration) or direct attachment via the BOINC Manager.

See also

• Latin square
• Orthogonal Latin squares
• BOINC
• Volunteer computing
• Gerasim@home

External links

• RakeSearch official website
• Project publications page
• Discovered orthogonality graphs
• Community-optimized client on GitHub
• RakeSearch at BOINC Publications list
• Personal page of Eduard I. Vatutin