Putnam 1986 A4

A transversal of an $n\times n$ matrix $A$ consists of $n$ entries of $A$, no two in the same row or column. Let $f(n)$ be the number of $n \times n$ matrices $A$ satisfying the following two conditions:

(a) Each entry $\alpha_{i,j}$ of $A$ is in the set $\{-1,0,1\}$.

(b) The sum of the $n$ entries of a transversal is the same for all transversals of $A$.

An example of such a matrix $A$ is $$A = \left( \begin{array}{ccc} -1 & 0 & -1 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{array} \right).$$ Determine with proof a formula for $f(n)$ of the form $$f(n) = a_1 b_1^n + a_2 b_2^n + a_3 b_3^n + a_4,$$ where the $a_i$'s and $b_i$'s are rational numbers.