from gropro.puzzle import Puzzle
from gropro.ebene import Ebene
from gropro.teil import Teil
from gropro.operation import Invert, Rotate
from dataclasses import dataclass
from collections import Counter
from typing import Optional
import logging
import os
TWEAK_COUNT = True if os.getenv("GROPRO_COUNT", "") else False
[Doku]
@dataclass
class PuzzleSolver:
puzzle: Puzzle
[Doku]
def solve(self) -> tuple[bool, int]:
"""Wrapper für die Backtracking Implementation
- Initialisiere anhand des übergebenen Puzzle
- Lege die erste, leere Ebene ohne Vorgänger an
- Sortiere die Puzzleteile
- Starte das Backtracking
- Ordne alle Ebenen die zu der Lösung führen dem Puzzle zu
"""
logger = logging.getLogger(__name__)
teile = list(sorted(self.puzzle.teile))
dim = self.puzzle.dimension[0]
ebene = Ebene(dim)
def insolve(
ebene: Ebene, teile: list[Teil], reccount: int = 0
) -> tuple[Optional[Ebene], int]:
"""Rekursionsvorschrift
- Breche ab wenn keine Teile übergeben wurden
- Gebe die aktuelle Ebene zurück, sie bildet den Kopf der Lösung Kette
- Erzeuge eine neue Ebene wenn die aktuelle voll ist
- Iteriere über alle verfügbaren Teile
- Iteriere rückwärts wenn es die erste Ebene ist
- Platziere jedes Teil
- Mache einen Rekursionsschritt wenn ein Teil platziert wurde
- Breche ab und signalisiere den ungültigen Pfad wenn kein Teil übrig ist
"""
reccount += 1
if not teile: # Positiv-Abbruch Bedingung
return ebene, reccount
if ebene.voll:
ebene = Ebene(dim, lower=ebene)
if TWEAK_COUNT:
if ebene.lower:
bump_count_bottom = 0
hole_count_bottom = 0
for teil in ebene.lower.teile:
c = Counter(teil.elemente)
hole_count_bottom += c[0] # type: ignore
bump_count_bottom += c[1] + c[3] # type: ignore
bump_count_rem = 0
hole_count_rem = 0
for teil in teile:
c = Counter(teil.elemente)
hole_count_rem += c[0] # type: ignore
bump_count_rem += c[2] + c[3] # type: ignore
if (
hole_count_rem + hole_count_bottom
< bump_count_rem + bump_count_bottom
):
return None, reccount
unfit: list[Teil] = []
index = -1 if ebene.depth == 0 else 0
while teile:
teil = teile.pop(index)
if ebene.add(teil):
sln, reccount = insolve(ebene, teile + unfit, reccount)
if sln:
return sln, reccount
ebene.teile.pop()
teil.manipulate(Rotate())
if ebene.add(teil):
sln, reccount = insolve(ebene, teile + unfit, reccount)
if sln:
return sln, reccount
ebene.teile.pop()
teil.manipulate(Invert())
if ebene.add(teil):
sln, reccount = insolve(ebene, teile + unfit, reccount)
if sln:
return sln, reccount
ebene.teile.pop()
teil.operations.pop(0)
if ebene.add(teil):
sln, reccount = insolve(ebene, teile + unfit, reccount)
if sln:
return sln, reccount
ebene.teile.pop()
teil.operations = []
unfit.insert(0, teil)
return None, reccount
if TWEAK_COUNT:
capacity_topbottom = 2 * dim * dim
bump_count = 0
hole_count = 0
for teil in teile:
c = Counter(teil.elemente)
hole_count += c[0] # type: ignore
bump_count += c[1] + c[2] + 2 * c[3] # type: ignore
if hole_count + capacity_topbottom < bump_count:
logger.warn(
"Die Puzzle Teile weisen zu viele Halbkugeln auf, das Puzzle ist unlösbar!"
)
return False, 0
solution, reccount = insolve(ebene, teile)
if not solution:
return False, reccount
while solution.lower:
self.puzzle.ebenen.append(solution)
solution = solution.lower
self.puzzle.ebenen.append(solution)
return True, reccount