Algorithm to mix colours on 7 individual pieces of toy

Question

I'm a woodworker trying to seek some math and algorithm help on the expertise here.

I'm trying to make 28 sets of Tangram for gifting relatives, like this:

^{DanielHolth + RobotE at nl:Wp [CC BY-SA 3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], from Wikimedia Commons}

The toys consists of 7 pieces of wood board that should be painted to individual colours. To make the painting easier, I think the best way is to paint them in batches of 4 sets in the same colour, then mix them.

I have labeled the pieces 1-7 to make discussion easier:

What is the most efficient way to mix the pieces so I do not get identical colour combination per set? I would like the gift to be as individual as possible and colour combination is a good way to achieve this goal.

Edit: Each set of puzzle is made of seven pieces each of a different colour.

Answer 1

I've already posted an answer that attempts to solve the problem as simply as possible, but I felt it was appropriate to provide a solution that also attempts to maximize uniqueness. Another answer already covers the basics of this, but does not account for color pairs created from identical puzzle pieces, so I've attempted to do so here.

This solver isn't the fastest, but guarantees that there will be no more than two identically colored pairs of pieces between any two sets. When ran without shuffling, there is a large bias towards certain colors taking particular pieces, so I provide an argument to shuffle the intermediate arrays to eliminate this bias, at the cost of fewer generated sets (potentially less than 28 - if so, run again). The program will spit out all sets found that satisfy the above criteria, so you can manually pick whichever 28 seems the most "random" or "uniform" to the human eye.

from itertools import combinations, permutations
from random import shuffle

def get_subsets(color_set):
    subsets = []
    for d in ({}, {'1':'5'}, {'4':'6'}, {'1':'5', '4':'6'}):
        tr = lambda s: str.translate(s, str.maketrans(d))
        subsets.extend(set(tr(y) for y in x) for x in combinations(color_set, 3))
    return subsets

def make_sets(do_random=True):
    color_sets = [set(c+str(i) for i, c in enumerate(perm)) for perm in permutations("RGBYPOW")]

    results, pairs = [], []
    while color_sets:
        results.append(color_sets[0])
        pairs.extend(get_subsets(color_sets[0]))
        color_sets = [x for x in color_sets if all(y - x for y in pairs)]
        if do_random: shuffle(color_sets)

    results = sorted(sorted(perm, key=lambda x:x[1]) for perm in results)
    print("\n".join(map(str, results)))
    print(len(results))

if __name__ == "__main__":
    make_sets()

Example output:

['B0', 'G1', 'O2', 'W3', 'P4', 'R5', 'Y6']
['B0', 'P1', 'W2', 'Y3', 'O4', 'G5', 'R6']
['B0', 'R1', 'W2', 'O3', 'G4', 'P5', 'Y6']
['B0', 'R1', 'Y2', 'P3', 'W4', 'O5', 'G6']
['B0', 'W1', 'R2', 'G3', 'O4', 'Y5', 'P6']
['G0', 'B1', 'O2', 'P3', 'R4', 'W5', 'Y6']
['G0', 'B1', 'R2', 'W3', 'Y4', 'O5', 'P6']
['G0', 'O1', 'P2', 'B3', 'W4', 'R5', 'Y6']
['G0', 'O1', 'Y2', 'R3', 'B4', 'W5', 'P6']
['G0', 'P1', 'O2', 'Y3', 'B4', 'R5', 'W6']
['G0', 'W1', 'P2', 'O3', 'R4', 'Y5', 'B6']
['O0', 'B1', 'Y2', 'W3', 'R4', 'P5', 'G6']
['O0', 'G1', 'R2', 'Y3', 'W4', 'P5', 'B6']
['O0', 'P1', 'G2', 'R3', 'Y4', 'B5', 'W6']
['O0', 'R1', 'B2', 'G3', 'P4', 'W5', 'Y6']
['P0', 'B1', 'R2', 'O3', 'W4', 'Y5', 'G6']
['P0', 'R1', 'G2', 'W3', 'B4', 'Y5', 'O6']
['P0', 'W1', 'B2', 'Y3', 'O4', 'R5', 'G6']
['P0', 'W1', 'G2', 'B3', 'Y4', 'O5', 'R6']
['R0', 'G1', 'B2', 'Y3', 'P4', 'O5', 'W6']
['R0', 'O1', 'P2', 'Y3', 'G4', 'W5', 'B6']
['R0', 'Y1', 'W2', 'P3', 'G4', 'B5', 'O6']
['W0', 'G1', 'B2', 'P3', 'R4', 'Y5', 'O6']
['W0', 'O1', 'P2', 'G3', 'Y4', 'B5', 'R6']
['W0', 'R1', 'Y2', 'G3', 'O4', 'P5', 'B6']
['W0', 'Y1', 'G2', 'O3', 'B4', 'P5', 'R6']
['W0', 'Y1', 'O2', 'R3', 'P4', 'G5', 'B6']
['Y0', 'B1', 'P2', 'R3', 'W4', 'G5', 'O6']
['Y0', 'G1', 'W2', 'O3', 'B4', 'R5', 'P6']
['Y0', 'O1', 'B2', 'G3', 'R4', 'P5', 'W6']
['Y0', 'P1', 'R2', 'B3', 'G4', 'W5', 'O6']
31

Answer 2

For fun, here's some code that attempts to minimise, without an exhaustive search, the number of sequential colour pairs that can coexist in the same position in an attempt to respond to your request for "as individual as possible." It has an element of randomness. Sometimes it can produce a triple sequence duplicate but at it's best, we get only pair duplicates. (Maybe the chance similarities recipients would find between their gifts would be part of the beauty.)

(Dillon Davis commented that it can produce identical pairs for positions 1 & 5 or 4 & 6, which appear to be prominent similar triangles in the design. I may make a change to it a little later to prioritise avoiding those duplicates.)

let cs = ['R', 'G', 'B', 'Y', 'P', 'O', 'W'];

let pairs = [];

for (let i=0; i<6; i++)
  for (let j=i+1; j<7; j++)
    pairs.push(cs[i] + cs[j], cs[j] + cs[i]);

let positionMatches = [];
const results = pairs.slice(0, 28);

// Build combinations
for (let i=0; i<5; i++){
  // Avoid repeating pairs
  // in the same position
  let set = new Set();

  for (let j=0; j<28; j++){
    const last = results[j].substr(-1);
    let found = false;

    for (let c of cs){
      const candidate = last + c;

      // Match found
      if (!set.has(candidate) && !results[j].includes(c)){
        results[j] += c;
        set.add(candidate);
        found = true;
        break;
      }
    }
    // Match not found
    // Lower the restriction
    // and insert random match
    if (!found){
      const cs_ = cs.filter(
        c => !results[j].includes(c));
      const c = cs_[
        ~~(Math.random()*cs_.length)];
      results[j] += c;
      positionMatches.push((i+2) + ':' + last + c);
    }
  }
}

console.log(results.join('\n'));

console.log('');

for (let p of positionMatches){
  const [pos, pair] = p.split(':');
  console.log(pair + ' duplicate at position ' + pos)
}

UPDATE

Here's a solver with much more random assignment than the one above, which is more sequential and therefore predictable. We can set pairs we'd like to "unmatch" in the unmatch map, and control how much more we'd like to try random candidates when examining the specially chosen unmatched pairs or other pairs (we might want to give more weight to the former to let them try more random candidates). One result that seemed pretty good as I was playing around is listed below (it was achieved with the same 50/50 random setting). Click "Run snippet" for a different result each time!

const unmatch = {
  // Try to avoid duplicate pairs
  // at indexes (0, 4) and (3, 5)
  4: 0,
  5: 3
};
const unmatchTrials = 50;
const regularTrials = 50;

let cs = ['R', 'G', 'B', 'Y', 'P', 'O', 'W'];
let pairs = [];

for (let i=0; i<6; i++)
  for (let j=i+1; j<7; j++)
    pairs.push(cs[i] + cs[j], cs[j] + cs[i]);

let positionMatches = [];
const results = pairs.slice(0, 28);

// Build combinations
for (let i=0; i<5; i++){
  // Avoid repeating pairs in the same position,
  // as well as in custom positions
  let set = new Set();
  let unmatchS = new Set();

  for (let j=0; j<28; j++){
    const last = results[j].substr(-1);
    let found = false;
    const ri = i + 2;
    let count = unmatch.hasOwnProperty(ri) ? unmatchTrials : regularTrials;

    while (!found && --count > 0){
      const ii = ~~(Math.random() * cs.length);
      const c = cs[ii];
      const candidate = last + c;
      let u = unmatch.hasOwnProperty(ri)
      ? unmatchS.has(results[j][unmatch[ri]] + c)
      : false;

      // Match found
      if (!set.has(candidate) && !results[j].includes(c) && !u){
        results[j] += c;
        set.add(candidate);
        if (unmatch.hasOwnProperty(ri))
          unmatchS.add(results[j][unmatch[ri]] + c)
        found = true;
      }
    }
    // Match not found
    // Lower the restriction
    // and insert random match
    if (!found){
      const cs_ = cs.filter(
        c => !results[j].includes(c));
      const c = cs_[
        ~~(Math.random()*cs_.length)];
      results[j] += c;
      positionMatches.push((i+2) + ':' + last + c);
    }
  }
}

console.log(results.join('\n'));

console.log('');

for (let p of positionMatches){
  const [pos, pair] = p.split(':');
  console.log(pair + ' duplicate at position ' + pos)
}

let m04 = new Set();
let m35 = new Set();

for (let r of results){
  const c04 = r[0] + r[4];
  const c35 = r[3] + r[5];
  if (m04.has(c04))
    console.log('15 match: ' + c04);
  m04.add(c04);
  if (m35.has(c35))
    console.log('46 match: ' + c35);
  m35.add(c35);
}

(The output below seemed pretty good. Dillon Davis noticed a pair of tangrams there that share a sequence "POW." Those could possibly be for two people who may or may not yet know that they share a special connection. (We could also, you know, just tweak one of them manually :)

RGWBYOP
GROBPYW
RBPWOYG
BRWYOGP
RYWPGOB
YRPBGWO
RPBYWOG
PRYGWBO
ROBWPGY
ORGYPBW
RWGOBYP
WRBOPGY
GBOWYRP
BGOYRWP
GYRWBPO
YGROWPB
GPWORBY
PGYBRWO
GOYPWRB
OGPYBRW
GWPROBY
WGBRYPO
BYGPOWR
YBRPOWG
BPGRWYO
PBYWGOR
BORGPWY
OBWGRPY

PO duplicate at position 4
PG duplicate at position 5
RW duplicate at position 5
OW duplicate at position 5
GO duplicate at position 5
GY duplicate at position 6
WO duplicate at position 6
BY duplicate at position 6
PO duplicate at position 6
46 match: BW
15 match: BO
46 match: PW