I agree that tries are good. There is also an 8x8 solution if you wait long enough. Strangely there don't seem to be any non-square solutions up to the sizes I

I agree that tries are good. There is also an 8x8 solution if you wait long enough. Strangely there don't seem to be any non-square solutions up to the sizes I was able to check, so you might as well search only for squares, which speeds it up a lot. I'm not sure if I should post a solution but I'm happy to email it to you.