Backtracking is definitely the way to go, but you'll want to optimise it so that rather than processing things in a specific order (one latin square first, then the other), you process them in a way that narrows down wrong paths as soon as possible.
There are two types of constraints you can use:
"
There is an x in column(/row) y"
[2n^2 constraints]
"
The cell at (x,y) must be filled"
[n^2 constraints]
For each constraint, you can count how many ways to place a value that satisfies this constraint (without breaking the rules of the grid).
At each stage of the recursion, you should loop over the 3n^2 constraints, and figure out which one leads to the minimum number of possibilities. Just consider that constraint, and try each one in turn. When that constraint has 0 possibilities, you backtrack.
--
There is a clever way of implementing this called 'Dancing Links' - not only does this allow you to narrow down the best possibility at any stage, but also stores things in a single data structure that allows very quick recursion + backtracking without needing to copy data back and forward all of the time, so works many constant factors faster than a straightforward approach.
It's quite complex to code but when done correctly it solves Sudokus instantly, and should perform similarly in this case for the sizes you're describing.
http://garethrees.org/2007/06/10/zendoku-generation/#section-4 has a good write up of how it works.
[Last edited by TripleM at 12-25-2014 02:52 AM]
