Ένας λαβύρινθος (maze) είναι κατά κανόνα ένα μονοπάτι η ένα σύνολο μονοπατιών από μία είσοδο σε ένα σημείο στόχο. Καθότι υπάρχουν διάφορα είδη λαβυρίνθων, επικεντρωνόμαστε σε εκείνο των τέλειων λαβυρίνθων (perfect mazes) σε επιφανειες δυο διαστασεων. Στοχος ειναι το προγραμμα μας να μπορει να κατασκευαζει εναν τυχαιο (δηλαδη οχι σταθερο ανα τις εκτελεσεις) τελειο λαβυρινθο, χρησιμοποιωντας μια παραλλαγμενη εκδοση του αλγοριθμου του Kruskal. Επισης, θα πρεπει να ειναι σε θεση να επιλυει εναν τελειο λαβυρινθο και να τον τυπωνει στην οθονη μαζι με το μονοπατι της λυσης.
Δηλαδη για καθε ζευγος δυο τυχαιων κελιων σημειων του λαβυρινθου, υπαρχει ακριβως ενα μονοπατι που τα ενωνει. Αναλογιζομενοι την ιδιοτητα αυτη των τελειων λαβυρινθων μπορουμε να αντιληφθουμε οτι το σημειο εισοδου και το σημειο στοχος δεν επηρεαζουν την κατασκευη του συγκεκριμενου τυπου λαβυρινθων. Συνεπως, θα μπορουσαμε να ορισουμε ως σημειο εισοδου και σημειο στοχο σημειο εξοδου οποιοδηποτε ζευγος σημειων (π.χ. πανω αριστερη γωνια και κατω δεξια γωνια του λαβυρινθου), αφου σιγουρα θα υπαρχει ενα μοναδικο μονοπατι που θα τα ενωνει.
Στην ουσια ενας λαβυρινθος θα πρεπει να αναπαρισταται στο προγραμμα σας με το data type Maze (Σχημα 1). Το data type Maze εχει τρια fields, εκ των οποιων τα δυο, width και height, αποθηκευουν τις τιμες των διαστασεων του λαβυρινθου στο διδιαστατο επιπεδο. Το field cells ειναι μια λιστα απο tuples τυπου (Bool, Bool) τα οποια αντιπροσωπευουν για καθε κελι - σημειο του λαβυρινθου την υπαρξη (True) η τη μη υπαρξη (False) τοιχου δεξια και αντιστοιχα κατω του κελιου - σημειου. data
Maze = Maze { cells :: [(Bool, Bool)] −− [(rightWall , downWall)] , width :: Int
, height : : Int }Ο αλγοριθμος επιλυσης ειναι ο Αναζητησης Κατα Βαθος (Depth-First Search). Ως γνωστον ο αλγοριθμος αυτος εξερευνα οσο το δυνατον περισσοτερο κατα μηκος ενα μονοπατι μεχρι να βρει το στοχο η ενα αδιεξοδο, οποτε και οπισθοδρομει. Ο αλγοριθμος θα πρεπει να ειναι σε θεση να δεχεται τις συντεταγμενες ενος κελιου αρχης (sx, sy) και ενος κελιου στοχου (gx, gy) και να υπολογιζει το μονοπατι μεταξυ αυτων (το οποιο σιγουρα υπαρχει σε εναν τελειο λαβυρινθο). Επισης, δε θα πρεπει σε καμια περιπτωση η υλοποιηση του DFS να χρησιμοποιει δομη στην οποια θα αποθηκευει τα κελια που εχουν ηδη επισκεφθει.
solvePerfect :: Maze → (Int, Int) → (Int, Int) → [(Int, Int)], Δεχεται ενα τελειο λαβυρινθο και τις συντεταγμενες ενος κελιου αρχης (sx, sy) και ενος κελιου στοχου (gx, gy) και επιστρεφει μια λιστα με τα κελια που ανηκουν στο μονοπατι της λυσης.
Ο αλγοριθμος κατασκευης που θα υλοποιησετε θα ειναι μια παραλλαγη του αλγοριθμου του Kruskal ο οποιος υπολογιζει το δεντρο επικαλυψης ελαχιστου κοστος (minimum-cost spanning tree) ενος γραφου. Στην ουσια δεν μας ενδιαφερει η ιδιοτητα του ελαχιστου κοστους αλλα ο υπολογισμος ενος δεντρου επικαλυψης που περιεχει καθε κομβο του γραφου, οπου ως γραφο φανταζομαστε εναν τε- λειο λαβυρινθο με τα κελια - σημεια να ειναι κομβοι και τα μονοπατια που ενωνουν γειτονικα κελια - σημεια (μονοπατια μηκους 1) να ειναι ακμες μεταξυ των κομβων. Το γεγονος οτι ο λαβυρινθος σας αναπαρισταται στην ουσια ως ενα πλεγμα απο κελια (Σχημα 1) δεν σας εμποδιζει να τον φανταζεστε και να τον διαχειριζεστε ως μια δενδρικη δομη. Εξαλλου, ο τροπος που περιγραφεται ενα κελι - (υπαρξη η μη υπαρξη τοιχου δεξια, υπαρξη η μη υπαρξη τοιχου κατω) - παραπεμπει σε δενδρικη δομη. Ο αλγοριθμος κατασκευης εχει ως εξης: Αρχικα, φτιαχνουμε ενα σετ για καθε κελι ci του λαβυρινθου και προσθετουμε το κελι ci στο αντιστοιχο σετ. Επισης, φτιαχνουμε μια λιστα ολων των τοιχων που θα μπορουσαν να υπαρχουν στο λαβυρινθο, η οποια εχει τη μορφη [ ... , (ci, cj), ... ], οπου το ζευγος (ci, cj) δηλωνει την υπαρξη τοιχου μεταξυ των κελιων ci και cj. Εν συνεχεια, ανακατευουμε τυχαια τη λιστα και τη διατρεχουμε. Για καθε τοιχο ελεγχουμε αν τα κελια ci και cj τα οποια διαχωριζει ανηκουν σε διαφορετικα σετς και αν κατι τετοιο ισχυει, αφαιρουμε τον τοιχο και ενωνουμε τα σετς των κελιων ci και cj. Παρακατω παρουσιαζεται ο αλγοριθμος σε ψευδοκωδικα.
kruskal :: Maze → Maze,
η οποια δεχεται ενα λαβυρινθο χωρις μονοπατια (οπως δηλαδη αυτος επιστρεφεται απο μια κληση της ) και εκτελωντας την παραλλαγη του αλγοριθμου του Kruskal επιστρεφει εναν τυχαιο τελειο λαβυρινθο.
showMaze :: Maze → [(Int, Int)] → String,η οποια δεχεται ενα λαβυρινθο και μια λιστα με τα κελια που ανηκουν στο μονοπατι της λυσης και επιστρεφει σε ενα String την αναπαρασταση του λαβυρινθου και της λυσης οπως περιγραφεται παρακατω. Καθε κελι θα αναπαρισταται σαν ενα κουτακι απο το οποιο ομως μπορει να λειπει οποιοσδηποτε τοιχος. Επειδη καθε κελι εχει πληροφορια μονο για τους τοιχους που βρισκονται δεξια και κατω του.
putStr (showMaze (kruskal (makeMaze 5 5) ) [] )