The problem can be slightly generalized as follows: given a set $I\subseteq\{1,\dots,n\}$ and a set $S$ of lists of $n$-tuples, find a permutation $\sigma:\{1,\dots,|I|\}\to I$ such that each $l\in S$ is sorted according to the lexicographical preorder that compares the $\sigma(1)^\text{th}$ component, and then the $\sigma(2)^\text{th}$ component, ..., and finally the $\sigma(|I|)^\text{th}$. I'll write $<_\sigma$ for this lexicographical order.
This new problem is easily solvable by recursion: If $I=\emptyset$, there is nothing to do. Otherwise, find some $i_0\in I$ such that in each $l\in S$, the $i_0^\text{th}$ component are increasing (and if no such $i_0$ exist, return an error). Define $I':=I\setminus\{i_0\}$ and $S'$ the set of lists you get by splitting each list every time the $i_0^\text{th}$ component changes. A recursive call with $I'$ and $S'$ gives you a bijection $\sigma':\{1,\dots,|I|-1\}\to I'$ and you can then simply return $\sigma$ defined by $\sigma(1)=i_0$ and $\sigma(i+1)=\sigma'(i)$.
This algorithm runs in $O(|I|^2 |S|)$ (where $|I|$ is the cardinal of $I$, and $|S|=\sum\limits_{l\in S}\operatorname{length}(l)$). In your case and with your notations, that would be $O(n^2N)$.
I think that a slight variation of this algorithm runs in $O(|I||S|+|I|^2)$. It is described at the end of this answers. The proofs concern the $O(|I|^2 |S|)$ version but should be (relatively) easy to adapt to the faster version.
Correctness
The invariant is that if the algorithm returns a permutation $\sigma$, then all the lists in $S$ are sorted according to $<_\sigma$.
The proof is by induction on $I$. The base case is trivial because all lists are sorted according to the neutral element for the lexicographical product: equality.
In the inductive case, take any $l\in S$ we know that the sublists $l_1,\dots,l_r$ that resulted from splitting $l$ at the points where the $i_0^\text{th}$ component changed (i.e. $l=l_1@\dots@l_r$ where $@$ is concatenation, for each $k\in\{1,\dots,r\}$ all elements of $l_k$ have the same $i_0^\text{th}$ component, and for any $k\in\{1,\dots,r-1\}$ $(l_k.last)[i_0]\not=(l_{k+1}.first)[i_0]$. Since we chose $i_0$ such that $l$ (and therefore $l_k$ for all $k\in\{1,\dots,r\}$) is sorted with respect to $<_{i_0}$, this induces that (A) $a<_{i_0}b$ iff $a\in l_k$ and $b\in l_{k'}$ with $k<k'$. By the induction hypothesis, (B) each $l_k$ is sorted with respect to $<_{\sigma'}$.
Let $a,b\in l$ such that $a$ appears before $b$ in $l$.
If $a$ and $b$ appear in the same $l_k$, by (A), $a~_{i_0}b$ (i.e. $a\le_{i_0}b$ and $b\le_{i_0}a$) and $a$ appears before $b$ in $l_k$ so that by (B) $a<_{\sigma'}b$. We therefore have $a(<_{i_0}\times_\text{lex}<_{\sigma'})b$.
If $a$ appears in $l_k$ and $b$ appears in $l_{k'}$ with $k<k'$, then by (A), $a<_{i_0}b$ and we therefore have $a(<_{i_0}\times_\text{lex}<_{\sigma'})b$.
We are done because $(<_{i_0}\times_\text{lex}<_{\sigma'})={<_\sigma}$.
Completeness
The invariant is that if every $l\in S$ is sorted according to some $<_{\tilde\sigma}$ then the algorithm will return $\sigma$ such that for any $l\in S$ and $a,b\in l$, $a<_\sigma b$ iff $a<_{\tilde\sigma}b$. This implies that a list in $S$ being sorted with respect to $<_\sigma$ is equivalent it being sorted with respect to $<_{\tilde\sigma}$. We prove this invariant by induction in $I$. The base case is trivial.
In the inductive case, suppose that $l\in S$ is sorted according to some $<_{\tilde\sigma}$. Defined $\tilde\sigma':\{1,\dots,|I'|\}\to I'$ by $\tilde\sigma'(i)=\tilde\sigma(i)$ if $i<i_0$ and $\tilde\sigma'(i)=\tilde\sigma(i-1)$ if $i>i_0$. Since each $l_k\in S'$ is sorted with respect to $\tilde\sigma$, it is also sorted with respect to $\tilde\sigma'$. By the induction hypothesis, we therefore have that for all $a,b\in l_k$, $a<_{\tilde\sigma'}b$ iff $a<_{\sigma'}b$.
Let $a,b \in l$.
If $a,b\in l_k$, $a<_{\tilde\sigma} b$ iff $a<_{\tilde\sigma'}b$ iff $a<_{\sigma'}b$ iff $a<_{\sigma}$.
If $a\in l_k$ and $b\in l_{k'}$ with $k<k'$, by (A), $a<_{i_0} b$ and we therefore have $a<_{\sigma}b$. Since $l$ is sorted with respect to $<_{\tilde\sigma}$, $a<_{\tilde\sigma}b$. So we indeed have $a<_{\tilde\sigma}b$ iff $a<_{\sigma}b$ (because both are true).
We can boost it a bit by keeping keeping $S$ as a list (such that $L:=\operatorname{flatten}(S)$ is an invariant) instead of a set. You also keep a list $J$ of integers such that $\forall k\in\{1,\dots,|I|\}$, the sublist $L[1\dots J[k]]$ is sorted according to $<_k$. Then, to test a candidate $i_0$, you only check that $L[J[i_0]\dots |L|]$ is sorted with respect to $<_{i_0}$ (where you would previously test that $L[1\dots |L|]$ is), and if it fails at some point, you update $J[i_0]$ to the greatest $j$ such that $L[1\dots j]$ is sorted according to $<_{i_0}$. The number of comparisons is then bounded by $O(|I||S|+|I|^2)$ because:
You only get a positive answer for a test once (because then, you remember it was positive with $J$ and never test it again) which amounts for $O(|I||S|)$ because $\sum\limits_{1\le k \le |J|}J[k]$ starts at $0$, increases by one after every positive test (if we update it after every comparison instead of just after a comparison with a negative answer), and is bounded by $\sum\limits_{1\le k \le |J|}|S|=|J||S|=|I||S|$.
There are at most $O(|I|^2)$ negative answers, because $|I|$ strictly decreases at each iteration of the outer loop, and in the worst case, the right $i_0$ is the last you try.
You could probably further optimize it by trying all possible $i_0$ in parallel, and picking one as soon as it's the only one left (instead of checking that the rest of the list is indeed sorted with respect to that index).
