Time complexity of a backtrack algorithm
The running time of your algorithm is at most $N (N-1) (N-2) \cdots (N-K+1)$, i.e., $N!/(N-K)!$.  This is $O(N^K)$, i.e., exponential in $K$.

Justification: There are $N$ possible choices for what you put into the first blank, and in the worst case you might have to explore each.  There are $N-1$ choices for the second blank, and so on.  You can draw a tree of the choices made: the first level shows the choice of what to put in the first blank, the second level shows the choice of what to put in the second blank, and so on.  The degree of the root is $N$; the degree of the nodes at the second level is $N-1$; and so on.  The number of leaves is the product of the degrees at each level, i.e., $N (N-1) (N-2) \cdots (N-K+1)$.  In the worst case, your algorithm might have to explore every possible node in this tree (if it is not able to stop early before reaching the $K$th level and backtrack from a higher-up node).  Therefore, this is a valid upper bound for the running time of your algorithm.

If you want a tighter analysis, here is the exact worst-case running time (not an upper bound).  The number of leaves in your search tree, in the worst case, is the number of strictly increasing sequences of length $K$ over $\{1,\dots,N\}$ that start with 0.  (We can assume without loss of generality that the first blank contains a 0, as you point out, which is why we can restrict to sequences that start with a 0.)  That number is exactly $C(N-1,K-1) = (N-1)!/((K-1)!(N-K)!)$.

This is a tighter analysis, but it doesn't save us from exponential running time.  When $N\gg K$, $C(N-1,K-1)$ is still $O(N^K)$, i.e., exponential in $K$.

That said, evaluating your algorithm experimentally (by testing it on some real data sets) would probably be a better way to evaluate your algorithm than trying to derive a worst-case running time.  You might want to compare it to the performance of translating your problem into a SAT instance and using an off-the-shelf SAT solver.  Depending upon the value of $N$ and $K$, there might be other better alternatives as well.

See also the following question for a closely related problem, and for algorithms to solve it:


How to obtain the unknown values ai,bj given an unordered list of ai−bjmodN?