Nice problem. The only linear solution that works is $P(x)=x$, so from now and on assume $\deg P \geq 2$. We divide into two cases: If $P(0)\neq 0$ Take $x=0$, we have that $$P(0)=(-1)^n P(0)P(1)\dots P(n-1) \implies P(1)P(2)\dots P(n-1)=(-1)^{n+1}$$ , which implies that all roots of $P$ except $P(0)$ are $\pm 1$. If one of the roots is $1$ then $P(1)=0$ by taking $x=1$, which is a contradiction, hence all roots are $-1$, so we have that $P(x)=(x+1)^{n-1}(x-P(0))$, then by taking $x=1$ we have that $-1=P(1)=2^{n-1}(1-P(0))$ which is a clear contradiction since $2$ does not divide $1$. If $P(0)=0$ we have that $P(x)=x(x-P(1))(x-P(2))\dots (x-P(n-1))$, by taking $x=1$ we get $$\begin{align} (1-P(1))(1-P(2))\dots (1-P(n-1))=P(1) \end{align}$$ which is not true if $1-P(1)$ has a prime divisor because $\gcd(P(1),1-P(1))=1$. So, we have to check when $P(1)=0$ or $P(1)=2$, in the first case we have $P(k)=1$ for some $2\leq k \leq n-1$, then we take $x=k$ in the polynomial we have that $1=k^2(k-1)(k-P(2))\dots (k-P(n-1))$ which is a contradiction. If $P(1)=2$ we have that $(1-P(2))\dots (1-P(n-1))=-2$, since $1$ can't be root of this polynomial, we get that $P(k)=3$ for some $k$ and $P(i)=0$ for all others, for $n\geq 3$ we get that $P(x)=x^{n-2}(x-2)(x-3)$ which clearly doesn't satisfy the conditions, and hence no solutions exist except the identity.

It's $n\geq 1$, so $P(x)=x$ is a solution.

Observe that if $n\leq 2$ then the only polynomial that works is $P(x)=x.$ From now on, assume that $n=\deg P\geq 3.$ For the sake of brevity, let $r_i:=P(i)\in\mathbb{Z}$ for all $0\leq i\leq n-1.$ It follows that $P(x)=(x-r_0)\cdots(x-r_{n-1}).$ By plugging in $x=0$ in the latter we get that $$r_0=P(0)=\prod_{i=0}^{n-1}(0-r_i)=r_0\cdot (-1)^n\cdot \prod_{i=1}^{n-1} r_i.$$ Two cases arise, the first of which is $r_0\neq 0.$ It follows from the latter that $r_1,\ldots,r_{n-1}\in\{1,-1\}$ and furthermore, for some $k\in\mathbb{N},$ precisely $n-2k$ of the $r_i$ are equal to $-1$ and $2k-1$ are equal to $1.$ In other words, $P(x)$ rewrites as $(x-r_0)(x-1)^{2k-1}(x+1)^{n-2k}.$ Since $P(0)=r_0\neq 0,$ then $0$ is not a root of $P.$ However, $P(1)=r_1$ is a root of $P$ by the problems's condition and since $(x-1)^{2k-1}\neq(x-1)^0$ divides $P(x)$ it follows that $r_1=0,$ contradiction! Now, assume that $r_0=0.$ By plugging in $x=k$ $($for $1\leq k\leq n-1)$ in our polynomial we get that $$r_k=P(k)=\prod_{i=0}^{n-1}(k-r_i)=k (k-r_k)\cdot\prod_{i=1}^{k-1} (k-r_i)\prod_{i=k+1}^{n-1} (k-r_i).$$ It follows that $r_k=0$ or, if not, $k(k-r_k)\neq 0$ divides $r_k,$ which cannot happen unless $k=1$ or $2$ in which case $r_k=2$ and $r_k=4$ respectively. Therefore, our polynomial looks like $P(x)=x^{n-2}(x-r_1)(x-r_2)$ and $r_1\in\{0,2\}$ and $r_2\in\{0,4\}.$ These polynomials can easily be checked to not work, so the only answer is $P(x)=x.$

Different finish: $P(x)=x(x-P(1))(x-P(2))\dots (x-P(n-1)) \implies P(i)=0$ or $i(i-P(i))|P(i) \implies P(i)$ is even which implies contradiction because $(1-P(1))(1-P(2))\dots (1-P(n-1))=P(1)$.

XbenX wrote: If $P(1)=2$ we have that $(1-P(2))\dots (1-P(n-1))=-2$, since $1$ can't be root of this polynomial, we get that $P(k)=3$ for some $k$ and $P(i)=0$ for all others We have $1-P(k) | -2 \rightarrow P(k)=1$ or $P(k)=3$. (Also, what if $P(i)=1$ and $P(t)=2$ for some $i,t$?) We should consider the previous cases separately. For case 1: $P(k)=-1 \rightarrow -1=k(k+1)(k-2)(1-P(2))...(1-P(n-1)) \rightarrow k | -1$ and since $k>0$ we have $k=1$, but then $k+1 = 2 | -1$, contradiction. For case 2: $P(k)=3 \rightarrow 3=k(k-3)(k-2)(1-P(2))...(1-P(n-1)) \rightarrow k | 3$ and since $k>0$ we have $k=1$ or $k=3$, and we end up in a contradiction similarly.

Solution from Twitch Solves ISL: The answer is $P(x) = x$ only. For $n = 1$ it's easy to check that $P(x) = x$ is the only solution. We prove there are no others. Claim: If $n > 1$, any potential solution would need to have $P(0)=0$. Proof. If not, plug in $x=0$ and cancel $P(0)$ to get $$1 = (-1)^n P(1) P(2) \dots P(n-1).$$ So we'd need to have $P(k) = \pm1$ for $k=1,\dots,n-1$. However, $P(1) \neq 0$, so actually $P(k) = -1$ for $k=1,\dots,n-1$. In other words $P(x) = x(x+1)^{n-1}$, which doesn't work for $n \ge 2$. $\blacksquare$ We manually bash $n=2$ now: if $P(x) = x^2 + bx$ then we'd need $P(x) = x^2 + bx = (x-0)(x-(1+b))$, which is impossible. Now assume $n \ge 3$. Claim: For $k = 3, 4, \dots, n-1$, any potential solution would have $P(k) = 0$. Proof. Note that by plugging in $k$, we get $$P(k) = k \cdot (k-P(k)) \cdot T_k$$ for some integer $T_k$ (namely $T_k = \prod_{\substack{1 \le i \le n-1 \\ i \neq k}} (k-P(i))$, but we don't need the actual value). This rearranges to $$(1+kT_k) P(k) = k^2T_k.$$ However, $1 + kT_k$ shares no factors with $k^2 T_k$. So this can only occur if $1 + kT_k \in \{-1,1\}$ or $T_k = 0$. For $k \ge 3$, we extract $P(k) = 0$. $\blacksquare$ Now, we are left with $P(x) = x(x-P(1))(x-P(2)) x^{n-3}$. So plug in $x=1$ and $x=2$: $$\begin{align*} P(1) &= (1-P(1)) (1-P(2)) \\ P(2) &= 2(2-P(1)) (2-P(2)) \cdot 2^{n-3}. \end{align*}$$ Solve to get $P(1) = \frac{2(2^n-2)}{2^n-8}$ and $P(2) = \frac{3 \cdot 2^n}{2^n+4}$. This means $n \neq 3$, and for $n > 3$ we have $2^n+4 \nmid 3 \cdot 2^n$ (since $2^n + 4 \nmid -12$), so there are no other solutions.

Looks like P(P(x))=0??? Hint please