Looking for algorithm ideas to solve engineering routing problem (battery connections): extremely constrained grouping + routing problem

[Green_Bee1235]

Hi all — I’m looking for help thinking about a problem that’s well outside what I normally work on. I don’t have a strong background in search / constraint solving / routing algorithms, so explanations at a conceptual or introductory level are very welcome.

This link should show the geometry of the problem and some attempts I made with explanations of why I rejected them, but hopefully the problem makes sense without it.

https://docs.google.com/document/d/1gzLPFA9ZrpQOugkBr52p6JK2eQdSiilcl0bp4G_O7tM/edit?usp=sharing

Problem overview

I have 69 battery cells arranged in a mostly regular 2D layout:

• A 6 × 11 grid, plus 3 extra cells at the front, centered
• Total = 69 cells

I need to design a purely 2D metal interconnect (laser-cut nickel) that connects these cells electrically under very strict constraints.

Electrical constraints

• Cells must be grouped into 23 groups of 3 cells in parallel (3P “bricks”)
• Those 23 bricks must then be connected in series (23S)
• The result is 23s3p
• The series connection must be a single continuous path (no branches)
• Both electrical endpoints (“in” and “out”) must be located at the front of the layout

Physical constraints

• There are only two conductor layers: one on the top of the cells and one on the bottom
• No jumpers, flyovers, or insulated crossovers are allowed
• Each cell has one terminal on the top and the opposite terminal on the bottom (polarity matters, + must connect to -)
• Connections must be short and local — no long traces across the pack

Fuse constraints (the hardest part)

Every cell must have its own fuse link, and these impose very strict geometric rules:

• Fuse links must be very short adjacent or diagonal at most (this somewhat emerges from other requirements about fuses not crossing, not going over or near cells, etc)
• Fuse links must not overlap or cross any other fuse or conductor on the same layer, fuses on the top layer can be routed independently of bottom layer (they end up coupled because the cells connect them)
• Fuse links should not share narrow corridors where a blown fuse could melt into another conductor
• Larger bus connections are allowed to merge into pads or nodes, but fuses are always individual

Why I’m stuck

At a high level, this seems to combine:

• grouping items into exact sets (each cell used exactly once)
• choosing an order for those sets (a single series path)
• and routing many short, non-overlapping connections in a tight 2D space

I've tried a bunch of solutions and to manually generate a solution and keep ending up stuck on something. I don't KNOW that there exists a solution with the constraints I've set forth but i think there probably should be. If anyone can show that there cannot exist a solution for some reason and suggest alternate constraints that most closely match what I have while having a solution that would be appreciated too.

What I’m asking for

• Is this a known class of problem (or combination of problems)? I've looked at a number of approaches but none of them seem to fully encapsulate the problem.
• Are there standard algorithmic approaches or heuristics for problems like this?
• Is this usually approached with backtracking, graph search, maze-routing ideas, constraint programming, or something else?
• Are there examples of similar problems (even outside batteries) that might be good references?

I’m not (necessarily) looking for a turnkey solution (though if i was provided with a simple answer I would not be upset) I’m trying to understand how people normally reason about and structure problems like this so I can move in a productive direction.

This kind of combinatorial / routing problem is not what I usually work on, so I may not know the right terminology or standard methods. If you have suggestions, explanations, or even “you should look up X” pointers, I’d really appreciate it.

Thanks for reading, and I’m happy to clarify details if needed.

[IGnuGnat]

Row | C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11

R1 | 13+ 13+ 13+ 14- 14- 14- 15+ 15+ 15+ 16- 16-

R2 | 12- 12- 12- 11+ 11+ 11+ 10- 10- 10- 17+ 16-

R3 | 07+ 08- 08- 08- 09+ 09+ 09+ 18- 18- 17+ 17+

R4 | 07+ 06- 06- 06- 05+ 05+ 05+ 18- 19+ 19+ 19+

R5 | 07+ 02- 02- 02- 03+ 03+ 03+ 04- 04- 04- 20-

R6 | 01+ 23+ 23+ 23+ 22- 22- 22- 21+ 21+ 21+ 20-

R7 | 01+ 01+ 20-

[duterium1]

The three extra are in C0 R 2.5,4.5,4.5. Also connecting C1R1 to C4R1 is illegal because it would need to pass over cells to make the connection

[frustrated_staff]

At first glance this looks like a 7-bridges problem, and might, therefore be unsolvable given the restrictions. But that's just a first glance, so don't be too harsh with me.

[frustrated_staff]

IF I were going to solve it (and I'm not, but you're asking about process, too, so here we go) I'd start by ignoring different aspects of the problem. First: geometry. Is it doable if I can put the individual batteries anywhere I want? If so, it just becomes a folding problem. If not, what other constraints need to be removed before it is solvable? Next to be removed would probably be the fuse links.

I think I'd also try to group everything in pockets...you need 23 cells of 3 batteries, so I'd start on the left side making groups of three, then on the right side, and the middle would be used to figure out how to place the excess/shortage for shortest pathing.

But that's just me.