It seems rather surprising that any given polynomial p(x) with nonnegative integer coefficients can be determined by just the two values p(1) and p(a), where a is any integer greater than p(1). This result has become known as the "perplexing polynomial puzzle." Here, we address the natural question of what might be required to determine a polynomial with integer coefficients, if the condition that the coefficients be nonnegative is removed.