We were presented with this problem in a course in constraint programming where we used a library called Gecode [2] to implicitly express and effectively search the solution space in terms of variable relationships/constraints. I remember symmetry breaking being a central concept [3].
Yes, but even better there is the global constraint geost [1] which is specifically for this purpose in k-dimensions; see also [2] for a more detailed presentation.
Unfortunately, Gecode does not provide it (and you would have to express it in form of other, more lower level constraints which gets quickly complicated), and neither does Google's OR-tools which have a nice Python interface.
There is JaCoP which provides the geost global constraint and makes it available via the declarative MiniZinc problem description language so one needs not to use the Java API.
[1] https://en.wikipedia.org/wiki/Constraint_programming [2] http://www.gecode.org/ [3] https://en.wikipedia.org/wiki/Symmetry-breaking_constraints