package kapitel_11 /** * Beispiel aus * * - Algorithmen und Datenstrukturen für Dummies * - von Andreas Gogol-Döring und Thomas Letschert * - Verlag Wiley-VCH; Oktober 2019 * - Kapitel 11, Probleme totschlagen * * @author A. Gogol-Döring, Th. Letschert */ import scala.collection.mutable.ListBuffer object AuD_11_09_MazeBacktrackImp_App extends App { val V : List[Int] = (0 to 45).toList // Der Irrgarten aus Kapitel 11 val E1: List[(Int, Int)] = List( (0,1), (1,3), (4,5), (6,7), (3, 9), (4, 10), (5,13), (6,14), (7,17), (8,9), (10,11), (13,14), (16,17), (1,18), (11,22), (14, 25), (18, 19), (20,21), (22,24), (25,26), (19, 29), (20,30), (22,32), (24,33), (16, 36), (27, 37), (28, 29), (29,30), (31,32), (33,34), (35,36), (36,37), (28, 38), (31,39), (32,40), (35,43), (38, 39), (40, 41), (42,43), (43, 44), (44,45), // Zykel: (8, 19), // Abkuerzung: (9, 10) ) val E = E1.flatMap { case (s,d) => List((s, d), (d,s)) } val start = 0 val dest = 45 def MazeBTImp(start: Int, dest: Int): List[Seq[Int]] = { val solutions = new ListBuffer[Seq[Int]] val path : ListBuffer[Int] = new ListBuffer[Int] path.append(start) def solve(): Unit = { if (path.last == dest) solutions.append(path.toList) else { for (x <- V if !path.contains(x) && E.contains((path.last, x))) { path += x solve() path.trimEnd(1) } } } solve() solutions.toList } println(MazeBTImp(start, dest).map(_.mkString(",")).mkString("\n")) }