I think in your description you made one typo:

For example, if N=5, the puzzle has 25 columns, ...

.. I think should have said "if sqrt(N)=5".

To approach this, first off I don't see any reason to choose random numbers: for a 36x36 square, there are at most 36 numbers to consider, so it seems strange to pick 10,000 random numbers rather than just try each of the 36 in turn.

Second, the numbers have no intrinsic meaning, they are just labels - you could colour the squares using 36 different colours, and you'd still be solving the same problem. That implies in particular that given any solution you could swap, say, all the 1s and 2s around and have a new solution - it is just a different way of labelling the 36 colours using numbers. Given that, you might as well choose a fixed labelling by pre-filling the first row with the numbers in order.

Third, there is a very easy way to construct a magic NxN square for any odd N, and I suspect a small tweak to that construction would also allow you to construct a solution for this problem for odd N. I've blanked it out below in case you don't want to know.

  x......                     1234567
  ..x....                     6712345
  ....x..                     4567123
  ......x  giving the square  2345671
  .x.....                     7123456
  ...x...                     5671234
  .....x.                     3456712
[download]

Fourth, you may be able to get substantial speedups by dealing with bit vectors rather than arrays; however, I'd suggest posting your code here for more specific advice.

Hugo