Sorting dominoes

[DaveM]

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

[jepler]

So if you have the dominoes (1 2), (3 2) and (3 1) you must arrange them as
1|2|3
2|3|1
? If so, then it seems to me your algorithm is this:
1. pick an arbitrary domino to be first, and an arbitrary side to be the "top"
2a. until the dominoes are exhausted, pick the other domino with the same digit
as the "bottom" of the last domino picked, and put that digit on the top.
2b. If there is no domino with the same digit, then pick an arbitrary domino as
in step 1

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDd/5hJd01MZaTXX0RAvo0AJ4kBmMDXP8hDDwmguu9aL6vvMpIUgCf eLCr
aZrw1D45Z1seuXR+ojdSmKg=
=+FyN
-----END PGP SIGNATURE-----

[Yu-Xi Lim]

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.