Το ταξίδι του Αλόγου (Knight's Tour)

Υπενθύμιση: έχει ανέβει η αναθεώρηση 24 με μικρές διορθώσεις πάνω στο διερμηνευτή (λεπτομέρειες δηλαδή).

Ακολουθεί το πρόγραμμα knight Tour, όπου στόχος είναι να δίνουμε μια θέση σε μια άδεια σκακιέρα και να μετακινήσουμε ένα άλογο σε όλες τις θέσεις χωρίς να περάσουμε δεύτερη φορά από μια ίδια θέση. Υποχρεωτικά πρέπει να χρησιμοποιήσουμε BackTrack, να παίρνουμε πίσω κινήσεις αν δεν βγαίνει το μέτρημα. Το μέτρημα είναι απλό, βάζουμε 1 στη αρχική θέση και αυξάνουμε μια μεταβλητή Moves ή αν χρειαστεί την μειώνουμε και σβήνουμε βάζοντας μια μεγάλη τιμή πχ το 100 αρκεί.

Το ζήτημα είναι ότι αν δούλευε μόνο αυτό θα έπρεπε κάποτε να περιμένουμε χρόνια. Οι συνδυασμοί είναι 19,591,828,170,979,904. Οπότε πρέπει κάτι να γίνει πριν ξεκινήσει η τοποθέτηση του αλόγου, να έχουμε προετοιμάσει το έδαφος!

Χρειαζόμαστε μια συνάρτηση όπου θα δίνουμε τη τρέχουσα θέση του αλόγου και έναν αριθμό θέσης, από το 1 έως το 8. Αν το άλογο είναι σε κάποια θέση στο κέντρο της σκακιέρας υπάρχουν και οι οκτώ θέσεις. Αν είναι  όμως σε γωνία υπάρχουν μόνο δυο θέσεις. Έτσι η συνάρτηση μπορεί να γυρίσει το ζεύγος της νέας θέσης ή κενό. Το κενό εδώ είναι ο κενός πίνακας, ή κενό tuple. Ο κενός πίνακας ως σταθερά, στη Μ2000 συμβολίζεται με (,)  (δείτε το κόμμα ανάμεσα στις παρενθέσεις).

Την KnightMove() την βάζουμε τοπική συνάρτηση στη τελική όπως θα δούμε στο τέλος.

Δείτε ότι παίρνει τρεις μεταβλητές, η x και η αρχική θέση του αλόγου όπου το w=1 και h=1 είναι η θέση a1, η κάτω αριστερή γωνία από την μεριά των άσπρων.

Η συνάρτηση χρησιμοποιεί τέσσερις μεταβλητές. Αν ο x είναι μονός τότε αλλάζουμε τα a και b, μεταξύ τους. Αν το x είναι μεγαλύτερο του 2 αλλάζουμε πρόσημο στο p, και συνεχίζουμε στην επόμενη If (αν η πρώτη δεν βγει αληθής δεν συνεχίζει η ροή στις επόμενες). Αν είναι το x μεγαλύτερο του 4 τότε αλλάζουμε τα z και p (άρα το z γίνεται -1 και το p γίνεται 1). Αν το x είναι μεγαλύτερο του 6 τότε κάνουμε και το p αρνητικό. Μετά προσθέτουμε τα z*a και p*b στα w και h. Οι τυπικές παράμετροι περνούν με τιμή στην Μ2000 εκτός αν βάλουμε το & στην αρχή του ονόματος και στην κλήση δώσουμε επίσης μεταβλητή με το & στην αρχή (αυτό είναι το πέρασμα με αναφορά).

Στο τέλος ελέγχουμε αν η θέση που θα πάει το άλογο είναι εκτός σκακιέρας. Αν δεν είναι εκτός τότε δίνουμε το ζεύγος τιμών (w, h) αλλιώς δίνουμε το κενό (,)

Function KnightMove(x,w,h) {
    a=2:b=1:z=1:p=1
    if x mod 2=1 then swap a,b
    if x>2 then p-! : if x>4 then swap z, p : if x>6 then p-!
    w+=z*a
    h+=p*b
    if w>=1 and w<=8 and h>=1 and h<=8 then =(w, h) else =(,)
}

Παρατηρούμε ότι το x δεν λειτουργεί κυκλικά, κάπου δηλαδή πηδάει τεταρτημόριο, το οποίο το συνεχίζει αργότερα. Κάνει μια κίνηση Ζήτα, 1ο, 2ο, 4ο, 3ο.

Το πρόγραμμα βγάζει τις θέσεις του αλόγου στη σκακιέρα

Knight's Tour from a1

a1->b3->a5->b7->d8->f7->h8->g6->

h4->g2->e1->c2->a3->b1->d2->f1->

h2->g4->h6->g8->e7->c8->a7->b5->

c7->a8->b6->a4->b2->d1->f2->h1->

g3->h5->g7->e8->f6->h7->f8->d7->

b8->a6->b4->a2->c1->e2->g1->h3->

g5->e6->f4->d3->c5->e4->c3->d5->

e3->c4->d6->f5->d4->f3->e5->c6

Knight's Tour from h1

h1->g3->h5->g7->e8->c7->a8->b6->

a4->b2->d1->f2->h3->g1->e2->c1->

a2->b4->a6->b8->d7->f8->h7->g5->

f7->h8->g6->h4->g2->e1->c2->a1->

b3->a5->b7->d8->c6->a7->c8->e7->

g8->h6->g4->h2->f1->d2->b1->a3->

b5->d6->c4->e3->f5->d4->f3->e5->

d3->f4->e6->c5->e4->c3->d5->f6

Knight's Tour from a8

a8->b6->a4->b2->d1->f2->h1->g3->

h5->g7->e8->c7->a6->b8->d7->f8->

h7->g5->h3->g1->e2->c1->a2->b4->

c2->a1->b3->a5->b7->d8->f7->h8->

g6->h4->g2->e1->f3->h2->f1->d2->

b1->a3->b5->a7->c8->e7->g8->h6->

g4->e3->f5->d6->c4->e5->c6->d4->

e6->c5->d3->f4->d5->f6->e4->c3

Knight's Tour from h8

h8->g6->h4->g2->e1->c2->a1->b3->

a5->b7->d8->f7->h6->g8->e7->c8->

a7->b5->a3->b1->d2->f1->h2->g4->

f2->h1->g3->h5->g7->e8->c7->a8->

b6->a4->b2->d1->c3->a2->c1->e2->

g1->h3->g5->h7->f8->d7->b8->a6->

b4->d3->c5->e6->f4->d5->f6->e4->

d6->f5->e3->c4->e5->c6->d4->f3

Για τη διευκόλυνσή μας, βελτιστοποιούμε τον αλγόριθμο για ένα 4Χ4 τμήμα όπου μπαίνει το άλογο. Αν επιλέξουμε ένα άλλο τότε το γυρνάμε στο συμμετρικό του (κατά ύψος και κατά πλάτος) . Παρατηρήστε το αποτέλεσμα παραπάνω. Σε κάθε περίπτωση ο αλγόριθμος υπολόγισε τις θέσεις από την ίδια θέση! Απλά έκανε αλλαγή στα ονόματα και στους αριθμούς και έτσι πήραμε το σωστό "καθρέφτισμα".

Ο αλγόριθμος κρατάει έναν πίνακα Moves() που έχει τιμές από το (1,1) ως το (8,8). Όταν τελειώσει το γέμισμα υπάρχουν οι αριθμοί από το 1 έως το 64. Σαρώνουμε το πίνακα και φτιάχνουμε μια κατάσταση όπου το κλειδί είναι ο αριθμός και η τιμή είναι το a1 (αν έχουμε το 1,1). Το κάνουμε αυτό για να δώσουμε μια εντολή ταξινόμησης κλειδιού ως αριθμός. Οπότε μετά την ταξινόμηση περνάμε από όλα τα στοιχεία, από το 1 έως το 64. Και έτσι φτιάχνουμε την εξαγωγή παραπάνω. Χρησιμοποιώ ένα έγγραφο το export$ το οποίο αν και μοιάζει με αλφαριθμητικό εσωτερικά έχει ένα αντικείμενο το οποίο κρατάει χωριστά τις παραγράφους, με συνέπεια να μπορούμε προσθέτουμε πολύ εύκολα παραγράφους. Το σύμβολο = δεν κάνει εκχώρηση τιμής στο έγγραφο αλλά προσθήκη. Για να σβήσουμε το έγγραφο πρέπει να χρησιμοποιήσουμε το Clear ή Καθαρό, ή να φορτώσουμε ένα Έγγραφο από το δίσκο (μπορούμε να κάνουμε και προσθήκη κειμένου από αρχείο με μια εντολή).

Στην επιστροφή της KnightTour$() επιστρέφουμε το έγγραφο ως αλφαριθμητικό (το αντικείμενο διαγράφεται εσωτερικά).

Αυτό είναι το κύριο πρόγραμμα. Φτιάχνει ένα δικό του έγγραφο και ρίχνει μια έκφραση αλφαριθμητική (σε πολλές γραμμές). Το { } χρησιμοποιείται εκτός από μπλοκ εντολών και για αλφαριθμητικά με παραγράφους. Εδώ μας ενδιαφέρουν οι αλλαγές γραμμών. Δείτε ότι στην έκφραση καλούμε τέσσερις φορές το KnightTour$(). Την πρώτη φορά δεν βάζουμε τιμές. Εξ ορισμού έχουν από 1 η κάθε μία. Στη Μ2000 αν δεν βάλουμε τιμή σε μεταβλητή θα βγει λάθος. Στους πίνακες δεν ισχύει αυτό, γιατί μπαίνει τιμή εξ ορισμού η Empty (χωρίς τιμή) η οποία μπορεί να διαβαστεί και σαν 0 ή σαν "" (κενό αλφαριθμητικό). Στις μεταβλητές ο τύπος δεν αλλάζει οπότε χρειάζεται να έχει τύπο, δηλαδή να πάρει τιμή. Μόνο σε ειδικές εντολές ορισμού μεταβλητών αν θέλουμε δεν δίνουμε τιμή, και εκεί μπαίνει η εξ ορισμού. Ο τύπος εξ ορισμού είναι ο Double για αριθμητικές. Τα αλφαριθμητικά είναι String.

Στο κύριο πρόγραμμα  έχουμε δυο εντολές στο τέλος. Μια γράφει στο πρόχειρο το κείμενο του εγγράφου και μια άλλη το εμφανίζει στην οθόνη (κονσόλα) με έλεγχο ολίσθησης, όπου κάθε 3/4 του ύψους της κονσόλας ολίσθησης περιμένει για πάτημα διαστήματος ή πλήκτρου ποντικιού.

Document ex$
ex$= {Knight Tour from a1
}+ KnightTour$()+{Knight Tour from h1
}+ KnightTour$(8,1)+{Knight Tour from a8
}+KnightTour$(1, 8)+{Knight Tour from h8
}+KnightTour$(8, 8)
Clipboard ex$
Report ex$

Ας δούμε σημεία του KnigtTour$()

Υπάρχει ένας δεύτερος πίνακας το Board() πάλι από (1,1) έως (8,8), αλλά εδώ μας ενδιαφέρει σε κάθε στοιχείο να βάλουμε ένα στοιχείο Σωρός (Stack). 

Επίσης υπάρχει το f, ένας σωρός (ειδική στοίβα) με τιμές 1,2,3,4,5,6,7,8 οι οποίες όμως μπορούν να μετατοπιστούν και για το λόγο αυτό χρησιμοποιούμε το σωρό. Η stackitem(f, k) διαβάζει από το αντικείμενο f το k στοιχείο (ως αριθμό, αν είναι αλφαριθμητικό θα πάρουμε σφάλμα, οι σωροί παίρνουν τα πάντα ακόμα και άλλους σωρούς).

Έχουμε ένα τριπλό For (με δυο φωλιασμένα) τα οποία χρησιμοποιούμε με την απλοποίηση χωρίς αγκύλες, με το τέλος να το δηλώνει το Next. Εδώ δεν βάζουμε στη Next την αντίστοιχη μεταβλητή (αν την  βάλουμε την ελέγχει ο διερμηνευτής).

H s μέσα στο πρώτο φωλιασμένο for, παίρνει έναν νέο σωρό. Οι μεταβλητές που κρατάνε έναν καταχωρητή στοιχείων όπως ο σωρός είναι δείκτες σε αντικείμενα. Αυτό σημαίνει ότι αν τους περάσουμε με τιμή σε μια κλήση, στην ουσία το αντικείμενο είναι εκτεθειμένο σε αλλαγές, εκτός από την αλλαγή του δείκτη (αν συμβεί αλλαγή δείκτη τότε το αρχικό θα δείχνει ακόμα αυτό που πέρασε στη κλήση). Επιπλέον μπορούν δυο ή περισσότεροι δείκτες να δείχνουν το ίδιο αντικείμενο. Επίσης μπορούμε να αποθηκεύσουμε το δείκτη σε πίνακα. Πάμε λοιπόν στο δεύτερο φωλιασμένο For. Εκεί καλούμε την KnightMove με τη τιμή που μας δίνει ο σωρός f για το k, και τις τιμές i και j. Την επιστροφή την γράφουμε σε μια μεταβλητή m. Εδώ θα πάρουμε ή έναν πίνακα με δυο στοιχεία (δηλαδή μήκος ως μονοδιάστατου 2), ή έναν κενό (μήκος=0). Για το λόγο αυτό κοιτάμε αν το Len(m) είναι>1 (και μεγαλύτερο του 0 θα έπαιζε). Τότε αν έχουμε πάρει όντως μια θέση (ζευγάρι dyo τιμών) στη σκακιέρα την προσθέτουμε στο stack s. Η δομή Stack δείκτης_σε_σωρό { } βάζει τον σωρό s ως τρέχον σωρό και αποκρύπτει τον μέχρι τώρα τρέχον σωρό. Στην έξοδο επιστρέφει ο τρέχον σωρός του τμήματος. Έτσι μέσα στις αγκύλες, η Data m προσθέτει στο τέλος του σωρού το m - λειτουργία FIFO, το διάβασμα γίνεται από τη κορυφή, η Push βάζει στη κορυφή, η Data στο πυθμένα, ή τέλος).

Δείτε τώρα τι κάνουμε μετά τη καταχώρηση των έως 8 θέσεων στο s, το γράφουμε στο Board(i,j). Έτσι ο δείκτης του σωρού πάει εκεί (ένας σωρός με πίνακες), Και σε κάθε αλλαγή οριζόντιας γραμμής (μετά το δεύτερο Next), κάνουμε αντιστροφή των στοιχείων του f, αυτό γίνεται μόλις βάλουμε το f στη θέση του τρέχον και δώσουμε την εντολή Shift 1, -8, το οποίο βάζει τα στοιχεία ανάποδα (πχ αν είχαν την καλή σειρά θα πάρουν την ανάποδη 8,7,6,5,4,3,2,1).

For j=1 to 8 :For i=1 to 8
s=stack
For k=1 to 8
    m=KnightMove(stackitem(f, k),i, j)
    if len(m)>1 then Stack s {data m}
   Next : Board(i,j)=s : Next
  stack f {shift 1,-8}
Next

Τώρα έχουμε ένα πίνακα Board() όπου σε κάθε (i,j) θέση αντιστοιχούν μια σειρά θέσεων που μνορεί να πάει το άλογο. Έτσι δεν χρειάζεται να χρησιμοποιούμε την συνάρτηση πια. Έχουμε έτοιμες τις επόμενες θέση για κάθε θέση στη σκακιέρα. Ακόμα όμως δεν είμαστε καλοί!

Θέλουμε όταν εξετάζουμε μια θέση να κοιτάμε πρώτα τις θέσεις που είναι στις άκρες και τις πλευρές, όπου αυτές έχουν λιγότερες από 8 θέσεις προορισμού σε σχέση με τις κεντρικές θέσεις.

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

Δείτε τι κάνουμε: Πρώτα παίρνουμε αντίγραφο του δείκτη στο Board(i,j) στο s. Αν έχουμε δυο στοιχεία δεν τα ταξινομούμε! Είναι οι γωνίες. Μόνο οι γωνίες έχουν δυο θέσεις για προορισμό ισοδύναμε σε ότι έχει να κάνει με τις θέσεις του κάθε προορισμού σε προορισμούς!

Μετά φτιάχνουμε μια ουρά! Η ουρά (queue) στη Μ2000 είναι μια ειδική κατάσταση. Εδώ όταν ταξινομούμε τα στοιχεία της δεν έχουμε αλλαγή θέσεων όταν το κλειδί είναι ίδιο. Επίσης, μόνο σε αυτόν τον τύπο κατάστασης μπορούμε να έχουμε όμοια κλειδιά (η κανονική κατάσταση λέγεται και λίστα έχει μοναδικά κλειδιά. και αν πάμε να βάλουμε ίδιο βγαίνει λάθος).

Διαβάζουμε λοιπόν όλα τα k στοιχεία του s με την stackitems)s, k) (οι σωροί ξεκινούν από το 1), στο m. Βάζουμε στο τέλος της ουράς με την Append, με κλειδί το μήκος Len() του στοιχείου της Board() όπου οι θέσεις βγαίνουν από τις τιμές στο 0 και στο 1 (τα touple έχουν βάσει το 0).. Ο αριθμός θα γίνει κλειδί στην ουρά, και τιμή θα πάρει ένα αντίγραφο του δείκτη m. Μόλις τελειώσει ο εμπλουτισμός της ουράς κάνουμε τη ταξινόμηση με χρήση του κλειδιού ως αριθμός. Αν είχαμε κλειδιά πχ Α50 και Α100 το Α50 θα έρχονταν πρώτο, ενώ αν ήταν ταξινόμηση ως κείμενο θα έρχονταν δεύτερο αφού πάει ανά χαρακτήρα ο έλεγχος. Στη ταξινόμηση ως αριθμός τα κλειδιά σπάνε σε μέρη αλφαριθμητικά και αριθμητικά. Εδώ έχουμε αριθμητικό (ταξινομεί ακόμα και με δεκαδικά σωστά). Τα κλειδιά ακόμα και τα αριθμητικά γίνονται αλφαριθμητικά στην ουρά.

Μετά την ταξινόμηση φτιάχνουμε ένα νέα σωρό στην s, και με μια Stack s { } με μια For Next μέσα βάζουμε τα στοιχεία με την data. Δείτε ότι την ουρά την διατρέχουμε εδώ με αριθμό k από το 0 και στο so() βάζουμε το ! που δηλώνει ότι δίνουμε αριθμό σειράς και όχι κλειδί. Οι λίστες και οι ουρές, οι δυο Καταστάσεις, έχουν πίνακα κατακερματισμού εσωτερικά για να βρίσκουν άμεσα σε O(1) το ζητούμενο ανεξάρτητα με το μέγεθος σε στοιχεία της δομής. Οι ουρές για λίγα στοιχεία έχουν ικανοποιητική ταξινόμηση και διατηρούν την σειρά στα όμοια κλειδιά, ενώ η λίστες έχουν quicksort, πολύ γρήγορη, δεν έχουν όμοια κλειδιά).

For i=1 to 8 :For j=1 to 8
s=Board(i, j)
if len(s)>2 then
    so=queue
    For k=1 to len(s)
        m=stackitem(s, k)
        Append so, Len(Board(m#val(0), m#val(1))) :=m
    Next
    sort ascending so as number
    s=stack
    stack s {for k=0 to len(so)-1:data so(k!):next}
    Board(i,j)=s
end if
Next : Next

Τώρα έχουμε την Board() με ταξινομημένους σε κάθε θέση τους προορισμούς, από τις θέσεις με λίγους προορισμούς προς τις θέσεις με τους πολλούς προορισμούς. Θέσεις με ίδιο αριθμό προορισμών δεν έχουν αλλάξει σειρά.

Πριν μπούμε στην βασική ή κεντρική επανάληψη, πρέπει να καθορίσουμε αρχικές συνθήκες. Πρώτα στην s θα πάρουμε τον σωρό (τις θέσεις προορισμού) από το σημείο (StartW, StartH), το αρχικό σημείο. Έχουμε την n με μηδέν τιμή (θα δούμε γιατί έχει μηδέν μετά).

Έχουμε επίσης την BackTrack ένα σωρό για να κρατάμε τις θέσεις που περνάμε. Το πώς θα το δούμε πιο μετά. Η Moves ξεκινάει από το 1, και βάζουμε στο Moves() στην πρώτη θέση το 1.

s= Board(StartW, StartH)
n=0
BackTrack=Stack
Moves=1
Moves(StartW, StartH)=1

Τώρα είμαστε έτοιμοι να ξεκινήσουμε. Μπαίνουμε σε μια Repeat Until μέχρι η Moves να γίνει final (το 64 για 8*8 σκακιέρα). Δείτε οτι η πρώτη εντολή αυξάνει κατά ένα την n. Θυμηθείτε ότι τους σωρούς μέσα στην Board() τους διαβάζουμε από το 1. Επίσης έχουμε ήδη την s με το περιεχόμενο της πρώτης θέσης (θέση εκκίνησης του αλόγου).

Repeat
n++
------
until Moves=final

Μετά την n++ θέλει προσοχή. Έχουμε μια while με συνθήκη το n>len(s). Αυτό θα συμβεί όταν έχουμε πάει σε όλους τους προορισμούς και δεν βρήκαμε άδεια θέση. Δεν υπάρχει περίπτωση να είμαστε στην 64 θέση και να περάσουμε από εκεί γιατί θα έχουμε βγει από την Repeat Until.

Μετά θα πάρουμε τη θέση στο n από το σωρό s, στην m (που είναι δείκτης σε πίνακα). Θα εξάγουμε τα w και h, τις θέσεις, και θα δούμε αν η Moves(w,h) έχει τιμή μεγαλύτερη από την Moves. (βάζουμε το 100 για να σημαίνει άδειο στην αρχή).  Αν δεν βρούμε κενή θέση στο (w, h) τότε πάμε για άλλο n, το επόμενο. 

Repeat
n++
While n>len(s) {
.................
}
m=stackitem(s, n)
w=m#val(0)
h=m#val(1)
if Moves(w, h)>=Moves then
--------------
end if
until Moves=final

Ήρθε η ώρα να δούμε την πρώτη περίπτωση, ότι η θέση υπάρχει στο (w,h). Έχουμε μια If Then Else End If όπου ελέγχουμε αν η Moves είναι μικρότερη από τη last. H last είναι η προηγούμενη από την final, η 63. Αν είμαστε στην 63 θα πάμε στο δεύτερο σκέλος, μετά την else, θα κάνουμε την moves 64 και έχουμε τελειώσει γιατί θα βγούμε μετά από το  

if Moves(w, h)>=Moves then
    if Moves<last then
         -----
    else
        Moves++
        Moves(w,h)=Moves
    end if
end if

Τώρα μας ενδιαφέρει τι κάνουμε στο Moves<last. Θυμάστε ότι από το s πήραμε αντίγραφο του δείκτη στο m από τη θέση n με την stackitem(s,n) και από το m βγάλαμε τα w και h, όπου σε αυτό το σημείο βρήκαμε ότι έχουμε άδεια θέση. Πάμε λοιπόν να δούμε τι έχουμε στο Board(w, h). Πρώτα θα πάρουμε αντίγραφο δείκτη στο s1. και ξεκινάμε με ένα ii=-1

Μπαίνουμε σε μια επανάληψη For (εδώ έχουμε τις αγκύλες) για κάθε i από 1 έως μήκος του s1.

Εντός της For βγάζουμε για κάθε i στο s1 ένα δείκτη m1 θέσης προορισμού. Κοιτάμε αν στη θέση αυτή έχουμε κενό, και αν ναι τότε βάζουμε στο ii το i-1. δηλαδή αν το βρούμε στη θέση 1 του s1, θα βάλουμε στο ii=0. Αν δεν βρούμε καμία θέση τότε θα μείνει το ii με την αρχική τιμή -1. Δείτε ότι αν βρούμε μια θέση κάνουμε έξοδο από την For με την Exit (σε For Next θα βάζαμε Exit For)

Ελέγχουμε λοιπόν στην επόμενη if μετά την δομή For αν το ii>=0. Αν είναι -1 τότε εγκαταλείπουμε,. πάμε για άλλο n (στο repeat υπάρχει το n++ ως άμεση εντολή), πάμε για άλλο προορισμό. Δηλαδή βρήκαμε κενή θέση αλλά είδαμε ότι αυτή δεν έχει άλλη κενή θέση, και αφού δεν είναι η προτελευταία δεν μας κάνει. Αν πάμε εκεί δεν θα μπορούμε να πάμε αλλού, άρα δεν θα φτάσουμε στην final (64). Αυτό που κάνουμε λέγεται Look Ahead, κοίταγμα μπροστά, μια μόνο κίνηση.

Αν όντως υπάρχει δυνατότητα να πάμε αλλού τότε αυξάνουμε την Moves κατά ένα, βάζουμε στο (w,h) το νούμερο της Moves, βάζουμε στο σωρό BackTrack το τρέχον n και s με την Push, άρα το τελευταίο που μπήκε θα βγει πρώτο (LIFO), και αλλάζουμε δείκτη στην s δίνοντας την s1 και στην n δίνοντας ii (το οποίο n θα αλλάξει με το n++ στην Repeat, το ξέρουμε γιατί το Moves<last όταν μπήκαμε στο if και το πολύ να γίνει last, αλλά δεν θα γίνει final αφού last=final-1)

s1=Board(w, h) :ii=-1
for i=1 to len(s1){m1=stackitem(s1, i) :if Moves(m1#val(0),m1#val(1))>moves then ii=i-1 : exit
}
if ii>=0 then
    Moves++
    Moves(w,h)=Moves
    Stack BackTrack {Push n, s}
    s=s1: n=ii
end if

Και τώρα πάμε στην περίπτωση που μετά το n++ έχουμε στο While τη συνθήκη n>Len(s) αληθής.

Για ασφάλεια αν η BackTrack δεν έχει στοιχεία, δηλαδή έχει μήκος μηδέν θα γράψουμε ένα Break και θα εκτελέσουμε την Break που σπάει όλες τις φωλιασμένες επαναλήψεις μέχρι το τμήμα ή συνάρτηση που εκτελέστηκε. Η συνάρτηση θα γυρίσει κενό αλφαριθμητικό (εκτός αν είχαμε δώσει κάποια τιμή, στη Μ2000 η επιστροφή τιμής δεν κάνει τερματισμό κλήσης της συνάρτησης, μπορούμε να εκτελέσουμε και άλλες εντολές).

Μετά τον έλεγχο ασφαλείας, μειώνουμε την Moves, και ανοίγουμε το BackTrack και σηκώνουμε τα s και n. Σηκώνουμε (pop) σημαίνει ότι τα βγάζουμε από το σωρό. (η StackItem() διαβάζει τα στοιχεία χωρίς να τα βγάλει από το σωρό). Ο σωρός μας έχει  μια σειρά δυο διαφορετικών στοιχείων, το πρώτο ένας σωρός και το δεύτερο το n. Στην πράξη ο κάθε σωρός επειδή είναι δείκτης υπάρχει μια φορά. Ο σωρός BackTrack κρατάει τους δείκτες των σωρών όχι αντίγραφα αυτών. Επειδή δεν τους πειράζουμε τους σωρούς, δηλαδή να γράψουμε δεν έχουμε ζήτημα ακεραιότητας δεδομένων. Μόνο το BackTrack πειράζουμε, βάζοντας και βγάζοντας στοιχεία. Από τα s και n, διαβάζουμε το m, το πίνακα με τιμές για την θέση που θέλουμε να καθαρίσουμε, να πάρουμε πίσω δηλαδή, και βάζουμε την τιμή HighValue (to 100), στη Moves(). Στο repeat until, o πίνακας Board(), oi σωροί ως τιμές του, και οι πίνακες ως τιμές σε κάθε σωρό δεν αλλάζουν, απλά διαβάζονται. Αυτό που αλλάζει είναι ο BackTrack σωρός και ο πίνακας Moves() όπου θέλουμε να έχει το αποτέλεσμα. Τέλος αυξάνουμε το n κατά ένα,  γιατί ήδη το n έχει εξεταστεί. Αν το n είναι μεγαλύτερο από το μήκος του νέου s, τότε συνεχίζουμε να πετάμε από το BackTrack θέσεις. Αλλιώς πάμε για έξοδο από τη While (η While γράφεται και με While / End While χωρίς μπλοκ)

While n>len(s) {
    if Len(BackTrack)=0 then Print "Break", moves : Break
    Moves--
    Stack BackTrack {Read s, n}
    m=stackitem(s, n)
    Moves(m#val(0), m#val(1))=HighValue
    n++
}

Έτσι στην έξοδο από το While έχουμε το επόμενο n για μια θέση στο τρέχον s που δεν έχει εξεταστεί.

Κάποια στιγμή τελειώνει το repeat until και πάμε στη διαδικασία να φτιάξουμε τη διαδρομή. Επειδή έχουμε κάνει για λόγους βελτιστοποίησης μεταφορά της αρχικής θέσης στο τεταρτημόριο κάτω δεξιά, (δουλεύει με τα λιγότερα βήματα), και έχουμε κρατήσει σε δυο boolean μεταβλητές την αλλαγή, κάνουμε την αντίστροφη ενέργεια για να καθρεφτίσουμε το πίνακα Moves(). Ουσιαστικά αντί να καθρεφτίσουμε αυτόν αλλάζουμε τους επικεφαλίδες των αξόνων, και έτσι έχουμε το ίδιο αποτέλεσμα.

Το τελικό πρόγραμμα:

Function KnightTour$(StartW=1, StartH=1){
    def boolean swapH, swapV=True
    if startW<=4 then swapH=true: StartW=8+1-StartW
    if startH>4 then swapV=False: StartH=8+1-StartH
    Let final=8*8, last=final-1, HighValue=final+1
    Dim Board(1 to 8, 1 to 8), Moves(1 to 8, 1 to 8)=HighValue
    f=stack:=1,2,3,4,5,6,7,8
    if 8-StartW=2 and StartH=2 then stack f {shift 1,-8}
    Function KnightMove(x,w,h) {
        a=2:b=1:z=1:p=1
        if x mod 2=1 then swap a,b
        if x>2 then p-! : if x>4 then swap z, p : if x>6 then p-!
        w+=z*a
        h+=p*b
        if w>=1 and w<=8 and h>=1 and h<=8 then =(w, h) else =(,)
    }
    For j=1 to 8 :For i=1 to 8
    s=stack
    For k=1 to 8
        m=KnightMove(stackitem(f, k),i, j)
        if len(m)>1 then Stack s {data m}
    Next : Board(i,j)=s : Next
           stack f {shift 1,-8}
    Next
    For i=1 to 8 :For j=1 to 8
    s=Board(i, j)
    if len(s)>2 then
        so=queue
        For k=1 to len(s)
            m=stackitem(s, k)
            Append so, Len(Board(m#val(0), m#val(1))) :=m
        Next
        sort ascending so as number
        s=stack
        stack s {for k=0 to len(so)-1:data so(k!):next}
        Board(i,j)=s
    end if
    Next : Next
    s= Board(StartW, StartH)
    n=0
    BackTrack=Stack
    Moves=1
    Moves(StartW, StartH)=1
    Repeat
    n++
    While n>len(s) {
        if Len(BackTrack)=0 then Print "Break", moves : Break
        Moves--
        Stack BackTrack {Read s, n}
        m=stackitem(s, n)
        Moves(m#val(0), m#val(1))=HighValue
        n++
    }
    m=stackitem(s, n)
    w=m#val(0)
    h=m#val(1)
    if Moves(w, h)>=Moves then
        if Moves<last then
        s1=Board(w, h) :ii=-1
        for i=1 to len(s1){m1=stackitem(s1, i) :if Moves(m1#val(0),m1#val(1))>moves then ii=i-1 : exit
        }
        if ii>=0 then
            Moves++
            Moves(w,h)=Moves
            Stack BackTrack {Push n, s}
            s=s1: n=ii
        end if
        else
            Moves++
            Moves(w,h)=Moves
        end if
    end if
    until Moves=final
    Document export$
    Inventory Tour
    letters=stack:="a","b","c","d","e","f","g","h"
    f=stack:=1,2,3,4,5,6,7,8
    if swapV Else stack f {Shift 1,-8}
    if swapH then stack letters {Shift 1,-8}
    For j=1 to 8:For i=1 to 8
        Append Tour, Moves(i,j) :=stackitem$(letters, i)+str$(stackitem(f, j),"")
    Next : Next
    Sort ascending Tour as number
    one=each(Tour)
    While one {
        export$=Eval$(one)
        if not one^=last then export$="->"
        If (one^+1) mod 8=0 then
        export$={
        }
        End if
    }
    =export$
}
Document ex$
ex$= {Knight's Tour from a1
}+ KnightTour$()+{Knight's Tour from h1
}+ KnightTour$(8,1)+{Knight's Tour from a8
}+KnightTour$(1, 8)+{Knight's Tour from h8
}+KnightTour$(8, 8)
Clipboard ex$
Report ex$

Και παρακάτω το πρόγραμμα πειραματισμού. Μοιάζει με το πάνω, αλλά εδώ με ενδιέφερε να βγάλω για κάθε αρχική θέση τον αριθμό κινήσεων (ακόμα και αυτών που πήρε πίσω). Εδώ αντί για συνάρτηση έχω τμήμα Experiment. Με αυτό έκανα έλεγχο όλες τις θέσεις Δείτε ότι περνάω στοιχείο πίνακα με αναφορά (γίνεται σε κλήσεις τμημάτων και κανονικών συναρτήσεων και συναρτήσεων λάμδα, αλλά όχι ρουτινών και απλών συναρτήσεων - αυτές που φτιάχνονται με το Συνάρτηση Τέλος Συνάρτησης, είναι οι απλές συναρτήσεις). Το στοιχείο γράφεται στην mmm, και στο τέλος κλήσης, αντιγράφεται στο πίνακα (είναι μια λειτουργία copy in copy out). Με αυτό τον τρόπο δεν κλειδώνει ο πίνακας, και αν αλλάξουμε μέγεθος, τότε η επιστροφή τιμής στο πίνακα δεν βγάζει λάθος απλά χάνεται η τιμή. Τέτοιο σύστημα copy in copy out, έχουν και οι στατικές μεταβλητές. Τα στοιχεία πίνακα και οι στατικές δεν ανήκουν στο λίστα μεταβλητών για να παραστούν με αναφορά όπως για παράδειγμα μπορούμε να περάσουμε ολόκληρο πίνακα.με αναφορά. Η Μ2000 περνάει πίνακες και σαν τιμές, αλλά  οι τυχόν δείκτες σε τιμές του θα αντιγραφούν σαν δείκτες. Μόνο τα αντικείμενα Ομάδα, σε πίνακα, αντιγράφονται αν δεν έχουν φτιαχτεί δείκτες σε αυτές τις ομάδες. Έτσι η αντιγραφή πίνακα θεωρείται ρηχή αντιγραφή. Αντίγραφο σωρού βγάζουμε με την Σωρός(), έτσι η Stack(s) βγάζει ένα νέο σωρό με ρηχή αντιγραφή με ότι΄έχει ο s. Ομοίως για tuple έχουμε το Cons(), με μια παράμετρο, ενώ με πολλές ενώνει πολλούς πίνακες σε έναν νέο. Οι καταστάσεις δεν έχουν εντολές για πρόσθεση.Πρέπει να διατρέξουμε μία και να προσθέσουμε στοιχεία που διαβάζουμε σε άλλη.

module Experiment(StartW=1, StartH=1, &mmm){
    Global ww=8, hh=8
    def boolean swapH, swapV=True
    if startW<=ww div 2 then swapH=true: StartW=ww+1-StartW
    if startH>hh div 2 then swapV=False: StartH=hh+1-StartH
    Form 80, 32
    Let final=ww*hh, last=final-1, HighValue=final+1
    Dim Board(1 to ww, 1 to hh), Moves(1 to ww, 1 to hh)=HighValue
    f=stack:=1,2,3,4,5,6,7,8
    if ww-StartW=2 and StartH=2 then stack f {shift 1,-8}
    Function KnightMove(x,w,h) {
        a=2:b=1:z=1:p=1
        if x mod 2=1 then swap a,b
        if x>2 then p-! : if x>4 then swap z, p : if x>6 then p-!
        w+=z*a
        h+=p*b
        if w>=1 and w<=ww and h>=1 and h<=hh then
            =(w, h)
        else
            =(,)
        end if
    }
    For j=1 to hh
    For i=1 to ww
    s=stack
    For k=1 to 8
        m=KnightMove(stackitem(f, k),i, j)
        if len(m)>1 then Stack s {data m}
    Next
    Board(i,j)=s
    Next
           stack f {shift 1,-8}
    Next
    For i=1 to ww
    For j=1 to hh
    s=Board(i, j)
    if len(s)>2 then
    so=queue
    For k=1 to len(s)
    m=stackitem(s, k)
    Append so, Len(Board(m#val(0), m#val(1))) :=m
    Next
    sort ascending so as number
    s=stack
    stack s {
        for k=0 to len(so)-1
            data so(k!)
        next
    }
    Board(i,j)=s
    end if
    Next
    Next
    Print "Done"
    s= Board(StartW, StartH)
    n=0
    BackTrack=Stack
    Moves=1
    Moves(StartW, StartH)=1
    mstep=10
    mm=mstep
    mmm=0
    Repeat
    n++
    While n>len(s) {
        if Len(BackTrack)=0 then Print "Break", moves : Break
        Moves--
        Stack BackTrack {Read s, n}
        m=stackitem(s, n)
        Moves(m#val(0), m#val(1))=HighValue
        n++
    }
    m=stackitem(s, n)
    w=m#val(0)
    h=m#val(1)
    if Moves(w, h)>=Moves then
        if Moves<last then
        s1=Board(w, h) :ii=-1
        for i=1 to len(s1){m1=stackitem(s1, i) :if Moves(m1#val(0),m1#val(1))>moves then ii=i-1 : exit
        }
        if ii>=0 then
            Moves++
            Moves(w,h)=Moves
            Stack BackTrack {Push n, s}
            s=s1: n=ii
            mm--
        end if
        else
            Moves++
            Moves(w,h)=Moves
            mmm+=mm
            mm=0
        end if
    end if
    if mm Else
        cls
        Print "Moves:";Moves
        sj=hh: sj1=1: if swapV then swap sj, sj1
        si=1: si1=ww: if swapH then swap si, si1
        For j=sj to sj1: Print :For i=si to si1
            Print If(Moves(i,j)<=Moves->Moves(i,j), 0),
        Next : Next
        Print
        mm=mstep
        mmm+=mm
        Print mmm
        refresh 10000
    end if
    if mmm>1000 then mmm=-1: exit
    until Moves=final
        cls
        Print "Moves:";Moves
        sj=hh: sj1=1: if swapV then swap sj, sj1
        si=1: si1=ww: if swapH then swap si, si1
        For j=sj to sj1: Print :For i=si to si1
            Print If(Moves(i,j)<=Moves->Moves(i,j), 0),
        Next : Next
        Print
        Print mmm
        Print "DONE"
        refresh 5000
}
dim res(1 to 8, 1 to 8)=0
for j=8 to 1
      for i=1 to 8
            Experiment i, j, &res(i, j)
      next
next
Print
for j=8 to 1
      for i=1 to 8
            Print res(i, j),
      next
      Print
next