Latin squares generator? (Sudoku-like constraint problem)

Question

Purpose

We're designing a Latin square (sudoku-like sequence) for an experimental design that needs to follow these constraints:

• Values cannot be repeated in a row
• Values cannot be repeated in a column
• Values cannot be repeated pairwise in any two rows

Example for the first 3 constraints:

2     3    5    7    11   13
7     2    11   3    13   5
11    5    2    13   7    3
3     7    13   2    5    11
5     13   3    11   2    7
13    11   7    5    3    2

Here, we chose primes, but the values are arbitrary (as long as there are 6 distinct values). Notice that it's the same as sudoku in a 6 x 6 grid, with the additional constraint that there are no repeated pairs (a.k.a. bigrams) across rows. That is, 2 3 only appears on the first row, but in no others, and so on for every other pair.

• Values should be pair with another 6 values that fit these constraints:
  • The 2nd-set values cannot be repeated in a row
  • The 2nd-set values cannot be repeated in a column
  • When paired with the 1st-set values, the 2nd-set values cannot be repeated.

That is, we need to have another six values (again, arbitrary -- they could be "a, b, c, d, e, f") that pair with the first six. The last constraint means that if you use (2, a) anywhere, you cannot use it again.

The last 2nd-set constraint is the problem. There is no solution for n x n grids where n = 6. That's the monkey wrench in the works. We want to minimize the number of repeats, to make a "sorta-kinda" orthogonal pair of Latin squares.

Question

Have you encountered this problem before? (It'd be great if there were a tool that will generate solutions.) We only need one such example for our purposes. We've tried several different construction strategies already.

We're flirting with the idea of writing a solver for it, but we'd like to avoid doing so if something already exists.

Answer 1

Take a look: Dancing Links

In computer science, Dancing Links, also known as DLX, is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the N queens problem, and Sudoku.

Answer 2

We wrote a solver that randomly permuted solutions and took the best balanced solution available after running it overnight. It might not be the best approach, but since a perfect solution doesn't exist for the constraints, we thought it should be better than other methods of finding a "not-so-bad" solution.