You see the image. It's a 4x4 grid. Come up with solution for each dot to get to one of the exists on the edge.

However here is the trick. The lines should not cross. One with the most optimized path wins.

God tier: make it 5x5 grid

Elder god tier: 8x8 grid with 16 exits on each edge

>>15392796 (OP)

Elaborate

Imagine you have a chip with the number of devices in grid that you want to power up, and you want to connect it from the edges. So you deposit wires on the chip but they are not allowed to cross as an example 

So the goal is to connect each dot with a wire on the edge without them crossing each other in the most optimal way

>>15392796 (OP)

Here

>>15392796 (OP)

The riddle must be trying to understand your english.

Heil Hitler

riddle for OP:

draw a square on paper, but one where all lines are straight

Each dot connected to one of the edge points with shortest path possible. OP didn't say it but presumably the edge has to be different for different points.

>the most optimal way

do you mean shortest mean distance, shortest total distance, or what

Can the lines be curved?

The optimal solution would not have curved lines in any case, so what does it matter?

I was just asking since 2 of the answers already had curved lines. I know the optimal solution doesn't have curved lines.



Rationale behind this solution: the shortest line from one of the center dots to an exit is sqrt(5)*u, the shortest line from one of the outer dots to an exit is 1u.

this better not be the 'think outside the box' ones where you need to do something outside the square

Wait actually there are more optimal solutions that do have curved lines. See >>15392997's.

Like this?

With an 5x5 grid that has 5 exits on each side this cannot be done. 

There would be 25 dots and 20 exits. At least 5 lines would intersect with 5 other lines, each pair in one separate exit. (Well, techincally they're line segments)

Line segments intersect even if they intersect in just 1 point, so it cannot be done unless the number of exits is greater than or equal to the number of dots.



This solution is invalid. See above.

But lines do not cross. The meet at points.

curved lines are less optimal i think

What does "cross" mean to you?

It should mean "intersect".

If 2 line segments "meet" at one point that means they intersect in that point, because that point is part of both line segments.

>>15392796 (OP)

This seems like a sort of a minimum matching problem on a bipartite graph for which there are many known algorithms. The planarity requirement might make it a bit tricky, though.

>>15392796 (OP)

just use vias in the pads

Yeah they are less optimal actually. I calculated it.

My solutions T is approximately 20.944u

The solution that used those curved lines had a T of approximately 21.301u.

It seemed more optimal at first glance but wasn't.

bump

You failed because the some of these line segments intersect.
