A friend of mine is creating a tabletop roleplaying game and asked for my help with a particular problem. I wrote a quick and dirty solution, but am now intrigued by what math would underlie a more elegant solution. I sketch the problem in game terms, then present a purely mathematical representation of the problem to find.
Your character has 32 skills that they can put skill points into. When you create your character, you choose from four empires and from five religions for them to be members of. Each gives you some bonus points to certain skills.
An empire boosts 3 skills by 1 point, 3 skills by 2 points, 2 skills by 3 points, and 2 skills by 4 points.
Similarly, a religion boosts 3 skills by 1 point, 2 skills by 2 points, 2 skills by 3 points, and 1 skill by 4 points.
Empires and religions should be such that the player cannot choose a pair that boosts any skill more than 5 points total. So if an empire boosts skill $S_8$ by 4 points, then a religion cannot boost that skill by more than 1 point. The following figure shows an example empire $E_1$ and religion $R_1$ which are compatible, i.e. they don't boost any skill $\ge 5$.
For my friend I wrote a Python program that generated a random set of 4 empires and 5 religions and checked if each empire—religion pair was compatible. If it wasn't, I threw it away and generated another. But there are 1.6 trillion possible empires and 17 billion possible religions. My Python program generated about a million potential solutions before it found an actual one, which took about a minute. I'd like to generate only actual solutions, possibly by enumerating them.
Definition A skill graph is a weighted simple tripartite graph $G = (V, E, w)$ with V partitioned into $M, N, R$, and edges $E = E_1 \cup E_2$, where $E_1 \in M \times N$ and $E_2 \in N \times R$. There are no edges in $M \times R$. The weighting function is $w$ and the shortest path between any two nodes is $d_\max$.
For given values of $m, n, r, w$, and $d_\max$, find all possible skill graphs.