8puzzle lisp

[woodripp3r]

Καλησπέρα θα ήθελα αν ξέρει κάποιος να με βοηθήσει. Έχω να λύσω το πρόβλημα του τετράγωνου παζλ 8 ψηφίδων, δηλαδή απο μια τυχαία κατάσταση να βρίσκει την λύση (1 2 3 8 _ 4 7 6 5) χρησιμοποιώντας τον bfs. Έχω γράψει τον ακόλουθο κώδικα αλλά δεν τερματίζει ποτέ.

>(defun bfs (lista_arxiki)
      (setf metopo_anazitisis (antistoixia_h-n_katastashs lista_arxiki))  (setf closed nil)
             (loop
                   (setf katastash (min_h-n metopo_anazitisis))
                       (if (not (member katastash closed))   
                                        (if (equal katastash `(0 (1 2 3 8 _ 4 7 6 5)))
                                             (return (print (list `(epituxia)  katastash)))

                             (progn (remove katastash metopo_anazitisis)
                             (push katastash closed)))


(progn (remove katastash metopo_anazitisis) (setf katastash (min_h-n metopo_anazitisis)) (remove katastash metopo_anazitisis) (push katastash closed)  ) )

(setf metopo_anazitisis  (antistoixia_h-n_katastashs (efarmogh_telestwn (second katastash)))   ))

 

 

Αρχικά η συνάρτηση bfs δέχεται την αρχική λίστα. Στη συνέχεια το μέτωπο αναζήτησης έχει την αρχική κατάσταση. Η συνάρτηση antistoixia_h-n_katastashs επιστρέφει την λίστα με ένα στοιχείο μπροστά, το οποίο είναι το πόσα κουτία έχουν διαφορετική τιμή απο την κατάσταση στόχο. Μέσα στο loop αρχικά βάζει στην katastash που είναι και η τρέχουσα κατάσταση την λίστα η οποία θα έχει και το μικρότερο h-n ( θέσεις με διαφορετικά στοιχεία απο την τελική λύση). Στην συνέχεια ελέγχει αν η κατάσταση αυτή ειναι στο κλειστό σύνολο. Αν δεν είναι τότε μπαίνει σε μια άλλη if οπού εκεί συγκρίνει αν ειναι η κατάσταση στόχος, αν είναι τότε επιστρέφει με επιτυχία, αν δεν είναι βγάζει απο το μέτωπο αναζήτησης την κατάσταση και την κάνει push στο closed. Αν η κατάσταση μας όμως ειναι στο κλειστό σύνολο τότε την κάνει remove απο το μέτωπο αναζήτησης και βάζει εκ νέου στην κατάσταση την λίστα με το μικρότερο h-n από το μέτωπο αναζήτησης, στην συνέχεια κάνει remove την καινούρια κατάσταση απο το μέτωπο αναζήτησης και την pusharei στο closed. Σε αυτό το σημείο βγαίνει απο το σωμα του πρώτου if. Τέλος μέσα στο loop θέτουμε στο μέτωπο τα "παιδιά" της κατάστασης μας.

 

Τρέχω λοιπόν το παραπάνω και δεν τερματίζει ποτέ. Ελπίζω να μην σας έμλεξα με αυτό που έχω γράψει. Αν κάποιος μπόρει να μου πεί που είναι το λάθος θα με σώσει! Ευχαριστώ πολύ.

 

---------- Προσθήκη στις 22:06 ---------- Προηγούμενο μήνυμα στις 20:27 ----------

 

απότι φαίνεται λύση δεν βρέθηκε ... έστω αν μπορεί κάποιος μια βοήθεια σχετικά με την ευριστική συνάρτηση αυτού του προβλήματος?

[C6WGMN]

απότι φαίνεται λύση δεν βρέθηκε ... έστω αν μπορεί κάποιος μια βοήθεια σχετικά με την ευριστική συνάρτηση αυτού του προβλήματος?

 

Δεν είχα ξαναλύσει το πρόβλημα αυτό. Μερικά σχόλια για τον κώδικα σου: γράφεις σαν να γράφεις σε C και όχι lisp. Προτείνω τα εξής βιβλία, του graham (on lisp) και "Practical Common Lisp", τα οποία διαθέτονται δωρεάν στο internet από τους συγγραφείς.

 

Παρακάτω παραθέτω λίγο καλογραμμένο κώδικα, που αντανακλά το στυλ με το οποίο γράφω lisp. Δεν είναι ανάγκη να γράφεις και εσύ έτσι, μιας που στην γλώσσα αυτή υπάρχουν αναρίθμητοι τρόποι να γράψει κανείς κάτι σωστά, αλλά σε συμβουλεύω να τον μελετήσεις, και περισσότερο να μελετήσεις τα προαναφερθέντα βιβλία (Ρίξε μια ματιά και στο λινκ που δίνω στον κώδικα μου). Ο κώδικας δεν είναι πλήρεις. Έχεις όλες τις συναρτήσεις που χρειάζεσαι για να γράψεις την κύρια συνάρτηση με την οποία θα ψάξεις για την λύση. Ο συγκεκριμένος κώδικας λύνει το πρόβλημα μόνο αν είναι 1 κίνηση μακρία από την λύση.

 

>
; to learn more about the problem
; [url]http://www.8puzzle.com/8_puzzle_algorithm.html[/url]

(defparameter *initial-state* '(2 8 3 1 6 4 7 0 5))
(defparameter *goal-state* '((0 1 2 3 4 5 6 7 8)
                            (1 2 3 8 0 4 7 6 5)))

(defun count-board (board)
 "Use this function to find the ending of the puzzle
  (odd->center, even->first)"
 (reduce #'+
         board
         :key (lambda (x) (count-if (lambda (y)
                                      (unless (zerop y)
                                        (> x y)))
                                    (member x board)))))
(defun goal (board)
 (if (evenp (count-board board))
     (car *goal-state*)
     (cadr *goal-state*)))

(defun blank-position (board)
 "What's the position of the blank tile?"
 (length (member 0 board)))

(defun possible-moves (board)
 "Return the possible moves (S E W N)"
 (let ((k (blank-position board)))
   (mapcan (lambda (f) (funcall f k))
           (list
            (lambda (x) (if (< x 7) (list 'S)))
            (lambda (x) (if (> x 3) (list 'N)))
            (lambda (x) (if (/= 0 (rem x 3)) (list 'W)))
            (lambda (x) (if (/= 0 (rem (1- x) 3)) (list 'E)))))))

(defun move (board direction)
 "Direction is S E W N"
 (if (member direction
             (possible-moves board))
     (let* ((k (- 9 (blank-position board)))
            (board (copy-list board))
            (new-position (case direction
                            (S (- k 3))
                            (N (+ k 3))
                            (W (- k 1))
                            (E (+ k 1)))))
       (rotatef (nth k board)
                (nth new-position board))
       board)))

(defun solve-puzzle-1 (board)
 "Solve the 8 puzzle! (1 step only)"
 (let ((goal (goal board)))
   (some
    (lambda (state) (equal goal state))
    (mapcar (lambda (direction)
              (move board direction))
            (possible-moves board)))))

[woodripp3r]

Σε ευχαριστώ πολυ για την βοηθεια σου!με βοήθησε αρκετά το λινκ σου.. να σε ρωτήσω κάτι τελευταίο? δηλαδή σύμφωνα με το λινκ που μου έδωσες και σύμφωνα με το άθροισμα που βγάζει... αν εγώ ξεκινήσω απο μια κατάσταση η οποία έχει άθροισμα άρτιο δεν μπορώ να πάω με κανένα τρόπο στην κατάσταση (1 2 3 8 _ 4 7 6 5), έτσι δεν είναι??? κατάλαβα σωστά? Άρα για να πάμε στην κατάσταση (1 2 3 8 _ 4 7 6 5) πρέπει ώς είσοδο στο πρόγραμμα μας να δώσουμε μια κατάσταση με περιτό άθροισμα?

[Directx]

Το μυστικό σε αυτά τα puzzles όσο το είχα ψάξει (η σελίδα που σου δόθηκε είναι ευαγγέλιο για το ζήτημα ) είναι το Initial State τους οπότε καθορίζει και τον τρόπο επίλυσης τους.

 

Υ.Γ.

Είχα γράψει σε C++ ένα τέτοιο παιχνιδάκι το οποίο ακολουθούσε την επίλυση " ,1,2,3..9" αντί της "1,2,3,8, ,4 .." αλλά από lisp δεν γνωρίζω.

[bruno11]

Γεια σας.Θα ήθελα να κάνω μια ερώτηση πάνω σε ένα κομμάτι κώδικα(σε LISP) που υλοποιεί το 8 puzzle problem.

Το κομμάτι του κώδικα είναι το εξής:

(defun next-boards (board)

"Given the current board, return a list of the next boards."

(let ((states nil)

(x (position *space* board)))

(flet ((maybe-swap (move-fn)

(when-bind (p (funcall move-fn x))

(push (swap board x p) states))))

(declare (dynamic-extent maybe-swap))

(mapc #'maybe-swap fns))

states)))

 

(defun swap (list n1 n2)

"Non-destructive equivalent of rotatef."

(setq list (copy-list list))

(rotatef (nth n1 list) (nth n2 list))

list)

 

Όταν κάνω compile τον κώδικα μου βγάζει 2 warnings:

1) Warning in (SUBFUNCTION MAYBE-SWAP NEXT-BOARDS): P assumed special

2) Warning in NEXT-BOARDS: Failed to find name MAYBE-SWAP in declaration (DYNAMIC-EXTENT MAYBE-SWAP).

 

Μπορεί κάποιος να μου δώσει μια εξήγηση??

thanks