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]*