61 

 

Οι  πρώτοι  επιλυτές  για  το  Ναρκαλιευτή,  όπως  αυτός  του  Adamatzky  [15],  έκαναν 

αποκλειστικά  χρήση  ντετερμινιστικών  αλγορίθμων  για  την  εύρεση  των  μετέπειτα  ασφαλών 

κινήσεων. Ο Pedersen [13] επέκτεινε αυτές τις μεθόδους εισάγοντας τυχαία επιλογή όταν το 

σύνολο  διαθέσιμων  κινήσεων  είναι  κενό.  H  υλοποίηση  εξετάζει  ένα  μπλοκ  τη  φορά  και 

εξάγει συμπεράσματα με βάση την κατάσταση των γειτονικών του μπλοκ. Εφαρμόζονται δύο 

κύριες  στρατηγικές  με  χρονική  πολυπλοκότητα  O((n×m)

2

)  για  ταμπλό  n×m  διαστάσεων,  η 

σήμανση  ξεκάθαρων  ναρκών  και  η  αποκάλυψη  απόλυτα  ασφαλών  μπλοκ,  οι  οποίες  θα 

αναλυθούν στη συνέχεια. Σημαντική πτυχή και για τις δύο αποτελεί μία από τις ιδιότητες των 

στοιχείων  στη  λίστα  με  τα  μπλοκς,  οι  εναπομένουσες  νάρκες.  Όπως  παρουσιάζεται  στην 

Εικόνα 3.14, κάθε αριθμός κρύβει έναν εσωτερικό μετρητή που εκφράζει τον αριθμό ναρκών 

που  ψάχνει.  Με  κάθε  σήμανση  νάρκης,  οι  μετρητές  των  μπλοκ  που  την  περιβάλλουν 

μειώνονται κατά ένα. 

 

Εικόνα 3.14: Αναπαράσταση μεταβολής εσωτερικού μετρητή ναρκών για μπλοκ αριθμούς.

 

 

3.6.1 Σήμανση Ξεκάθαρων Ναρκών 

 

Επιλέγοντας  ένα  μπλοκ  που  περιέχει  αριθμό,  μπορούν  να  αντληθούν  πληροφορίες 

σχετικά με την κατάσταση που κρύβουν τα γειτονικά κλειστά μπλοκ. Κατά την  στρατηγική 

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

έχει μηδενικό εσωτερικό μετρητή αν ο αριθμός κλειστών γειτονικών μπλοκ είναι ίσος με τις 

νάρκες που ψάχνει [Αλγόριθμος 3.3]. Αν ισχύει αυτή η συνθήκη, τότε κάθε γειτονικό μπλοκ 

είναι  νάρκη  και  πρέπει  να  σημανθεί.  Για  τη  σήμανση,  πρέπει  να  βρεθεί  ο  δείκτης  του 

εξεταζόμενου  μπλοκ  και  να  μειωθούν  οι  μετρητές  των  γειτονικών  μπλοκ  καθώς  και  ο 

καθολικός μετρητής ναρκών. Στην Εικόνα 3.15, εξετάζονται τρία μπλοκ με αριθμούς 1,2 και 

3. Αρχικά, ο αριθμός 1 γειτονεύει μοναχά με ένα κλειστό μπλοκ οπότε αυτό είναι ξεκάθαρη 

νάρκη.  Γύρω  από  τη  σημαία,  μειώνονται  οι  εσωτερικοί  μετρητές  κατά  ένα.  Αυτό  σημαίνει 

πως ο αριθμός 2 πλέον ψάχνει για μία και μόνο νάρκη και αφού γειτονεύει με μία σημαία και 

ένα κλειστό μπλοκ, το κλειστό μπλοκ είναι νάρκη. Ομοίως, ο αριθμός 3 ψάχνει μία και μόνο 

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