Given a board of NxN, distributed with tiles labeled 2 to N^2 - 1 (inclusive)

Ehm, no. That would be 0 to n²-1 ( and the second sample tests has two threes and no two ).

Did you mix this up with the minimum value for N ?