Buchstabenverteilung

19.10.2018

Beim Unterstufenwettbewerb des Landes Baden-Württemberg - Problem des Monats Oktober 2018 im Bereich Mathematik-Naturwissenschaften lautet die Fragestellung wie folgt:

Setze in die folgenden 8 Kreise die Buchstaben A, B, C, E, F, G, H und I so ein, dass in verbundenen Feldern keine 2 Buchstaben alphabetisch aufeinander folgen.

Der Lösungsansatz

Nebst den Möglichkeiten, das ein geeignetes Optimierungsverfahren bietet, sind hier das simple Ausprobieren aller Lösungsmöglichkeiten denkbar. Da es sich um acht Buchstaben auf acht Plätzen handelt, existieren 8! (sprich Acht Fakultät) Permutationen, demnach in Zahlen 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40320 Möglichkeiten die acht Buchstaben zu platzieren.

Nun kann man eine der möglichen Permutation als Feld ablegen und die Position des jeweiligen Buchstabens in diesem Feld der Position in dem obigen Bild zuordnen, wie in folgender Abbildung dargestellt. Die Felder 9, 10, 11 sind ja durch die Aufgabenstellung mit den Buchstaben P, D und M bereits festgelegt.

Die Permutationen starten mit [A,B,C,E,F,G,H,I] und enden mit [I,H,G,F,E,C,B,A].

    00001 : [A,B,C,E,F,G,H,I]
    00002 : [A,B,C,E,F,G,I,H]
    00003 : [A,B,C,E,F,H,G,I]
    ...
    03991 : [A,H,F,C,E,B,G,I]
    03992 : [A,H,F,C,E,B,I,G]
    03993 : [A,H,F,C,E,G,B,I]
    ...
    40318 : [I,H,G,F,E,B,C,A]
    40319 : [I,H,G,F,E,C,A,B]
    40320 : [I,H,G,F,E,C,B,A]

Die Modellierung

Für die Abhängigkeiten der zu prüfenden Bedingung, nämlich dass keiner der Knoten in der Graphik einen Buchstaben beinhaltet, der Vorgänger oder Nachfolger eines Nachbar-Knoten ist, kann man ein kleines Knoten-Netzwerk definieren, das die entsprechende Verbindungen enthält.

In JavaScript bieten sich dazu zwei Klassen an, die man wie folgt implementieren kann:

function Node (lt) {
  var node = this;
  node.letter = lt;
  node.neighbours = [];
}

Der Knoten bekommt einen Parameter, welcher den Buchstaben beinhaltet, sowie ein (anfangs leeres) Array mit seinen Nachbarn.

function Network (arr) {
  var nw = this;
  nw.node01 = new Node(arr[0]);  // top line
  nw.node02 = new Node(arr[1]);

  nw.node03 = new Node(arr[2]);  // second line
  nw.node04 = new Node(arr[3]);
  nw.node05 = new Node(arr[4]);
  nw.node06 = new Node(arr[5]);

  nw.node07 = new Node(arr[6]);  // third line
  nw.node08 = new Node(arr[7]);

  nw.node09 = new Node('P');  // bottom line
  nw.node10 = new Node('D');
  nw.node11 = new Node('M');
}

Das Netzwerk bekommt einen Parameter, der eines der permutierten Felder beinhaltet, mit denen die Knoten des Netzwerks belegt werden. Für die Knoten 9, 10 und 11 sind die Buchstaben fest vorgegeben.

Der Aufbau der Verknüpfungen ist eine kleine Fleißaufgabe und besteht darin, zu jedem Knoten seine Nachbarknoten ins neighbours Array einzufügen.

  nw.node01.neighbours.push(nw.node02); // connections of node 1
  nw.node01.neighbours.push(nw.node03);
  nw.node01.neighbours.push(nw.node04);
  nw.node01.neighbours.push(nw.node05);

  ... // skipped code due to length here - same for node02...node10

  nw.node11.neighbours.push(nw.node06); // connections of node 11
  nw.node11.neighbours.push(nw.node08);
  nw.node11.neighbours.push(nw.node10);

Überprüfung eines Netzwerks

Wenn ein Netzwerk mit einer Permutation befüllt wurde, soll eine Methode aufgerufen werden, die prüft, ob das Netzwerk unsere Bedingung erfüllt. Das ist immer dann der Fall, wenn für jeden der 11 Knoten gilt, dass kein Nachbar ein Vorgänger oder Nachfolger ist.

Das kann auf der Netzwerk-Klasse leicht wie folgt kodiert werden.

  nw.isValid = () => {
    const ok =
      nw.node01.checkNeighbours() &&
      nw.node02.checkNeighbours() &&
      nw.node03.checkNeighbours() &&
      nw.node04.checkNeighbours() &&
      nw.node05.checkNeighbours() &&
      nw.node06.checkNeighbours() &&
      nw.node07.checkNeighbours() &&
      nw.node08.checkNeighbours() &&
      nw.node09.checkNeighbours() &&
      nw.node10.checkNeighbours() &&
      nw.node11.checkNeighbours();

      return ok;
  };

Die Methode checkNeighbours ist ebenfalls recht einfach. Sie läuft alle Knoten ab, die ins neighbours Array eingefügt wurden und prüft den Buchstaben des Knotens ab, ob er ein Vorgänger oder Nachfolger ist. Diese Prüfung kann erfolgen, indem die beiden zu vergleichenden Buchstaben in ASCII Code gewandelt werden und voneinander abgezogen werden, ist der Betrag exakt 1, dann sind die beiden Buchstaben Nachbarn (also Vorgänger oder Nachfolger).

  const diff = Math.abs(letter1.charCodeAt(0) - letter2.charCodeAt(0));
  if (diff === 1) // ... this is a neighbour!

Die Methode checkNeighbours auf der Knoten-Klasse sieht also wie folgt aus:

  node.checkNeighbours = () => {
    for (let n in node.neighbours) {
      const nb = node.neighbours[n];
      const abs = Math.abs(nb.letter.charCodeAt(0) - node.letter.charCodeAt(0));
      if (abs === 1) return false;
    }
    return true;
  };

Alle Permutationen erstellen

Alle Permutationen eines Arrays input berechnet die folgende Funktion:

function permutation (input) {
  let ret = [];
  for (let i = 0; i < input.length; i = i + 1) {
    let rt = permutation(input.slice(0, i).concat(input.slice(i + 1)));
    if (!rt.length) {
      ret.push([input[i]]);
    }
    else {
      for (let j = 0; j < rt.length; j = j + 1) {
        ret.push([input[i]].concat(rt[j]));
      }
    }
  }
  return ret;
}

Das Finale

Mit diesem Code kann man dann ganz leicht für alle möglichen Kombinationen ein Netzwerk anlegen und überprüfen, ob es den Bedingungen gerecht wird.

Das Berechnen aller Möglichkeiten geht (zumindest auf einem Desktop-Rechner) recht flink. Für das Problem gibt es 8 Lösungen:

1. Permutation #03991 : [A,H,F,C,E,B,I,G]
2. Permutation #14047 : [C,H,F,A,E,B,I,G]
3. Permutation #18548 : [E,G,H,C,I,B,A,F]
4. Permutation #27587 : [G,E,B,I,C,H,F,A]
5. Permutation #29697 : [G,I,B,E,C,F,H,A]
6. Permutation #30264 : [H,A,B,E,C,F,G,I]
7. Permutation #31824 : [H,C,B,E,A,F,G,I]
8. Permutation #39422 : [I,G,F,C,E,B,A,H]

Im Folgenden können die Lösung grafisch angezeigt werden, benutze die Schaltflächen, um das entsprechende Bild zu aktualisieren.