Constraints on sets of RPG skill bonuses as a graph problem

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.

Informal description

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$.

To illustrate:

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.

Mathematical description

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.

-
Insani trebancha ka saurus? – atulgangwar Nov 12 '13 at 20:10
You used $N$ in the mathematical description twice in different ways, so it's hard to understand. – zibadawa timmy Nov 12 '13 at 21:22
Oops, fixed. Thanks. – Ian Dalton Nov 12 '13 at 21:43

I will use a little bit different notation. Let denote empire as function $E: \{1,\dots,32\} \rightarrow \mathbb{N}_0$ satisfying your constraints, such as there are only two $i,j$ that $E(i)=E(j)=4$ and so on. Generate $n$ random empires $E_1,\dots,E_n$ and now start generating religions $R: \{1,\dots,32\} \rightarrow \mathbb{N}_0$ but such that $R(i)+\max_k E_k(i) \leq 5$ for all $i$. If you generate religion satisfying this condition than you get valid set of empires and religions.
What does $k$ represent? – Ian Dalton Nov 13 '13 at 1:04
$\max_k E_k(i)$ is the maximal bonus which gives some empire to the skill $i$. $k$ is the index over you take the maximum and it goes from one to $n$. – tom Nov 13 '13 at 17:17