Es macht ja auch Spaß, etwas auszuprobieren... Anbei ein Programm, mit dem man beliebige Felder und Steine vorgeben kann, und mit dem man auch "zu viele" Steine vorgeben kann, und dann nur ein Teil verwendet wird - da kann man dann herausfinden, ob es mit irgendwelchen Steinen eine Lösung gibt.
Leider keine Zeit mehr, um noch mehr zu erklären.
Code: Alles auswählen
import itertools
from collections import defaultdict
# Die Steine werden global definiert, auch die Liste aller Steine (weil praktisch)
# Ebenso das vollständige Feld
pink00 = [[0,0],[0,1],[1,1],[1,2],[1,3]]
lind01 = [[0,0],[0,1],[0,2],[1,0],[1,2]]
oran02 = [[0,0],[1,0],[1,1],[1,2],[2,1]]
blau03 = [[0,0],[0,1],[0,2],[1,0],[2,0]]
petr04 = [[0,0],[0,1],[0,2],[1,1]]
rot005 = [[0,0],[0,1],[0,2],[0,3],[1,0]]
mari06 = [[0,0],[0,1],[0,2],[1,0]]
mint07 = [[0,0],[0,1],[0,2],[1,0],[1,1]]
lila08 = [[0,0],[0,1],[1,1],[1,2],[2,2]]
gelb09 = [[0,0],[0,1],[0,2],[0,3],[1,1]]
wein10 = [[0,0],[0,1],[1,1],[1,2]]
azur11 = [[0,0],[0,1],[1,0]]
# Liste *aller* Steine
STEINE = [pink00, lind01, oran02, blau03, petr04, rot005,
mari06, mint07, lila08, gelb09, wein10, azur11]
FELD = set(itertools.product(range(11), range(5)))
# Liste der fehlenden Steine Beispiel 26
STEINE26 = [pink00, lind01, oran02, blau03, petr04, rot005, mari06]
# verbleibendes Spielfeld für Beispiel 26
FELD26 = {
(0, 2), (0, 3), (0, 4),
(1, 3), (1, 4),
(2, 3), (2, 4),
(3, 3), (3, 4),
(4, 2), (4, 3), (4, 4),
(5, 3), (5, 4),
(6, 3), (6, 4),
(7, 1), (7, 2), (7, 3), (7, 4),
(8, 2), (8, 3), (8, 4),
(9, 0), (9, 1), (9, 2), (9, 3), (9, 4),
(10,0), (10,1), (10,2), (10,3), (10,4)
}
# Algorithm X in 30 lines, von
# https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
def solve(X, Y, solution=[]):
if not X:
yield list(solution)
else:
# c = min(X, key=lambda c: len(X[c])) # original
# for r in list(X[c]): # original
for r in min(X.values(), key=len).copy(): # neu
solution.append(r)
cols = select(X, Y, r)
for s in solve(X, Y, solution):
yield s
deselect(X, Y, r, cols)
solution.pop()
def select(X, Y, r):
cols = []
for j in Y[r]:
for i in X[j]:
for k in Y[i]:
if k != j:
X[k].remove(i)
cols.append(X.pop(j))
return cols
def deselect(X, Y, r, cols):
for j in reversed(Y[r]):
X[j] = cols.pop()
for i in X[j]:
for k in Y[i]:
# if k != j: # überflüssig, add fragt das schneller ab
X[k].add(i)
def drehe_stein(stein):
"""Dreht den Stein um 90 Grad nach links"""
return [(y, -x) for x, y in stein]
def spiegle_stein(stein):
"""Spiegelt den Stein durch Vertauschen von x und y"""
return [(y, x) for x, y in stein]
def normiere_stein(stein):
"""Verschiebe den Stein in den Nullpunkt.
Der Stein mit dem kleinsten x und dem kleinsten y wird nach 0 verschoben.
"""
dx, dy = min(stein)
return tuple(sorted((x - dx,y - dy) for x, y in stein))
def bewege_stein(stein, dx, dy):
return tuple((x + dx, y + dy) for x, y in stein)
def erzeuge_varianten(stein):
"""Erstellt alle Variationen, den Stein abzulegen.
Nur normierte Varianten.
"""
varianten = [stein]
for _ in range(3):
stein = drehe_stein(stein)
varianten.append(stein)
stein = spiegle_stein(stein)
varianten.append(stein)
for _ in range(3):
stein = drehe_stein(stein)
varianten.append(stein)
return set(map(normiere_stein, varianten))
def aabb(plätze):
"""Berechne die "axis aligned bounding box" der angegebenen Plätze.
Gib die Extremwerte (min und max) für x und y zurück.
"""
x_min = min(xy[0] for xy in plätze)
x_max = max(xy[0] for xy in plätze)
y_min = min(xy[1] for xy in plätze)
y_max = max(xy[1] for xy in plätze)
return x_min, x_max, y_min, y_max
def zeige_feld(loesung, Y, feld_gesamt=()):
"""Stelle die (Teil-)Lösung als Zeichenkette dar.
Für eine Teillösung kann das gesamte Feld mitgegeben werden,
ggf. werden dann Punkte dargestellt.
"""
# Das gesamte Feld wird erst mal mit Punkten dargestellt
feld = dict.fromkeys(feld_gesamt, ".")
# Stein 0 = A, Stein 1 = B, usw. überschreibt ggf. die Punkte
for i, j, dx, dy in loesung:
for xy in Y[i, j, dx, dy]:
if isinstance(xy, tuple): # die virtuellen Plätze wollen wir nicht sehen
feld[xy] = chr(65 + i)
x_min, x_max, y_min, y_max = aabb(feld)
zeilen = ["".join(feld.get((x, y), " ") for x in range(x_min, x_max + 1))
for y in range(y_min, y_max + 1)]
return "\n".join(zeilen)
def zeige_benutze_steine(steine, loesung):
"""Stelle die benutzten und unbenutzten Steine dar."""
benutzt = set(stein[0] for stein in loesung if stein[1] is not None)
return "".join(chr(65 + i) if i in benutzt else "."
for i in range(len(steine)))
def berechne_bedingungen(steine=STEINE, feld=FELD, alle=True):
"""Berechne die Bedingungen X und Y.
X enthält als Schlüssel die möglichen Plätze. Die Werte sind alle
Steine (inkl. Bewegungen), die diesen Platz bedecken.
Y ist genau andersherum: Die Schlüssel sind alle Steine (inkl. Bewegungen),
die Werte sind alle Plätze, die davon bedeckt werden.
Wird alle=False gesetzt, dann müssen nicht alle Steine verwendet werden.
Das wird umgesetzt durch einen zusätzlich Stein, der nur den virtuellen Platz
belegt.
"""
X = defaultdict(set)
# damit ein Platz auch dann in X vorhanden ist, wenn ihn kein Stein überdeckt
for xy in feld:
X[xy] = set()
Y = defaultdict(list)
# stein: originaler Stein (unbewegt)
# variante: auch gedreht und gespiegelt, aber nicht verschoben
for i, stein in enumerate(steine): # stein ist unbewegt
if not alle:
X[i].add((i, None, None, None)) # virtueller Platz i wird durch virtuellen Stein i belegt
Y[(i, None, None, None)].append(i)
for j, variante in enumerate(erzeuge_varianten(stein)):
for dx, dy in feld:
stein_bewegt = bewege_stein(variante, dx, dy)
if not feld.issuperset(stein_bewegt):
continue
# stein kann nur an einer Stelle sein, daher bekommen alle
# Varianten einen künstlichen überlappenden Platz dazu
X[i].add((i, j, dx, dy)) # virtueller Platz i
Y[i, j, dx, dy].append(i)
for xy in stein_bewegt:
# Der Platz (x, y) wird vom Stein i in Variante j
# mit Verschiebung (dx, dy) überdeckt
X[xy].add((i, j, dx, dy))
Y[i, j, dx, dy].append(xy)
return X, Y
def str2feld(s):
"""Erzeuge aus einem string ein feld.
(0, 0) = links oben.
Erzeugt wird ein set.
Felder sind mit "#" zu kennzeichnen.
"""
feld = set()
for y, line in enumerate(s.splitlines()):
for x, c in enumerate(line):
if c == "#":
feld.add((x, y))
return feld
def loese_und_zeige(steine, feld, max_loesungen=10, alle=False, zeige_benutzt=False):
"""Berechne die Bedingungen, Lösungen, und zeige sie.
Höchstens max_loesungen Lösungen werden berechnet und gezeigt.
Der Parameter alle wird durchgereicht.
Ist zeige_benutzt=True, dann werden die benutzten Steine ausgegeben.
"""
print(zeige_feld((), (), feld))
X, Y = berechne_bedingungen(steine, feld, alle=alle)
for n, loesung in enumerate(itertools.islice(solve(X, Y), max_loesungen), 1):
print("Lösung", n)
print(zeige_feld(loesung, Y, feld))
print()
if zeige_benutzt:
print(zeige_benutze_steine(STEINE, loesung))
print()
if __name__ == "__main__":
# gesamtes Feld mit allen Steinen (Standardfall)
print("Vollständige Lösung")
X, Y = berechne_bedingungen()
for loesung in itertools.islice(solve(X, Y), 10):
print(zeige_feld(loesung, Y))
print()
# Beispiel 26
print("Beispiel 26")
loese_und_zeige(STEINE26, FELD26)
# Beispiel 26, aber alle Steine dürfen verwendet werden
print("Feld von Beispiel 26, aber alle Steine dürften verwendet werden")
# "alle=False" muss angegeben werden, weil nicht alle Steine verwendet
# werden müssen (können)
loese_und_zeige(STEINE, FELD26, alle=False)
# # Beispiel für eine besondere Form
print("besondere Form")
feldstr = """
#########
####### ###
###########
#########
"""
feld = str2feld(feldstr)
loese_und_zeige(STEINE, feld, alle=False)
# Beispiel für eine andere besondere Form, dauert etwas länger
# nur 2 Lösungen, und zwar mit den gleichen benutzen Teilen!
print("besondere Form, nur zwei Lösungen")
feldstr = """
#########
#### ####
#### ####
#########
"""
feld = str2feld(feldstr)
loese_und_zeige(STEINE, feld, alle=False, zeige_benutzt=True)
# Beispiel für noch eine andere besondere Form - dauert noch länger
print("Form mit vielen Lösungen, verschiedene benutzte Steine")
feldstr = """
######
######
######
######
######
######
######
######
"""
feld = str2feld(feldstr)
loese_und_zeige(STEINE, feld, alle=False, max_loesungen=10, zeige_benutzt=True)
