Given two vectors $x$ and $y$, where each element $x_i, y_i$ is from a finite field.
I have the restriction that for each of these variables only about half of the elements of this finite field are valid. Also the sets of possible values are independent of each other.
For instance:
$x_0 = \{0, 1, 4, 7, \ldots\}$, $x_1 = \{1, 2, 8, 9, \ldots\}$ etc.
I want to check if there exists a solution (resp. enumerate them) for:
$(x_o, x_1, \ldots, x_n) \cdot A = (y_0, y_1, \ldots y_n)$
where $A$ and the sets of possible elements for $x_i, y_i$ are given.
every system of equation in finite field in form of $Ax=b$ (in your case $A^Tx^T=y^T$) can be solved using Gauss-Jordan elimination in form of $x=\hat{x}+cN(A)$ ($N(A)$ is the null space of $A$).
Considering your limited number of choices, which isn't linear, it seems that the problem is NP. Still a branch and bound aproach might help you.
Choose a value for $x_0$, and solve $c_0=\hat{x_0}+cN(A)_0$, if there was a possible solution proceed with more assumptions on consecutive $x_i$'s, if not revise your most recent variable.