Now I wonder how Nenad Petrović and Jenő Bán came up with the optimal solutions to the problems in the 60s.

Probably by just thinking about it and working to incrementally improve their answers. I'd expect plenty of people solved it before them but never published or publicized their solution. It's quite logical in many ways. For instance just thinking about the problem abstractly:

- You can only have 9 queens and they're going to want to be as centrally placed as possible with as little overlap as possible.

- The black king will need to be tucked in a corner and covered by a minimum of his pieces and nonchecking pieces of your own.

- All your other pieces, if useable, will probably end up on the edge of the board since minimizing the number of squares they block is likely to be more impactful than maximizing the number of squares they cover.

There's probably other heuristics I'm not considering, but just with those 3 you're already well on your way to the solution. So you'd lay out the pieces, and then try to find a way to do it one move better, and iterate! The concerns I'd have: pawn promotion can complicate things dramatically. Pawns can promote to 4 different pieces which would technically be 4 different moves. And a pawn can have up to 3 different paths to promote - so that's 12 possible moves tucked in a very tiny space. And then king placement - castling can add up to 2 more moves, and so compensating for that (and the corresponding rook position) adds some complexity.

Glancing at it a chess players first instinct looks to be the "solution".

Assume all pawns are queens, then maximize queen moves, work backwards from there. Couple of other "obvious" assumptions such as minimal black pieces, which means shoving the king in a corner but somehow not in check, Rooks cover the next largest amount of space so they're going in corners, bishops will be mirrored, etc.

Not to say it isn't still impressive, but I always wonder how many "sane" positions there are for solving a puzzle like this in the first place. The paper quotes some huge number and someone else says it's a smaller, but still massive, number, but when you look at the stated goal and start from some obvious starting points, start working out rules (obviously 4 queens right in the middle blocks other queens and costs space), and eliminate symmetrical positions, well you're left with a decently solvable problem. At least compared to the kind of shit that's usually brute force solved.

Edit:

This is actually a fun one to think about for a bit the more I look at it.

It quickly becomes apparent that your basically getting 7 moves out a of a rank/column MAX, so you maximize for that first.

It quickly becomes apparent that the knights L move shape is also the optimal way to start tiling your 9 queens to maximize for squares taken.

As I said before the black position obviously has to be the dead minimum, and it makes sense that'd be a king and 2 pawns due to various end game stuff (basically impossible to prevent the king from being in check otherwise while taking up as much space as possible).

Once you know you're doing that with the black king you'll want to "block" the remaining space with pieces that can't threaten it, so you shove a bishop adjacent (which can still take the pawn), and figure you're going to mirror that bishop because that's kinda how bishop's work in play/mathematically.

It's actually quite neat to see how each step sorta leads you to the next one, like one of those metal puzzles or the sudoku's with unique rules and only 1 or 2 starting numbers.

Still i'm positive if I hadn't seen this picture first I probably NEVER would've gotten this answer correct, but I do think i would've come closer than I ever expected.

Edit 2:

Ahh i do see they have at least one or two solutions that are 218 where there's only 2 black pieces. I'm somewhat surprised that's a possible legal position but so be it. Interesting that still leads to the same net realestate. Thats the one area i'd expect to gain something if you could cheat.