ROWS <- 6 COLS <- 6
board <- matrix(0, nrow = ROWS, ncol = COLS)
fixed_obstacles <- list( c(2, 2), c(2, 3), c(3, 2) )
part_L <- list( matrix(c(1, 0, 1, 1), nrow=2, byrow=TRUE), # 0 Grad matrix(c(1, 1, 1, 0), nrow=2, byrow=TRUE), # 90 Grad matrix(c(0, 1, 1, 1), nrow=2, byrow=TRUE), # 180 Grad matrix(c(1, 0, 0, 1), nrow=2, byrow=TRUE) # 270 Grad (Achtung: Form prüfen!) )
part_I <- list( matrix(c(1, 1, 1), nrow=1, byrow=TRUE), # Horizontal matrix(c(1, 1, 1), nrow=3, byrow=TRUE) # Vertikal )
part_Square <- list( matrix(c(1, 1, 1, 1), nrow=2, byrow=TRUE) # Nur eine Form (Drehung ändert nichts) )
all_parts <- list( part_L, part_I, part_Square # Fügen Sie hier weitere Teile hinzu, bis alle aus dem Puzzle abgedeckt sind )
#’ Prüft, ob ein Teil (shape) an Position (r, c) gelegt werden kann #’ @param board Aktuelle Spielfeld-Matrix #’ @param part_shape Die Matrix des Teils (eine spezifische Drehung) #’ @param r Startzeile #’ @param c Startspalte #’ @return TRUE wenn platzierbar, sonst FALSE can_place <- function(board, part_shape, r, c) { p_rows <- nrow(part_shape) p_cols <- ncol(part_shape)
# 1. Prüfen ob das Teil innerhalb des Brettes liegt if (r + p_rows - 1 > ROWS || c + p_cols - 1 > COLS) { return(FALSE) }
# 2. Auf Kollisionen prüfen for (i in 1:p_rows) { for (j in 1:p_cols) { if (part_shape[i, j] == 1) { # Wenn im Teil eine 1 ist, muss im Board an der Stelle eine 0 sein if (board[r + i - 1, c + j - 1] != 0) { return(FALSE) # Kollision mit festem Stein (-1) oder anderem Teil (>0) } } } } return(TRUE) }
#’ Legt ein Teil auf das Brett (oder entfernt es) #’ @param board Aktuelle Matrix #’ @param part_shape Form des Teils #’ @param r Startzeile #’ @param c Startspalte #’ @param value Wert, der geschrieben wird (Teil-ID) #’ @return Neue Matrix place_piece <- function(board, part_shape, r, c, value) { p_rows <- nrow(part_shape) p_cols <- ncol(part_shape)
# Wir arbeiten auf einer Kopie, um das Original nicht zu verändern new_board <- board
for (i in 1:p_rows) { for (j in 1:p_cols) { if (part_shape[i, j] == 1) { new_board[r + i - 1, c + j - 1] <- value } } } return(new_board) }
#’ Hauptfunktion zum Lösen des Puzzles #’ @param current_board Der aktuelle Zustand des Brettes #’ @param parts_to_place Liste der noch zu platzierenden Teile #’ @param part_index Index des aktuellen Teils in der Liste #’ @return Matrix mit Lösung oder NULL wenn keine Lösung existiert solve_puzzle <- function(current_board, parts_to_place, part_index = 1) {
# BASISFALL: Alle Teile wurden erfolgreich platziert if (part_index > length(parts_to_place)) { return(current_board) }
# Das aktuelle Teil (Liste aller möglichen Drehungen) current_part_variants <- parts_to_place[[part_index]]
# 1. Jede erlaubte Drehung (Variante) des aktuellen Teils probieren for (variant in current_part_variants) {
# 2. Jede mögliche Position auf dem Brett probieren
for (r in 1:ROWS) {
for (c in 1:COLS) {
# Prüfen ob Platzierung möglich ist
if (can_place(current_board, variant, r, c)) {
# Teil legen (Wert = part_index, damit wir sehen welches Teil wo liegt)
next_board <- place_piece(current_board, variant, r, c, part_index)
# REKURSION: Versuche das NÄCHSTE Teil zu legen
solution <- solve_puzzle(next_board, parts_to_place, part_index + 1)
# Wenn eine Lösung gefunden wurde (nicht NULL), geben wir sie sofort zurück
if (!is.null(solution)) {
return(solution)
}
# BACKTRACKING:
# Wenn wir hier ankommen, war der Zweig eine Sackgasse.
# Da wir in place_piece eine Kopie erstellt haben, ist 'current_board'
# im nächsten Schleifendurchlauf wieder unverändert. Kein explizites "Entfernen" nötig.
}
}
}}
# Wenn keine Drehung und keine Position funktioniert hat: return(NULL) }
#’ Zeigt das Ergebnis als farbiges Gitter an #’ Benötigt keine externen Pakete, nutzt Basis-R Grafik plot_solution <- function(solution_matrix) { if (is.null(solution_matrix)) { cat(“Keine Lösung zum Plotten vorhanden.”) return() }
# Farbpalette definieren # 0 = Weiß (Leer), -1 = Schwarz (Fix), 1..n = Bunte Farben max_val <- max(solution_matrix) colors <- c(“white”, rainbow(max_val + 1)) # Anpassung: Schwarz für Hindernisse (-1) muss gehandhabt werden # Wir mappen die Werte für die Farbe: # Wir erstellen einen Vektor, wo Index dem Wert entspricht (Verschiebung nötig für -1)
# Einfacherer Ansatz für Basis-Plot: # Wir plotten das Bild direkt. # image() erwartet x, y, z (Matrix) # Matrix muss transponiert werden für korrekte Orientierung (unten links ist 1,1 in image)
# Farbtabelle erstellen # Index 1 entspricht dem kleinsten Wert im Matrix (wahrscheinlich -1) # Index n entspricht dem größten Wert unique_vals <- sort(unique(as.vector(solution_matrix))) col_map <- setNames(rainbow(length(unique_vals)), unique_vals) col_map[“-1”] <- “black” # Hindernisse immer schwarz col_map[“0”] <- “white” # Leere Felder weiß (sollte am Ende keine geben)
# Plot erstellen # Wir drehen die Matrix, damit (1,1) oben links ist wie im PDF plot_mat <- t(solution_matrix[nrow(solution_matrix):1, ])
image( z = plot_mat, col = col_map[as.character(unique_vals)], axes = FALSE, main = “Gelöstes Logic Puzzle” )
# Gitterlinien zeichnen grid(nx = COLS, ny = ROWS, col = “gray”)
# Legende (optional) # legend(“topright”, legend = names(col_map), fill = col_map, cex = 0.8) }
cat(“=== Starte Logic Puzzle Solver ===”)
for (obs in fixed_obstacles) { # obs[1] = Zeile, obs[2] = Spalte board[obs[1], obs[2]] <- -1 }
cat(“Hindernisse gesetzt. Starte Backtracking…”)
start_time <- Sys.time() result <- solve_puzzle(board, all_parts) end_time <- Sys.time()
if (!is.null(result)) { cat(“Erfolg! Lösung gefunden in:”, difftime(end_time, start_time, units = “secs”), “Sekunden”) print(result)
# Grafische Ausgabe plot_solution(result)
} else { cat(“Keine Lösung gefunden für diese Konfiguration.”) cat(“Tipp: Prüfen Sie die Definition der Teile (all_parts) und die Hindernisse.”) }