Διάταξη Θέσεων

Προσδιορισμός θέσεων ατόμων σε μια σειρά βάσει ενδείξεων περιορισμών όπως γειτνίαση, σχετική σειρά και σταθερές θέσεις.

Μάθηση

Τα παζλ διάταξης θέσεων απαιτούν τον προσδιορισμό θέσεων ατόμων σε μια γραμμική ακολουθία βάσει ενός συνόλου περιορισμών. Οι περιορισμοί μπορεί να περιλαμβάνουν σχετική τοποθέτηση, γειτνίαση, μη γειτνίαση, ακραίες θέσεις και σταθερές θέσεις. Ο στόχος είναι να βρεθεί η διάταξη που ικανοποιεί όλους τους περιορισμούς ταυτόχρονα.

Δεδομένων N στοιχείων και περιορισμών C1, C2, ..., Ck: βρες μετάθεση P που ικανοποιεί όλα τα Ci

3 άτομα κάθονται σε σειρά. Η Αλίκη κάθεται αριστερά του Βασίλη. Η Γιώτα κάθεται σε άκρη. Ποιος κάθεται στη μέση;
4 άτομα κάθονται σε σειρά. Ο Δημήτρης δεν κάθεται δίπλα στην Ελένη. Ο Φίλιππος κάθεται στη θέση 1.
5 άτομα κάθονται σε σειρά. Η Αλίκη κάθεται σε άκρη. Ο Βασίλης κάθεται αριστερά της Γιώτας. Ο Δημήτρης δεν κάθεται δίπλα στην Ελένη.

Πώς να το αναγνωρίζετε

Ξεκινήστε με τους πιο περιοριστικούς όρους (σταθερές θέσεις, ακραίες θέσεις)
Χρησιμοποιήστε αποκλεισμό για να μειώσετε τις δυνατότητες
Σχεδιάστε διάγραμμα: αριθμήστε τις θέσεις και συμπληρώστε αυτά που γνωρίζετε
Δοκιμάστε τις εναπομένουσες διατάξεις έναντι όλων των περιορισμών
Αν κολλήσετε, υποθέστε μια θέση και ελέγξτε για αντιφάσεις

Συνηθισμένα λάθη

Να ξεχνάτε ότι 'αριστερά του' σημαίνει οπουδήποτε αριστερά, όχι αναγκαστικά δίπλα
Σύγχυση μεταξύ 'δίπλα σε' και 'αριστερά/δεξιά του'
Μη έλεγχος όλων των περιορισμών στην τελική διάταξη

Λύση βήμα προς βήμα

3 άτομα κάθονται σε σειρά (θέσεις 1-3). Η Αλίκη κάθεται αριστερά του Βασίλη. Η Γιώτα κάθεται σε άκρη. Ο Βασίλης κάθεται στη θέση 2. Ποιος κάθεται στη θέση 1;

Ο Βασίλης είναι στη θέση 2 (δεδομένο)
Η Αλίκη κάθεται αριστερά του Βασίλη, άρα η Αλίκη είναι στη θέση 1
Η Γιώτα κάθεται σε άκρη. Η θέση 1 είναι κατειλημμένη, άρα η Γιώτα στη 3
Τελική διάταξη: Αλίκη (1), Βασίλης (2), Γιώτα (3)

Απάντηση: Αλίκη

Καθοδήγηση εξάσκησης

Λογική Συμπερασματολογία