Packing problem with many twists and constraints

Question

I'm a novice programmer. I came up with a problem and now I'm obsessed with it. My knowledge is limited, so I can't build up a solution from the ground up. I tried to search for similar problems to adapt their solutions to my case but didn't find anything more or less complete. Also, I'm looking for advice from which end I should approach my problem? How to divide it into smaller problems maybe? I hope someone will find this problem interesting.

The problem is the following:

I have a set of 33 rectangles (tiles) of various sizes (2 of 1x2, 9 of 2x2, 11 of 2x3, 3 of 2x4, 5 of 3x3, 1 of 3x4, 1 of 4x4, and 1 of 2x9). I have a 15x15 board with 3 fixed holes in it (see picture). I need to find the best tiling possible with my set of rectangles while following all rules.

Here is Python dictionary with all tiles and their height, width:

dict = {'A': (2, 4), 'B': (2, 2), 'C': (2, 3), 'D': (2, 3), 'E': (2, 2), 'F': (2, 2), 'G': (2, 2), 'H': (2, 2), 'I': (2, 3), 'J': (2, 2), 'K': (3, 3), 'L': (3, 3), 'M': (3, 4), 'N': (3, 3), 'O': (2, 3), 'P': (2, 3), 'Q': (2, 3), 'R': (2, 3), 'S': (3, 3), 'T': (2, 4), 'U': (2, 3), 'V': (2, 3), 'W': (1, 2), 'X': (4, 4), 'Y': (2, 2), 'Z': (1, 2), 'AA': (2, 3), 'AB': (3, 3), 'AC': (2, 4), 'AD': (2, 9), 'AE': (2, 2), 'AF': (2, 2), 'AG': (2, 3) }

There are several rules/constraints:

1. Most important. Each tile has good/bad/neutral (or 1/-1/0) relations with each other tile from the set. These relations are represented with the following weighted adjacency matrix:

[[ 0,-1, 1, 0,-1, 0, 1, 0,-1,-1, 0, 0, 1, 0,-1, 0,-1, 1, 1,-1,-1, 1, 1,-1, 1,-1, 1,-1, 0,-1, 1,-1,-1], [-1, 0, 1,-1, 0, 0, 1, 0, 1, 0,-1,-1, 1, 1,-1, 0, 0, 1, 1, 0,-1, 0, 0, 1,-1,-1, 0, 0,-1, 1,-1, 0,-1], [ 1, 1, 0, 1, 0, 1, 0, 0, 1,-1,-1,-1, 0, 1,-1,-1, 0,-1, 1,-1, 1, 0, 1,-1,-1,-1, 0, 1, 0, 1, 1, 0,-1], [ 0,-1, 1, 0,-1, 0,-1, 0, 1, 0, 1, 1, 1, 1, 1,-1, 0, 1, 1,-1, 0, 0, 1, 1,-1,-1,-1, 1, 1,-1,-1,-1,-1], [-1, 0, 0,-1, 0, 0,-1, 0, 1,-1,-1,-1, 0, 1,-1, 0, 0,-1, 1, 1, 1,-1, 1,-1, 1, 1,-1,-1, 1, 0,-1, 1,-1], [ 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1,-1, 1,-1, 0,-1, 0, 0, 0, 1, 0, 1, 0,-1, 1,-1,-1, 0, 0, 0, 0, 0], [ 1, 1, 0,-1,-1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0,-1,-1,-1, 0, 1,-1,-1, 1,-1, 0, 1,-1, 1, 1, 1, 0,-1, 1], [ 0, 0, 0, 0, 0, 1, 0, 0,-1, 0, 1, 0,-1,-1,-1,-1, 0, 0, 1,-1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1], [-1, 1, 1, 1, 1, 0, 0,-1, 0, 0, 0,-1, 0, 1,-1,-1, 1,-1, 1, 0,-1, 0, 0,-1, 0,-1,-1, 1, 0,-1,-1,-1, 0], [-1, 0,-1, 0,-1, 0, 0, 0, 0, 0, 1, 1, 0,-1, 0,-1, 1, 0, 1, 1, 1,-1, 0, 1, 1, 0, 1, 1, 0, 1,-1, 0,-1], [ 0,-1,-1, 1,-1, 1, 1, 1, 0, 1, 0, 1, 1, 1,-1, 1, 1,-1, 0, 0,-1, 0,-1, 1, 1, 1, 1,-1, 0,-1, 0, 1,-1], [ 0,-1,-1, 1,-1, 1, 1, 0,-1, 1, 1, 0,-1, 0,-1, 0,-1, 0,-1, 1, 0, 0, 0, 0, 1, 0,-1,-1, 0, 0, 1,-1,-1], [ 1, 1, 0, 1, 0,-1, 0,-1, 0, 0, 1,-1, 0, 0, 1, 1, 0,-1, 0, 0, 0, 0, 1, 1,-1, 1, 1, 0,-1, 0, 1, 0,-1], [ 0, 1, 1, 1, 1, 1, 1,-1, 1,-1, 1, 0, 0, 0, 1, 0,-1, 1, 1, 0, 0, 0,-1, 0, 1,-1, 1,-1, 1, 0,-1, 0,-1], [-1,-1,-1, 1,-1,-1, 0,-1,-1, 0,-1,-1, 1, 1, 0, 0,-1,-1, 0, 0,-1, 1, 0,-1, 1,-1,-1, 0,-1, 1, 1, 0, 0], [ 0, 0,-1,-1, 0, 0,-1,-1,-1,-1, 1, 0, 1, 0, 0, 0, 0,-1,-1,-1,-1, 0,-1,-1,-1, 0, 0, 0, 1, 1, 1, 1, 1], [-1, 0, 0, 0, 0,-1,-1, 0, 1, 1, 1,-1, 0,-1,-1, 0, 0, 1, 1,-1, 0,-1,-1, 0, 0,-1, 1,-1, 1, 0, 1, 0, 1], [ 1, 1,-1, 1,-1, 0,-1, 0,-1, 0,-1, 0,-1, 1,-1,-1, 1, 0, 1, 0,-1, 1, 0, 1, 0, 1,-1, 1, 1,-1, 1,-1, 0], [ 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0,-1, 0, 1, 0,-1, 1, 1, 0,-1, 1, 0, 0,-1, 0, 0,-1, 1,-1,-1, 0, 1, 0], [-1, 0,-1,-1, 1, 0, 1,-1, 0, 1, 0, 1, 0, 0, 0,-1,-1, 0,-1, 0, 0, 1, 1, 0,-1,-1, 1, 0, 0,-1,-1,-1, 1], [-1,-1, 1, 0, 1, 1,-1, 1,-1, 1,-1, 0, 0, 0,-1,-1, 0,-1, 1, 0, 0,-1,-1, 1,-1,-1, 0,-1, 0, 0, 0, 1, 0], [ 1, 0, 0, 0,-1, 0,-1, 1, 0,-1, 0, 0, 0, 0, 1, 0,-1, 1, 0, 1,-1, 0,-1, 0, 1, 0,-1, 1,-1,-1, 1, 0,-1], [ 1, 0, 1, 1, 1, 1, 1, 1, 0, 0,-1, 0, 1,-1, 0,-1,-1, 0, 0, 1,-1,-1, 0, 0, 1, 1, 1, 0, 0,-1,-1, 1,-1], [-1, 1,-1, 1,-1, 0,-1, 0,-1, 1, 1, 0, 1, 0,-1,-1, 0, 1,-1, 0, 1, 0, 0, 0,-1, 1, 1, 1,-1, 1, 0, 1, 0], [ 1,-1,-1,-1, 1,-1, 0, 0, 0, 1, 1, 1,-1, 1, 1,-1, 0, 0, 0,-1,-1, 1, 1,-1, 0, 0,-1,-1, 0,-1, 0, 0,-1], [-1,-1,-1,-1, 1, 1, 1, 1,-1, 0, 1, 0, 1,-1,-1, 0,-1, 1, 0,-1,-1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1,-1,-1], [ 1, 0, 0,-1,-1,-1,-1, 1,-1, 1, 1,-1, 1, 1,-1, 0, 1,-1,-1, 1, 0,-1, 1, 1,-1, 1, 0, 0,-1, 1, 0, 1,-1], [-1, 0, 1, 1,-1,-1, 1, 1, 1, 1,-1,-1, 0,-1, 0, 0,-1, 1, 1, 0,-1, 1, 0, 1,-1, 0, 0, 0,-1, 1, 0, 1,-1], [ 0,-1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0,-1, 1,-1, 1, 1, 1,-1, 0, 0,-1, 0,-1, 0, 1,-1,-1, 0, 1,-1, 1, 0], [-1, 1, 1,-1, 0, 0, 1, 1,-1, 1,-1, 0, 0, 0, 1, 1, 0,-1,-1,-1, 0,-1,-1, 1,-1, 0, 1, 1, 1, 0,-1,-1, 1], [ 1,-1, 1,-1,-1, 0, 0, 1,-1,-1, 0, 1, 1,-1, 1, 1, 1, 1, 0,-1, 0, 1,-1, 0, 0, 1, 0, 0,-1,-1, 0,-1,-1], [-1, 0, 0,-1, 1, 0,-1, 0,-1, 0, 1,-1, 0, 0, 0, 1, 0,-1, 1,-1, 1, 0, 1, 1, 0,-1, 1, 1, 1,-1,-1, 0, 1], [-1,-1,-1,-1,-1, 0, 1, 1, 0,-1,-1,-1,-1,-1, 0, 1, 1, 0, 0, 1, 0,-1,-1, 0,-1,-1,-1,-1, 0, 1,-1, 1, 0]]

Not sure how to distinguish zero weights and zeroes on the main diagonal. Is it necessary?

For example: First tile A in good relations with C,G,L,R,S,V,W,Y,AA and AE. It is also in bad relations with B,E,I,J,O,Q,T,U,X,Z,AB,AD,FF and AG. And it is neutral to all others. This means the first tile should be adjacent to C,G,L... and not adjacent to B,E,I... Neutral neighbors are possible when there is no positive available.

The goal is to have 0 bad connections between tiles on board (if possible) and maximum possible positive ones.

2. Not all tiles will fit the board. It's fine to leave out 1-2 less important ones.
   • The total area of small rectangles is 221 cells and free space on the board is (15x15 - 3x4) = 213 cells.
3. Tiles can be rotated.

Here for example my bad manual solution (picture). I got many neutral and several bad connections in the end (bottom-right) cause didn't predict it well. There is also one free cell left.

My thoughts about this problem and its solution.

---

1. At first glance it looks like a variation of bin packing problem. But there is just one "bin", there are fixed holes in that "bin", and tiles have their "values" and restrictions.
2. Cause tiles have some values (some tiles are more "friendly" than others) it looks similar to knapsack problem. But in this case, I must care how and where to place my items into knapsack, not just throw them in.
3. There is also graph theory involved. Should I sort tiles from "best" to "worst" first? Or better to evaluate it after each placed tile? Is it needed at all? Where should I start placing my (best) tiles? In center? In corner? In most free space? In most tight space?

I'm sorry for such big text. I tried to explain as detailed as possible.