We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in the matrix.
We want to count paths that start in some cell, then moving in one of the four directions (up, down, left, right) visit all $21$ number exactly once.
It is impossible to move on cells marked as $-1$.
For example:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, -1, 21
-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, -1, -1, -1, -1, -1, -1, 18, 19, 20
We can start in the upper-left cell, move right until 17 then down, right again, and up on the end.
The second path is the same as the first path but reversed (starting from 21).
My idea is to use dynamic programming with three states $i, j$, coordinates of the current point, and bitmask of the visited cells. However this is pretty slow for numbers up to 21. Is there any way to speed up this calculation.
Link from the task that appeared on the contest: mendo.club/Task.do?id=647