Dear participants of the project!

Probably, there are many programmers among you.

A contest is announced to the best optimization of program of search the orthogonal LS for a given LS of order 10.
This is a very important program!

The author of this program is colleague S. Belyaev.
The program was created and posted for general use on the Math Help Planet forum on February 29, 2016.
http://mathhelpplanet.com/viewtopic.php?p=261989#p261989

You can download the archive from the following link
https://yadi.sk/d/2sX-6d_Vphfsx

The source code of the program in archive is available.

---

https://yadi.sk/i/S417t0IpwnP6r

I want to note that the excellent optimization of this program was made by the participant of the project team Harry White.
Optimization of Harry gave an acceleration of about 10 times.

You can download the version of the program Harry White from the following link
http://budshaw.ca/temp/lat02nmC.zip

The source code of the program is available.

But I think that there are still reserves for program optimization.

---

https://yadi.sk/i/S417t0IpwnP6r

You can get acquainted with the transversals in the article: Ian M. Wanless "Transversals in Latin squares".
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.244.6006&rank=17&q=Ian Wanless&osm=&ossid=

Abstract
A latin square of order n is an n×n array of n symbols in which each symbol occurs exactly once in each row and column. A transversal of such a square is a set of n entries such that no two entries share the same row, column or symbol. Transversals are closely related to the notions of complete mappings and orthomorphisms in (quasi)groups, and are fundamental to the concept of mutually orthogonal latin squares. Here we provide a brief survey of the literature on transversals. We cover (1) existence and enumeration results, (2) generalisations of transversals including partial transversals and plexes, (3) the special case when the latin square is a group table, (4) a connection with covering radii of sets of permutations. The survey includes a number of conjectures and open problems.

---

https://yadi.sk/i/S417t0IpwnP6r

If you have any questions, please write

1) in this topic;
2) a personal message on the forum;
3) a personal message to e-mail natalimak1@yandex.ru

---

https://yadi.sk/i/S417t0IpwnP6r

See also the topic "On transversals of Latin squares"
https://boinc.progger.info/odlk/forum_thread.php?id=47

In the topic there are several specific examples with illustrations.

---

https://yadi.sk/i/S417t0IpwnP6r

A little information about working with the program Harry White.

All source LSs must be written to the inp.txt file
This is the default input file.

All orthogonal LSs will be written to the file Ort.txt
With each new program run, the Ort.txt file is cleared.

The console displays progress (+2048 LS).

---

https://yadi.sk/i/S417t0IpwnP6r

Test

Unfortunately, the original program by S. Belyaev only accepts one LS for processing.
Therefore, I test one LS

0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
5 6 1 2 9 0 7 8 3 4
7 0 5 6 8 1 3 4 9 2
6 4 9 1 2 7 8 0 5 3
9 5 6 8 7 2 1 3 4 0
2 3 4 9 1 8 0 5 6 7
4 9 8 7 6 3 2 1 0 5
8 7 3 5 0 9 4 6 2 1
3 8 7 0 5 4 9 2 1 6

This is the protocol of the program by S. Belyaev

Name:a.txt
max=500
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
5 6 1 2 9 0 7 8 3 4
7 0 5 6 8 1 3 4 9 2
6 4 9 1 2 7 8 0 5 3
9 5 6 8 7 2 1 3 4 0
2 3 4 9 1 8 0 5 6 7
4 9 8 7 6 3 2 1 0 5
8 7 3 5 0 9 4 6 2 1
3 8 7 0 5 4 9 2 1 6
144 134 138 162 142 142 162 138 134 144 1440
100 39 244
200 87 194
300 126 217
Число найденных квадратов=336

The program worked a little more than 3 minutes.

This is the protocol of the program by Harry White

elapsed time 0:00:05

Total LS: 1, found: 336, min: 336, max: 336, avg: 336.00

Press a key to close the console

The program worked for 5 seconds.

For a given LS, 336 orthogonal LSs were found.

The processing time, of course, depends on LS.

---

https://yadi.sk/i/S417t0IpwnP6r

I'll show you another test.

The original squares are 500 DLS. All these DLS have orthogonal DLS and LS.

First, the program by Belyshev ortogon(u) works.
This program finds only orthogonal DLSs.
The program operation protocol

Проверка ДЛК10 на марьяжность (ОДЛК)

Введено ДЛК:  500
Найдено ОДЛК: 500
Время работы: 1.747 сек

Here 576 orthogonal DLSs are found.
Note the execution time of the program: 1.747 sec.

Now we look at these DLS as LS.
The program by Harry White is working.

elapsed time 0:03:24

Total LS: 500, found: 2522, min: 1, max: 256, avg: 5.04

Running time 3 min. 24 sec.
2522 orthogonal LSs are found here, and 576 DLSs are included.

It is clear that the search for orthogonal DLS requires less time.
However, the time difference is too great.
Hence I draw a conclusion: there is a reserve for the optimization of the Harry White program.
Perhaps this is an erroneous conclusion.

PS. Belyshev published the program ortogon(u) for general use.
Look, for example, here
http://forum.boinc.ru/default.aspx?g=posts&m=89712#post89712

The source code of the program is available.

---

https://yadi.sk/i/S417t0IpwnP6r

Is there going to be a new app for this project? Or an app to try with app_info?

Is there going to be a new app for this project? Or an app to try with app_info?

Not yet planned.

But if you are ready to help us ... :)

---

https://yadi.sk/i/S417t0IpwnP6r

I want to note that the excellent optimization of this program was made by the participant of the project team Harry White.
Optimization of Harry gave an acceleration of about 10 times.

You can download the version of the program Harry White from the following link
http://budshaw.ca/temp/lat02nmC.zip

The source code of the program is available.

But I think that there are still reserves for program optimization.

The link to that source code from Harry White is not working anymore. Can you please post the file somewhere for me to download?

The link to that source code from Harry White is not working anymore. Can you please post the file somewhere for me to download?

New link
https://cloud.mail.ru/public/7NaG/nG5nBcjkz

Thank you.

Please clarify the goals.
Should the program search for orthogonal diagonal mates or just orthogonal mates?

On my machine the best time is about 1050 DLS per second checked for their orthogonal diagonal mates. This high speed is archived thanks to Knuth's dancing links (DLX) algorithm in the ortogon program.
Quick modification of the program to search for all mates runs at 5 LS per second while still using DLX.
For DLS the time is dominated by search for transversals (85%).
For LS the time is dominated by selecting disjoint transversals (91%), because there is about 8-9 times more general transversals than diagonal transversals.
Just for curiosity, family_mar runs at 30 DLS per second (or almost 9000 daughter dls per second).

Please clarify the goals.
Should the program search for orthogonal diagonal mates or just orthogonal mates?

It is required to find all orthogonal LS to given LS or DLS.

Above are the tests that indicate the execution time.

The new version of the program should work in Windows-64bit so that I can check it.

Turns out that my simple change to DLX transversal search runs about as fast (455ls/1min+18s) as the non-DLX program by Harry White (455ls/1min+50s). Perhaps combining the White's transversal enumeration with DLX disjoint set search can offer a bit of speedup?
But this thing I do not understand. The exe fine (lat02mnC) is about two times faster than the source code recompiled! All optimizations turned on, yet it's still slower.