Schaut euch mal die grafische Repräsentation auf Wikipedia an: https://en.wikipedia.org/wiki/Tower_of_Hanoi#Graphical_representation
So einen Suchbaum für beliebige n möchte ich mit Graphviz programmatisch auch aufstellen… Bei mir fehlen für n=2 aber ein paar Knoten:
graph G {
aa -- ab
ab -- bc
bc -- ac
ac -- cc
ac -- ab
ab -- bb
bb -- bc
bc -- ac
}
Hättet ihr eine Idee, woran das liegen könnte?
public static class Towers {
public ArrayList<Integer> a, b, c;
public Towers(int n) {
a = new ArrayList<>();
b = new ArrayList<>();
c = new ArrayList<>();
for (int i = n; i > 0; i--) {
a.add(i);
}
}
public Towers(Towers o, ArrayList<Integer> x, ArrayList<Integer> y) {
y.add(x.remove(x.size() - 1));
a = new ArrayList<>(o.a);
b = new ArrayList<>(o.b);
c = new ArrayList<>(o.c);
x.add(y.remove(y.size() - 1));
}
@Override
public int hashCode() {
return Objects.hash(a, b, c);
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Towers other = (Towers) obj;
return Objects.equals(a, other.a) && Objects.equals(b, other.b) && Objects.equals(c, other.c);
}
}
public static String graph(int n) {
StringBuilder b = new StringBuilder();
b.append("graph G {\n");
Towers t = new Towers(n);
Set<Towers> s = new HashSet<>();
s.add(t);
b.append(graph(t, s));
b.append("}");
return b.toString();
}
public static String graph(Towers t, Set<Towers> s) {
StringBuilder b = new StringBuilder();
if (!t.a.isEmpty()) {
if (last(t.a) < last(t.b)) {
Towers t2 = new Towers(t, t.a, t.b);
if (!s.contains(t2)) {
s.add(t2);
b.append(edge(t, t2));
b.append(graph(t2, s));
}
}
if (last(t.a) < last(t.c)) {
Towers t2 = new Towers(t, t.a, t.c);
if (!s.contains(t2)) {
s.add(t2);
b.append(edge(t, t2));
b.append(graph(t2, s));
}
}
}
if (!t.b.isEmpty()) {
if (last(t.b) < last(t.a)) {
Towers t2 = new Towers(t, t.b, t.a);
if (!s.contains(t2)) {
s.add(t2);
b.append(edge(t, t2));
b.append(graph(t2, s));
}
}
if (last(t.b) < last(t.c)) {
Towers t2 = new Towers(t, t.b, t.c);
if (!s.contains(t2)) {
s.add(t2);
b.append(edge(t, t2));
b.append(graph(t2, s));
}
}
}
if (!t.c.isEmpty()) {
if (last(t.c) < last(t.a)) {
Towers t2 = new Towers(t, t.c, t.a);
if (!s.contains(t2)) {
s.add(t2);
b.append(edge(t, t2));
b.append(graph(t2, s));
}
}
if (last(t.c) < last(t.b)) {
Towers t2 = new Towers(t, t.c, t.b);
if (!s.contains(t2)) {
s.add(t2);
b.append(edge(t, t2));
b.append(graph(t2, s));
}
}
}
return b.toString();
}
public static String edge(Towers t1, Towers t2) {
StringBuilder b = new StringBuilder();
for (int j = 0; j < t1.a.size(); j++) {
b.append('a');
}
for (int j = 0; j < t1.b.size(); j++) {
b.append('b');
}
for (int j = 0; j < t1.c.size(); j++) {
b.append('c');
}
b.append(" -- ");
for (int j = 0; j < t2.a.size(); j++) {
b.append('a');
}
for (int j = 0; j < t2.b.size(); j++) {
b.append('b');
}
for (int j = 0; j < t2.c.size(); j++) {
b.append('c');
}
b.append("\n");
return b.toString();
}
public static int last(List<Integer> l) {
if (l.isEmpty())
return 100;
return l.get(l.size() - 1);
}
public static void main(String[] args) {
System.out.println(graph(2));
}