Εισαγωγή
Ο Γρίφος της Ζέβρας είναι ένας διάσημος γρίφος λογικής, στον οποίο υπάρχουν πέντε σπίτια, καθένα βαμμένο με διαφορετικό χρώμα.
Τα σπίτια έχουν διαφορετικούς κατοίκους, οι οποίοι έχουν διαφορετικές εθνικότητες, διαφορετικά κατοικίδια, πίνουν διαφορετικά ποτά και απολαμβάνουν διαφορετικά χόμπι.
Για να σε βοηθήσουμε να λύσεις τον γρίφο, σου δίνονται 15 προτάσεις που περιγράφουν τη λύση.
Ωστόσο, μόνο αν συνδυάσεις τις πληροφορίες από όλες τις προτάσεις θα μπορέσεις να βρεις τη λύση του γρίφου.
Ο Γρίφος της Ζέβρας είναι ένα πρόβλημα ικανοποίησης περιορισμών (CSP).
Σε ένα τέτοιο πρόβλημα, έχεις ένα σύνολο από πιθανές τιμές και ένα σύνολο από περιορισμούς που καθορίζουν ποιες τιμές είναι έγκυρες.
Ένα άλλο γνωστό CSP είναι το Sudoku.
Οδηγίες
Ο στόχος σου είναι να λύσεις το Παζλ της Ζέβρας, για να βρεις τις απαντήσεις σε αυτές τις δύο ερωτήσεις:
- Ποιος από τους κατοίκους πίνει νερό;
- Ποιος έχει τη ζέβρα;
Παζλ
Για τις παρακάτω 15 προτάσεις γνωρίζουμε πως είναι όλες αληθείς:
- Υπάρχουν πέντε σπίτια.
- Ο Άγγλος μένει στο κόκκινο σπίτι.
- Ο Ισπανός έχει τον σκύλο.
- Το άτομο στο πράσινο σπίτι πίνει καφέ.
- Ο Ουκρανός πίνει τσάι.
- Το πράσινο σπίτι βρίσκεται αμέσως δεξιά από το σπίτι του ελεφαντοστού.
- Στον ιδιοκτήτη του σαλιγκαριού αρέσει να πηγαίνει για χορό.
- Το άτομο στο κίτρινο σπίτι είναι ζωγράφος.
- Το άτομο στο μεσαίο σπίτι πίνει γάλα.
- Ο Νορβηγός μένει στο πρώτο σπίτι.
- Αυτός που απολαμβάνει το διάβασμα μένει στο σπίτι δίπλα στο άτομο με την αλεπού.
- Το σπίτι του ζωγράφου είναι δίπλα στο σπίτι με το άλογο.
- Το άτομο που παίζει ποδόσφαιρο πίνει χυμό πορτοκαλί.
- Ο Ιάπωνας παίζει σκάκι.
- Ο Νορβηγός μένει δίπλα στο μπλε σπίτι.
Επιπλέον, καθένα από τα πέντε σπίτια είναι βαμμένο με διαφορετικό χρώμα, και οι κάτοικοί τους έχουν διαφορετική εθνικότητα, έχουν διαφορετικά κατοικίδια, πίνουν διαφορετικά ροφήματα και ασχολούνται με διαφορετικά χόμπι.
Υπάρχουν 24 δισεκατομμύρια (5!⁵ = 24.883.200.000) πιθανές λύσεις, οπότε προσπάθησε να αποκλείσεις όσο το δυνατόν περισσότερες λύσεις.
Υλοποίηση
Όρισε μία μόνο συνάρτηση, τη SolvePuzzle, η οποία επιστρέφει μια λύση
που περιέχει δύο συμβολοσειρές, των οποίων οι τιμές είναι οι απαντήσεις στις
ερωτήσεις του γρίφου της ζέβρας "Ποιος πίνει νερό;" και "Ποιος έχει τη ζέβρα;".
Κάθε απάντηση θα είναι μία από τις εθνικότητες των κατοίκων:
Englishman, Spaniard, Ukrainian, Norwegian ή Japanese.
Προφανώς, θα μπορούσες απλώς να γράψεις μια συνάρτηση μιας γραμμής,
αν κρυφοκοιτάξεις το πρόγραμμα των τεστ για να δεις την αναμενόμενη λύση.
Όμως ο στόχος είναι να αναπτύξεις έναν αλγόριθμο που χρησιμοποιεί
τα δεδομένα στοιχεία και τους περιορισμούς του γρίφου
και προσδιορίζει τις δύο σωστές απαντήσεις.
