Eichen im Kreis – systematische Suche

Wie schreibt man ein Programm, das alle Konstellationen prüft?
Man formuliert die Vorgehensweise in natürlicher Sprache und macht dann ein Programm daraus.

Wir nennen die Anzahl der zu verteilenden Eichen N. Wir nummerieren die Eichen von [ 0 .. (N-1) ] durch.
Wir stellen uns einen Kreis vor, indem es (N*(N-1)+1) Positionen gibt. Die Positionen werden im Uhrzeigersinn durchnummeriert, von [ 0 .. N*(N-1) ].
Der Abstand zweier Bäume entspricht der Differenz ihrer Positionen. Wir nennen ihn distR und distL, also Distanz nach rechts und nach links. Die Summe dieser Distanzen beträgt immer (N*(N-1)+1). Die kleinst mögliche Distanz ist 1, d.h. zwei Bäume stehen direkt nebeneinander, die größtmögliche Distanz ist (N*N-1).
Wir legen eine Liste (positions) an, die für jeden Baum dessen Position im Kreis enthält. Ist die Position eines Baums noch nicht festgelegt, tragen wir bei ihm einen speziellen Wert ein, der als Positionsangabe unzulässig wäre, zum Beispiel „-1“.
Wir füllen positions zunächst für jeden Baum mit diesem Wert, denn noch haben wir keinerlei Festlegungen über die Anordnung der Bäume getroffen.
Die Grundidee ist nun, dass wir die Bäume der Reihe nach möglichst eng platzieren, wobei wir aber ständig darauf achten, dass alle ihre Abstände unterschiedlich sind.
Naheliegenderweise beginnen wir damit, dass wir den Baum 0 der Position 0 zuordnen. Der nächste verfügbare Baum ist danach Baum 1.
Wir stellen ihn möglichst eng rechts (also im Uhrzeigersinn) daneben. Nun sieht positions so aus
[ 0 , 1 , -1 , -1 , -1 , -1 ].
Jedesmal wenn wir einen weiteren Baum platziert haben, überprüfen wir alle Abstände.
Dazu benutzen wir eine Liste aller denkbaren Abstände, die wird dists (distances) nennen. Diese Liste enthält für jeden Abstand 1 oder 0, je nachdem, ob er bei der bisherigen Anordnung der Bäume vorkommt oder nicht. Nachdem wir die ersten zwei Bäume platziert haben, enthält dists überall 1, nur die Einträge an den Positionen 1 und 30 sind 0. Aus technischen Gründen enthält dists auch ein Element an Position 0, das allerdings immer 0 ist, da der Mindestabstand zweier Bäume 1 beträgt.
Wir fahren damit fort, weitere Bäume hinzuzufügen, und zwar immer möglichst eng rechts neben ihrem Vorgänger.
Wenn wir jetzt Baum 2 auf die nächste Position rechts von Baum 1 stellen wollen, erhalten wir den ersten Konflikt, denn der Abstand 1 kommt bereits vor.
Jedesmal wenn es zu einem Konflikt kommen würde, probieren wir es mit der nächsten Position weiter rechts.
Nun sieht positions so aus: [ 0, 1, 3, -1, -1, -1 ].
In der Liste der Abstände sind jetzt schon 6 Werte besetzt, nämlich 1,2,3,28,29,30.
Manchmal werden wir feststellen, dass kein Platz mehr für den Baum ist, den wir neu hinzufügen wollen, denn direkt links neben Baum 0 ist Schluss). In so einem Fall fügen wir den Baum nicht hinzu, sondern schieben den vorherigen Baum weiter nach rechts, natürlich immer unter Überprüfung der Abstände.
Haben wir für ihn einen passenden anderen Platz gefunden, versuchen wir wieder, den nächsten Baum möglichst nah zu platzieren.
Achtung: Beim Verschieben eines Baums, der bereits platziert worden war, müssen wir die ihm zuvor zugeordneten Abstände wieder als verfügbar markieren (auf 0 setzen) und nach dem Verschieben die neuen Abstände als benutzt markieren (=auf 1 setzen).
Es kann sein, dass es nicht genügt, den vorletzten Baum auf diese Weise zu verschieben; finden wir für ihn keinen passenden Platz mehr, dann entfernen wir auch ihn und schieben analog seinen Vorgänger weiter nach rechts.
Wenn es uns gelingt, alle Bäume zu platzieren, dann haben wir eine Lösung gefunden. Wir machen dann dennoch weiter, um auch die übrigen Lösungen zu finden. D.h. wir entfernen den letzten Baum und versuchen, seinen Vorgänger weiter nach rechts zu schieben. Ist auch für den kein Platz mehr, so entfernen wir ihn und verschieben den Vor-Vorgänger usw.; alles wie gehabt!
Irgendwann werden wir an einem Punkt ankommen, an dem es nötig werden würde, den zweiten Baum (Baum 1) zu verschieben. In diesem Moment sind wir fertig, denn jede weitere Lösung wäre nur noch eine Drehung der bisher gefundenen Anordnungen. Schließlich muss immer irgendwo der Abstand 1 vorkommen, den wir gleich zu Beginn verwendet haben. Da bei jeder gefundenen Lösung immer auch deren Spiegelbild vorkommt, ist die Anzahl der „echt“ verschiedenen Lösungen halb so groß wie von uns gefundene Anzahl.

Mit etwas Nachdenken erkennt man Ansatzpunkte, um Rechenzeit einzusparen. Beispielsweise bilden die Abstände wie oben erläutert grundsätzlich Paare. Es genügt daher, nur den jeweils kleineren Abstand als benutzt zu markieren. Die Liste der Abstände ist dann nur noch halb so lang.

Man kann beim Hinzufügen der Bäume immer sofort mit dem kleinsten noch nicht benutzten Abstand beginnen. Dessen Wert kann man sich merken, anstatt ihn jedesmal neu zu ermitteln. Ebenso kann man sich den größten benutzten Abstand merken und mit dem Verschieben eines Baums nach rechts aufhören, wenn dieser Wert erreicht werden würde.