Wenn man die sich den Stern aufmalt und die Knoten von oben nach unten und links nach rechts durchnummeriert, kann man das Problem mathematisch beschreiben:
Code: Alles auswählen
a1 + a4 + a7 + a11 = 26
a1 + a3 + a6 + a8 = 26
a2 + a3 + a4 + a5 = 26
a2 + a6 + a9 + a12 = 26
a5 + a7 + a10 + a12 = 26
a8 + a9 + a10 + a11 = 26
Mit der zusätzlichen Einschränkung, dass `a1` bis `a12` paarweise verschieden sein müssen. Dann brauchst Du nur noch "brute force" alle Möglichkeiten die 12 Variablen zu belegen auf die Gleichungen testen. Sind ja nur 479001600 Stück. Wenn man pro Prüfung eine Millisekunde braucht, steht spätestens in etwas mehr als 5½ Tagen eine Lösung fest.
Mit der mathematischen Beschreibung kann man natürlich auch eine Bibliothek füttern, die einen "Finite Domain Constraint Solver" implementiert. Dort gibt man einfach die Variablen (`a1` bis `a12`), den endlichen Wertebereich ("finite domain") für jede Variable (1 bis 12 für `a1` bis `a12`) und die Einschränkungen ("constraints") an; das wären die sechs Formeln und das alle Variablen mit verschiedenen Werten belegt werden müssen. Dann sagt man der Bibliothek: Bitte lösen.
Für Python gibt's zum Beispiel ein Package von Logilab, mit dem eine Lösung so aussehen könnte:
Code: Alles auswählen
from logilab.constraint import fd, Repository, Solver
def main():
def make_variable_names(nodes):
return ['a%d' % i for i in nodes]
def make_sum_constraint(nodes):
return fd.make_expression(nodes, '+'.join(nodes) + ' == 26')
variables = make_variable_names(xrange(1, 13))
domains = dict((v, fd.FiniteDomain(range(1, 13))) for v in variables)
line_variables = map(make_variable_names, ((1, 4, 7, 11),
(1, 3, 6, 8),
(2, 3, 4, 5),
(2, 6, 9, 12),
(5, 7, 10, 12),
(8, 9, 10, 11)))
constraints = map(make_sum_constraint, line_variables)
constraints.append(fd.AllDistinct(variables))
repository = Repository(variables, domains, constraints)
solutions = Solver().solve_one(repository)
print solutions
Das Programm findet bei mir in ca. 3 Sekunden eine Lösung. Alle 960 Lösungen werden in ungefähr 6 Minuten und 15 Sekunden gefunden. Wobei einige von denen natürlich isomorph sind.
Deine Teillösung für mögliche Kombinationen auf einer Geraden etwas verallgemeinert könnte man so aufschreiben:
Code: Alles auswählen
from itertools import ifilter
def iter_combinations(elements, length):
def comb(accu):
if len(accu) == length:
yield tuple(sorted(accu))
else:
for element in elements:
for result in comb(accu + (element,)):
yield result
return comb(tuple())
def all_distinct(elements):
return len(set(elements)) == len(elements)
def exact_sum(target, elements):
return sum(elements) == target
def find_sums(target, elements, length):
def predicate(summands):
return all_distinct(summands) and exact_sum(target, summands)
return sorted(set(ifilter(predicate, iter_combinations(elements, length))))
def main():
sums = find_sums(26, xrange(1, 13), 4)
print sums
print len(sums)
