Topic awaiting preservation: Latin Square Trick That Blew My Mind (Page 1 of 1)

One day I started playing with sudoku. I wanted to make big ones. I found
that using orthogonal latin squares makes it wicked easy. Full of patterns,
but I also figured out how to break those patterns in the final sudoku.

There was one idea on creating larger orthos that had occurred to me way
back then. I played with it a bit, but I couldn't quite see it. The idea
being to start with smaller orthos and making them bigger a little bit
at a time. Back then, I would have been happy just to be able to make
bigger latin squares a little bit at a time.

Imagine taking a latin square of size 3x3 and turning it into a 4x4.
Imagine being able to do the same thing with corresponding ortho.
That is the basic idea.

But I couldn't see it, even for a regular latin square. It has been on
the back burner for a few years.

And then came this morning... right before my alarm went off. I was in a
half-and-half state and running all sorts of transversals through my
brain. And then I saw it! And then my alarm went off! Egads, no!

I walk to work and on the way I was running through it some more looking
for little things. Everything looked good in my brain. And I thought
about it some more while I was at work. While on break I drew a little
doodle and it does work for latin squares. What about corresponding
orthos? Well, that would have to wait a little bit after I played with
just latin squares.

I finally get home and fired up Geany. Normally graphic paper to start,
but low-tech supplies woefully low. Text editor of choice it is. For
latin squares, still looks good.

Time to play a little bit to see if I can do the same with an ortho and
keep things ortho.

First try was an epic fail. I did the Zen thing on the epic fail for a
little minute and said, "Fuck it." The next thing that I tried absolutely
floored me. Seriously, me, stunned at what I was looking at.

Okay, time for the basic idea and technique. And it starts with orthos
of size 3x3:

0 1 2   0 1 2   
 2 0 1   1 2 0
 1 2 0   2 0 1

That is as small as you can get. To get the transversals, going to use one
to mask the other:

. . 2   . . 2   
 . 0 .   . 2 .
 1 . .   2 . .
 
 0 . .   0 . .   
 . . 1   . . 0
 . 2 .   . 0 .

 . 1 .   . 1 .   
 2 . .   1 . .
 . . 0   . . 1

Let's take the first one, upper-left and operate to expand it to a 4x4.

. . 2   0 1 2 .
 . 0 .   2 0 1 .
 1 . .   1 2 0 .
         .  . . .

Can you see it? That transversal and the square that it came from but
expanded to 4x4 on the right and bottom?

So, in the first line at the top, going to shoot a 2 to the right and to
the bottom. Then change the original 2 position to a 3.

. . 2   0 1 3 2
 . 0 .   2 0 1 .
 1 . .   1 2 0 .
         . . 2 .

Please tell me you can see that because we are going to do the same thing
0 in the next line and finally 1 in the last line.

Now 0:

. . 2   0 1 3 2
 . 0 .   2 3 1 0
 1 . .   1 2 0 .
         . 0 2 .

And finally 1 in the last line:

. . 2   0 1 3 2
 . 0 .   2 3 1 0
 1 . .   3 2 0 1
         1 0 2 .

And the last thing to do is put a 3 in the bottom-right corner for this:

0 1 3 2
 2 3 1 0
 3 2 0 1
 1 0 2 3

And we now have a latin square of 4x4. Not only that, but it is a permed
version of XOR 4x4 (the fact that it is XOR is the very first thing that
I had noticed).

If you have the right transversal, you can made a bigger latin square.
Said proper transversal seems to come from the ortho. So, is it possible
make the ortho bigger as well?

My first attempt on that was epic fail. It was a pattern that I had seen
many times before that didn't suit my purpose.

And that's when I said, "Fuck it," and just randomly tried something
just to see what would pop-out the other end.

From that one square, I took the three transversals, these guys:

0 1 2   . . 2    0 . .    . 1 .
 2 0 1   . 0 .    . . 1    2 . .
 1 2 0   1 . .    . 2 .    . . 0

(Same as above but horizonetal instead of vertical.)
And I did the same right/bottom/replace thing. And something completely
amazing came out of the other end.

Check these bad boys out:

0 3 2 1  3 1 2 0   0 1 3 2
 1 2 3 0  1 3 0 2   3 2 0 1
 3 0 1 2  2 0 3 1   2 3 1 0
 2 1 0 3  0 2 1 3   1 0 2 3

Not only is each a valid latin square, but they are all mutually orthogonal
latin squares (MOLS). Pick any two and they are orthogonal.

Here is the basic relationship that holds true using 0's in the first one
as the mask:

0 . . .  3 . . .   0 . . .
 . . . 0  . . . 2   . . . 1
 . 0 . .  . 0 . .   . 3 . .
 . . 0 .  . . 1 .   . . 2 .

Seriously? WTF?! I did *not* see that coming. Somehow I had managed to
take orthos of size 3x3 and turn them into 3 MOLS of size 4x4. My mind
absolutely boogles at that.

But that is my first go and it has been less that 24 hours. I have
absolutely zero idea is this will lead anywhere or if it is a one-trick
pony. Either way I am very happy and excited about this little nugget
(even if it is a nugget with no mother lode).

Woot!

(Edited by warjournal on 03-16-2021 15:51)

Uhmmmm... something went wrong with formating in in the CODE tag.
Maybe Geany, I don't know. I am on a different machine and I haven't
really delved into idiosynchronicities when it comes to dev and
writing just yet. Me + new machine = weird little things go awry.
Difficult to say when I can get to it.

edit: and this keyboard. For the most part is fine and adjustable, but the placemeant of CapLock on the left really sucks. I can deal with PgUp, Pg Dn, and Delete being odd - but CapsLock is driving me bonkers.

(Edited by warjournal on 03-16-2021 15:48)

Okay, something wrong with formatting in code tag. I tried to fix it and
I was told that something went wrong with my input and that I needed
to go back and fix it. Herm. So, I'm just going to let it stand for the time
being.

So, humping along, I coded my LS/Ortho expansion code real nice and
parametric like. I can toss anything at it and will do my bidding.

It does everything that I described above. But as soon as I tried to go
bigger, it broke. I was hopeful that it would work, but I wasn't surprised
at all.

There is a small domain phenom that I have seen plenty of times before.
When things are small, things work just fine and are "self-solving". But
bigger sizes means more complexity and more prone to breakage. There
are some tricks that work in 4d for sizes 3 and 4 that work just fine
and are indeed self-solving. But trying to go bigger and things really
do start to break. The rules become more complex.

Not to meantion the even/2^n/odd/prime number thing. The structures for
a latin square with an even size are vastly different than a latin square
with an odd size. And then there are latin squares with the size of a
prime number. And also for 2^n (xor). *Very* different structures and
patterns.

That is why I was so surpised when I took orthos of size 3 (prime number)
and managed to make MOLS of size 4 (size 2^n). That is also why I wasn't
surprised that I couldn't get bigger (complexity).

So, I made some 5x5 "orthos" (invaled orthos) and took out the naughty
parts. For 5x5 using above technique we get this:

3 1 2 4 0  . 1 2 . .  0 00 1
4 3 0 2 1  . 3 0 . .  1 11 0
2 0 4 1 3  2 . . 1 .  2 22 3
0 4 1 3 2  0 . . 3 .  3 33 2
1 2 3 0 4  . . . . .

I don't expect anybody to be able to follow that sequence of data because
it is my data in my head. Just by looking at the first 5x5 square I know
that things aren't right. The other two squares of data just confirm it.
I can't fix it to work.

Looks like I do have a one-trick pony on my hands that only works
in a small domain. And I have absolutely zero idea if I can eventually
understand it and manipulate it to work. But I do know that this has
led to an ever so slightly deeper understanding of these things.

Maybe someday.

Cheers.

Okay, I'm starting to lose my mind. My brain has been going so
fast lately that my coding/writing can't keep up. I got home
yesterday and wrote for a good 2 hours. I got home today and
did something pretty funny. I am more than several step ahead
of where I left off. But I need to organize my thoughts better
before I can get explicit about them.

But I will tell you the funny thing that I did a few minutes
ago that I find rather entertaining - and it is something that
I don't do very often: brute force.

I mentioned that there are only 2 latin squares of size 5. I sat
down, coded the brute force in a few minutes, and got exactly
2. My brute force version of them look like this:

0 1 2 3 4
1 0 3 4 2
2 4 0 1 3
3 2 4 0 1
4 3 1 2 0

0 1 2 3 4
1 0 4 2 3
2 3 0 4 1
3 4 1 0 2
4 2 3 1 0

They don't look like the ones that I did on graph paper (which
I still can't find), but they are the real deal. Absolutely any
5x5 that you can create is merely a perm of one of those two.

So, my plan as of right now, is to finish the writing that I started
yesterday and post that in this thread. It does start to get
kind of out there a bit, but close enough.

And then maybe start a new thread about brute forcing these
things with wicked speed in the logic. Well, not perfectly efficient
with regards to code, but some understanding/insight in the
method can greatly speed things up. For example, brute forcing
those two 5x5 starts with two loops and two conditionals.

Check it out:

#!/usr/bin/env python
import itertools

s=5

for i in itertools.permutations(range(s)):
	for j in range(s):
		if i[j]==0:
			if i[0]==j:
				print(i)

And that's it for the first step.

Stay tuned and I will get to it eventually.

---------------

Alright, hang on second. I just did a quick test in the code
and it matches the probablity math in my head.

Thinking about size=8, I have the expression 7! + 7 * 6! = 10,080
possible solutions. I plugged s=8 into the above code and got
the *exact* same number of code-valided solutions.

Damn, I rock.

edit:
Brain still going crazy even while sleeping.
I was able to reduce 7!+7*6! down to just
6!=720. The general being (n-2)! possible
transversals.

(Edited by warjournal on 03-25-2021 01:29)