Fifteen (Δεκαπέντε)

Η Δεκαπέντε (15-puzzle), που ονομάζεται επίσης Gem Παζλ, Boss παζλ, το παιχνίδι των Δεκαπέντε, Πλατεία Mystic και πολλά άλλα - είναι μια συρόμενη παζλ που αποτελείται από ένα πλαίσιο αριθμημένων τετράγωνα πλακίδια με τυχαία σειρά με λείπει ένα κεραμίδι. Ο γρίφος, αν 4 × 4 πλακάκια, το παζλ ονομάζεται 15-παζλ ή 16-παζλ που ονομάζεται, αντίστοιχα, για τον αριθμό των πλακιδίων και του αριθμού των χώρων.
Ο σκοπός του παζλ είναι να τοποθετήσετε τα κεραμίδια για (1-15) κάνοντας συρόμενες κινήσεις που χρησιμοποιούν το κενό. Το Δεκαπέντε είναι ένα κλασσικό πρόβλημα για αλγορίθμους μοντελοποίησης που αφορούν heuristics. Συνήθως χρησιμοποιούνται heuristics για αυτό το πρόβλημα περιλαμβάνουν μετρώντας τον αριθμό των άστοχες πλακιδίων και βρίσκοντας το άθροισμα των αποστάσεων των ταξί μεταξύ κάθε μπλοκ και τη θέση της στη διαμόρφωση του στόχου. Σημειώστε ότι και οι δύο είναι παραδεκτή, δηλαδή ποτέ δεν υπερεκτιμούν τον αριθμό των κινήσεων αριστερά, η οποία εξασφαλίζει βέλτιστη για ορισμένους αλγόριθμους αναζήτησης.