This problem is also really good.

This solution (that I found during the MOP test) is quite cute and nice. It's one page long and doesn't mention graphs at all (and it's better phrased without graphs). The answer is $2n-2$. An example is given for $n=4$ which generalizes easily. \[ 1 2 3 4 | 1 | 2 3 4 | 1 2 | 3 4 | 1 2 3 | 4 \]Define a maximal piece to be a piece that has $n$ squares in it. We claim that there is an optimal construction with at most one maximal piece; this implies the problem because counting the pieces needed for each row yields a lower bound of $1+2(n-1)=2n-1$ pieces, which requires $2n-2$ cuts. Suppose for contradiction that this was not true. Then take an optimal construction with the fewest amount of maximal pieces possible; by assumption there are at least two. Start with the leftmost maximal piece $A$ and repeatedly apply the following: Consider piece $B$ immediately at the right of $A$. It cannot be a maximal piece, and the piece cannot form the start of any row in the final square (as this row would be the row covered by $A$). Consider piece $C$ to the left of it in the final square, and suppose it has $n$ numbers. Take the final $n$ numbers from the right of piece $A$ and transfer them to piece $B$. Now the line formerly constructed by $A$ is formed by the left part of $A$ and $C$, and the part of line formerly constructed by $B$ and $C$ is formed solely by $B$. This does not change the number of cuts. Moreover, by minimality, since $A$ is no longer a maximal piece, $B$ must be. However, repeating this procedure eventually forces two maximal pieces to be adjacent, a contradiction.

Cute!

The answer is $2n - 1$ pieces (or $2n-2$ cuts). Since everything is taken modulo $n$, assume that the original strip contains $n$ copies of the list $(1, \dots, n)$ instead of the numbers $(1, \dots, n^2)$. Construction. First, divide the $1\times n^2$ strip into $n$ pieces, each labeled with $1, \dots, n$. We will use each of these pieces to make one row of the square. Here is an example for $n = 4$ which readily generalizes: [asy][asy] // diagram modified from MarkBcc168 picture grid; size(grid, 90); defaultpen(fontsize(12pt)); int n=4; for(int i = 0; i <= n; ++i) { draw(grid, (i, 0) -- (i, n), gray); draw(grid, (0, i) -- (n, i), gray); } for(int i = 0; i <= n-1; ++i) { draw(grid, (0, i) -- (i+1, i) -- (i+1, i+1) -- (0, i+1) -- cycle, black+linewidth(1.2)); draw(grid, (i+1, i+1) -- (i+1, i) -- (n, i) -- (n, i+1) -- cycle, black+linewidth(1.2)); } for(int i=0; i<n; ++i){ for(int j=0; j<n; ++j){ label(grid, (string)((i-j-1)%n + 1), (i+0.5, j+0.5)); } } picture strip; size(strip, 300); for (int i=0; i<(n^2); ++i){ draw(strip, (i,0)--(i,1), gray); label(strip, (string)(i%n + 1), (i+0.5, 0.5)); } draw(strip, (0,0)--(0,1)--(n^2,1)--(n^2,0)--cycle, black+linewidth(1.2)); // for n = 4 real[] t = {4, 5, 8, 10, 12, 15}; for (int i=0; i<t.length; ++i){ draw(strip, (t[i],0)--(t[i],1), black+linewidth(1.5)); } add(grid.fit(), (0,0), N); add(strip.fit(), (0,0), 10S); [/asy][/asy] For the first row of the grid, the $1\times n$ strip already works perfectly. For rows $i\ge 2$, take the $1\times n$ strip and make a cut between $i-1$ and $i$. After flipping the two pieces one obtains the desired arrangement for row $i$. Thus, we can use one piece for the first row and two pieces for every subsequent row, for a total of $2n-1$ pieces. Proof of bound. Consider the following augmented procedure. In addition to having a $1\times n^2$ strip of paper, suppose that Paul has $n$ different highlighters with colors $C_1, \dots, C_n$. First, Paul colors the left and right edges of the $1\times n^2$ strip with color $C_1$. Next, before he makes any cut, say along the line $\ell$ between $i-1$ and $i$, he uses his highlighter $C_i$ to draw a thick line over $\ell$. Then after making the cut, the color $C_i$ still shows on both freshly cut edges. He rearranges the pieces into an $n\times n$ square satisfying the condition in the problem statement. For each $i = 1, \dots, n$, Paul writes down the set of rows $R_i$ containing any edge of color $C_i$. Finally, Paul constructs a graph $G$ with vertices representing the rows of the square. For each $i = 1, \dots, n$, Paul draws a path connecting all the rows in the set $R_i$. (At step $i$, he draws $|R_i| - 1$ edges.) Let an inner edge be an edge that lies in the interior of the square; the edges on the left and right boundary of the square are outer edges. Since the final square still keeps $i-1$ adjacent to $i$ everywhere, inner edges have one well-defined color. [asy][asy] picture grid; size(grid, 130); defaultpen(fontsize(12pt)); int n=4; for(int i = 0; i <= n; ++i) { draw(grid, (i, 0) -- (i, n), gray); draw(grid, (0, i) -- (n, i), gray); } draw(grid, (0,3)--(0,4), orange+linewidth(1.2)); draw(grid, (4,3)--(4,4), orange+linewidth(1.2)); draw(grid, (3,2)--(3,3), orange+linewidth(1.2)); draw(grid, (0,2)--(0,3), lightblue+linewidth(1.2)); draw(grid, (4,2)--(4,3), lightblue+linewidth(1.2)); draw(grid, (2,0)--(2,1), lightblue+linewidth(1.2)); draw(grid, (0,1)--(0,2), red+linewidth(1.2)); draw(grid, (4,1)--(4,2), red+linewidth(1.2)); draw(grid, (3,0)--(3,1), red+linewidth(1.2)); draw(grid, (0,0)--(0,1), heavygreen+linewidth(1.2)); draw(grid, (4,0)--(4,1), heavygreen+linewidth(1.2)); for(int i = 0; i <= n; ++i) { draw(grid, (0, i) -- (n, i), black+linewidth(1.2)); } for(int i=0; i<n; ++i){ for(int j=0; j<n; ++j){ label(grid, (string)((i-j-1)%n + 1), (i+0.5, j+0.5)); } } label(grid, "$1, 2$", (6, 3.5), orange); label(grid, "$2, 4$", (6, 2.5), lightblue); label(grid, "$3, 4$", (6, 1.5), red); label(grid, "$4$", (6, 0.5), heavygreen); picture strip; size(strip, 300); for (int i=0; i<(n^2); ++i){ draw(strip, (i,0)--(i,1), gray); label(strip, (string)(i%n + 1), (i+0.5, 0.5)); } real[] o = {0, 4, 16}; for (int i=0; i<o.length; ++i){ draw(strip, (o[i],0)--(o[i],1), orange+linewidth(1.2)); } real[] b = {5, 13}; for (int i=0; i<b.length; ++i){ draw(strip, (b[i],0)--(b[i],1), lightblue+linewidth(1.2)); } real[] r = {6, 10}; for (int i=0; i<r.length; ++i){ draw(strip, (r[i],0)--(r[i],1), red+linewidth(1.2)); } real[] g = {11}; for (int i=0; i<g.length; ++i){ draw(strip, (g[i],0)--(g[i],1), heavygreen+linewidth(1.2)); } draw(strip, (0,0)--(n^2,0)^^(0,1)--(n^2,1), black+linewidth(1.2)); picture graph; size(graph, 80); pair A, B, C, D; A = dir(180); B = dir(90); C = dir(0); D = dir(270); draw(graph, A--B, orange+linewidth(1.2)); draw(graph, B--D, lightblue+linewidth(1.2)); draw(graph, C--D, red+linewidth(1.2)); dot(graph, "$1$", A, dir(A)); dot(graph, "$2$", B, dir(B)); dot(graph, "$3$", C, dir(C)); dot(graph, "$4$", D, dir(D)); picture pic; add(pic, grid.fit(), (0,0), W); add(pic, graph.fit(), (0,0), 30E); add(pic.fit(), (0,0), N); add(strip.fit(), (0,0), 10S); [/asy][/asy] Claim: There are at least $|R_i| - 1$ inner edges with color $C_i$. Proof. For each $j = 1, \dots, n$, the outer edges in row $j$ must be colored $C_j$. Hence $i\in R_i$, and if any other $j\neq i \in R_i$, there must be an inner edge colored $C_i$ in row $j$. $\blacksquare$ Claim: The graph $G$ is connected. Proof. Imagine walking from cell $1$ to cell $n^2$ along the original $1\times n^2$ strip, and tracing the path $P$ through the final location of those cells (in order) in the $n\times n$ square. Note that $P$ hits every cell in the square exactly once. The key observation is that whenever $P$ jumps from a piece $X$ in row $i$ to a piece $Y$ row $j$, the right edge of $X$ must have the same color as the left edge of $Y$. By construction, this implies that $i$ and $j$ are connected in $G$. Since $P$ hits every cell in the $n\times n$ square, it must certainly jump to every row. Hence $G$ itself must be connected. $\blacksquare$ To finish, $G$ connected implies that \[ |E(G)| = \sum_{i=1}^n (|R_i| - 1) \ge n-1, \]which by the first claim means that there are at least $n-1$ inner edges. Thus, Paul must have used at least $2n-1$ pieces. Remark: [Motivation] In the problem statement, the cells of the $1\times n^2$ strip are labeled with the numbers $1, \dots, n^2$ (although of course, only their residues modulo $n$ matter). When thinking about how the strip rearranges into the square, I think it's natural to consider the path $P$ formed by cell $1$, cell $2$, ..., cell $n^2$ in the final $n\times n$ square. Then one can ask: what kinds of jumps can happen? At this point, I noticed that $P$ can only jump to a new row using edges of the same color, and that any edge with color $C_i$ in a row $j\neq i$ must be an inner edge. Thus jumping between rows forces new inner edges, leading to the solution above.

We show that Paul requires at least $2n-1$ pieces to accomplish the task. The construction for the claimed bound is as follows: \[\left\langle \begin{matrix} 1 & 2 & \cdots & n\\ n+2 & n+3 & \cdots & 2n+1 \\ \vdots \\ n+1 & 2n+2 & \cdots & n^2-1 \\ \end{matrix} \right\rangle\] In this construction, the first $n-1$ rows contain consecutive entries, which means they require $n-1$ strips, while the last row requires $n$ strips as well. In all, we require $2n-1$ strips. Proof of Bound. Define a ``singlet" as a single strip in an $n\times n$ square. We claim that there must be at most $n-1$ singlets in our square. We construct an algorithm which reduces (or keeps same) the number of strips required. At each step, we identify a singlet with entry $k$. The square to the left of $k-1$ (say $l$) and to the right of $k+1$ (say $r$) must not be $k$. We swap $l$/$r$ and $k$. This will decrease the number of pieces or keep it constant. We keep doing this algorithm until we cannot. At this point, either all singlets have been converted to larger strips, or for every singlet with entry $k$, the square with entry $k-1$ lies on the right edge, while the square with entry $k+1$ lies on the left edge. It follows that we can have at most $n$ singlets. We claim that for every residue $\pmod n$, we have at least one singlet. Suppose for contradiction there are no singlets for some residue class, say $e \pmod n$. Then, every entry of residue $e+1\pmod n$ and $e-1\pmod n$ cannot be in a singlet as they must ``mingle" with a guy of residue $e\pmod n$. Inducting, there are no singlets in this $n\times n$ grid. It can be shown that this is never possible. Hence, there must be at least $n$ singlets in any arrangement. Since every singlet forces at least two cuts, the result follows.

We claim the answer is $2n-1$, achievable, by taking the easily generalizable construction $12345|1|2345|12|345|123|45|1234|5$. Call of strip of length $n$ an large strip and call all strips that precede or come after a large strip a bound strip. Call the remaining strips small strips. It is easy to see why all boundary strips cannot be a large strip and why all large strips have unique boundary strips. Consider a large strip in row $i$. We get that following boundary strip must go from $i, \ldots, k$. Now if there are two strips in the same row as the boundary strip, then this row must be row $k+1$. However, this means the other strip in the row is from $k+1, \ldots, i-1$. Then, the following strip cannot be a large strip. Let this strip go from $i, \ldots, j-1$. Now, if there is exactly one other strip in this row, then it must be $j, \ldots, i-1$. If we ever get a row with three strips, the average number of strips per row so far is two and repeat the argument to get the bound. If there is never a row with three strips, we can repeat the argument until we have covered all rows which gives a bound of $2n-1$.

Let a piece of length $n$ be called a maximal piece. Suppose we have a solution of pieces that can be constructed into a square, call a starting piece a piece that is at the front of a row and call an ending piece a piece that is at the end of a row. I will now prove that by making a number of moves that keep the number of pieces the same or decrease it we can obtain a configuration with 1 maximal piece. First find the starting piece for square $a_{(1,1)}$, now extend this piece so it forms a maximal piece, if it hits the end before this is possible this is a contradicition as this piece is $1\pmod n$, to make sure a square can still be formed line up the pieces which used to form the remaining pieces of the 1st row and copy the removed cuts over to these pieces, this keeps the number of pieces the same or decreases it. Now change this maximal piece to be a maximal piece with starting square $1$, this is possible as modulo $n$ no value changes. Now suppose we have another maximal piece, take the piece in front of it, this cannot be an ending piece as no two rows end on the same square modulo $n$, thus extend this piece so it becomes an ending piece and replace the removed section of the maximal piece with the pieces that went after the piece we removed, if the piece we extended is not a starting piece this reduces the number of maximal pieces by $1$, if it is a starting piece than we get a new maximal piece but moved forward in the line, by repeating this process if a new maximal piece is created every time an maximal piece will eventually be created thats adjacent to the maximal piece starting at $1$, which is a contradicition. Thus as we can force any working case to have only $1$ maximal piece we have at least $2n-1$ pieces.

It took me way too long to post this. The answer is $2n-1$. Take the numbers on the strip of paper modulo $n$. The construction comes naturally. Specifically, the first row is in itself one of the pieces, while for $2\leqslant i\leqslant n$, the $i$-th row is comprised of the pieces $[i,\ldots,n]$ and $[1,\ldots,i-1]$, in this order. It remains to show that $2n-1$ pieces are always required. In order to do this, we form a graph $G$ with vertices labelled from $1$ to $n$. To a piece starting in $a$ and ending in $b$, we associate an edge between the vertices labelled $a$ and $b+1$. Naturally, everything is taken modulo $n$. Let $H_i$ be the set of pieces of paper which, concatenated, yield the $i$-th row of the table. The set $H_i$ corresponds to a cycle $C_i$ in $G$, which contains the vertex labelled $i$. Consequently, the edges of $G$ can be split into such disjoint cycles $C_1\sqcup\cdots\sqcup C_n$. Additionally, because the pieces of paper can be concatenated to form the $1\times n^2$ original strip of paper, the graph $G$ has an Eulerian cycle. Therefore, the existence of a cycle $C_i$ passing through any vertex $v_i$ of $G$ implies connectivity. We may then consider a spanning tree $T$ of $G$. Because the edges of $G$ cannot form a cycle, $|C_i|\geqslant |C_i\cap T|+1$. Furthermore, because the cycles $C_1,\ldots,C_n$ are disjoint and they contain all the edges of $G$, it follows that \[\#\text{ edges}=\sum_{i=1}^n|C_i|\geqslant n+\sum_{i=1}^n|C_i\cap T|=n+|T|=2n-1.\]As every edge in $G$ corresponds to a piece of paper, we have proven the desired result.