Backtracking — systematisch suchen
Backtracking ist Rekursion + „Wenn dieser Weg nicht klappt, geh zurück und probiere den nächsten." Klassisches Werkzeug für Constraint‑Probleme.
Pseudo‑Code Schema:
function solve(state):
if isSolved(state): return state
for next in possibleMoves(state):
if isValid(state, next):
apply(next)
result = solve(state)
if result: return result
undo(next)
return null // kein WegKlassische Backtracking‑Probleme:
- N‑Queens: N Damen auf Schachbrett ohne Konflikt.
- Sudoku Solver.
- Permutationen / Kombinationen.
- Labyrinth lösen.
- Graph Coloring.
- Subset Sum.
Zurück zu Informatik