At first glance I'd say for any size one can at least create a trivial puzzle with this pattern:
Code:
123456
234561
345612
456123
561234
612345
And you only need the horizontal hints to make this unique. I guess that gives some room to create more interesting puzzles when also introducing the vertical hints, but I haven't tried it.