64 

 

καλύπτει  ο  επιλυτής  CP-SAT  σε  συνδυασμό  με  τη  γεννήτρια  πιθανοτήτων  του 

Αυτοματοποιημένου επιλυτή. Η επιλογή με βάση την πιθανότητα να υπάρχει νάρκη για κάθε 

μπλοκ  εκμεταλλεύεται  πλήρως  την  κατάσταση  του  ταμπλό  και  σίγουρα  επιφέρει  καλύτερα 

αποτελέσματα από την τυχαία επιλογή. 

 

3.7.1 Μοντελοποίηση του Προβλήματος 

 

Όταν οι βασικές στρατηγικές φτάσουν σε μια κατάσταση του ταμπλό που δε μπορούν 

να  επιλύσουν,  καλείται  η  συνάρτηση  μοντελοποίησης  σε  CSP  με  χρονική  πολυπλοκότητα 

O((n×m)

2

)  για  ταμπλό  n×m  διαστάσεων.  Με  είσοδο  την  κατάσταση  του  ταμπλό,  ξεκινά  η 

έκφραση  της  ως  τα  τρία  βασικά  κομμάτια  〈𝑋, 𝐷, 𝐶〉  του  CSP.  Το  μοντέλο  περιλαμβάνει  ως 

μεταβλητές 𝑋 τα μπλοκ άκρης [Εικόνα 3.17] τα οποία είναι όσα κλειστά μπλοκ γειτονεύουν 

με κάποιο αριθμό. Εισάγοντας μόνο τα μπλοκ άκρης περιορίζεται η αχρείαστη επέκταση του 

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

τις τιμές μηδέν και ένα εκφράζοντας την ύπαρξη (ή μη) της νάρκης. Το σύνολο των αριθμών 

επιβάλλουν περιορισμούς 𝐶 στα μπλοκ άκρης με τη μορφή: 

𝐶

𝑖

→ 𝑋

1

+ 𝑋

2

+. . . 𝑋

8

= 𝛭𝜀𝜏𝜌𝜂𝜏ή𝜍 𝛮𝛼𝜌𝜅ώ𝜈 

(3.8)

 

Σύμφωνα  με  την  εξίσωση  3.8,  κάθε  περιορισμός  περιέχει  έως  8  μεταβλητές  (επειδή 

μπορεί να έχει έως 8 γείτονες) και είναι γραμμική εξίσωση με βάση τις νάρκες που αναζητεί ο 

αριθμός.  Στην  Εικόνα  3.17  περιγράφεται  μία  κατάσταση  του  ταμπλό  με  πέντε  μεταβλητές 

𝑋

0−4

, πεδία ορισμού 𝐷

0−4

= {0,1} και πέντε αριθμούς που εκφράζονται ως περιορισμοί 𝐶

1−5

 

με τη γραμμική εξίσωση των μεταβλητών 𝑋

0−4

 και τον αντίστοιχο μετρητή. 

 

Εικόνα 3.17: Μοντελοποίηση μιας κατάστασης του Ναρκαλιευτή ως CSP. Σαν μεταβλητές ορίζονται τα μπλοκ άκρης, 

ως πεδίο ορισμού το 0 και 1 και σαν περιορισμοί οι γραμμικές εξισώσεις που επιβάλλουν οι αριθμοί.