Sorting dominoes

Yu-Xi Lim yuxi at ece.gatech.edu
Mon Nov 14 04:35:11 CET 2005

```DaveM wrote:
> Essentially, I'm trying to sort 12 dominoes. Each domino has two different
> numbers and there are two of every number. Identical dominoes are possible,
> but doubles are not.
>
> The problem is to place the dominoes in a line, side to side, so that two
> columns (or rows, depending how you orientate them) are formed, with each
> number appearing once in each column(row).
>
> I thought this would be the easy part of the program I'm writing, but so far
> some initial states have defeated every attempt I've made, short of
> re-shuffling the dominoes after an arbitrary number of attempts.
>
> I'm sure I'll work out an effective algorithm eventually, but I suspect I'm
> re-inventing the wheel, so any hints on the best way to tackle this would be
> appreciated!
>
> DaveM

Assuming your dominoes are expressed as a list of tuples, e.g. [ (1, 2),
(3, 2), (3, 1) ].

The pseudo-code would probably be as follows:

1) create a corresponding list of dominoes with each domino reversed
2) concatenate your original list of dominoes with the list of flipped
dominoes
3) sort the new concatenated list
4) take every other element in the sorted list, e.g. using [::2]

I hadn't actually thought about it enough to verify if it works all the
time.

```