Given the latest progress, I started to sketch some rough diagrams and that's the current state so far :

I'm not sure yet about the order of the lines or columns but it's getting close, it will depend on the physical dimensions. The only way to know is to make a physical prototype...

I can also reorganise the lines and columns and use my JS code to recreate the wiring diagram !

In the above sketch, I have interleaved the lines from both halves but this creates another problem: the diodes can be less densely packed. By construction, there can be at most 2 diodes on a given column and 4 lines, which reduces the density a bit and allows the diodes to be rather evenly spread. But this is broken if the order of lines is changed.

So I came up with this organisation:

(sorry if the symbols are not very consistent, it's just faster to draw and closer to the physical view)

and started wiring it, with slightly different diodes (D9K) :

The left side is driven from the top and the right side from the bottom.

It's pretty cool that one line has "disappeared" (two lines have been rewired on the right side) because there are only 13 lines instead of 14, which saves a little bit of room. Even though the number of lines has increased from 8 to 13 anyway :-D

Another little detail to notice is that all the relays are oriented in the same direction, on both sides of the PCB. This ensures that all the lines are in monotonically increasing order. It's easier to define/find which line is 0