Πύργος του Ανόι

μικρογραφία|300x300εσ| Μια κινούμενη λύση του πύργου του Ανόι για το T (4, 3) 
μικρογραφία|300x300εσ| Πύργος του Ανόι διαδραστική παρουσίαση στο Μουσείο Universum στην Πόλη του Μεξικού 
Ο πύργος του Ανόι (ονομάζεται επίσης τον Πύργο του Βράχμα ή Lucas' Πύργος  και μερικές φορές πολλαπλό) είναι μαθηματικό παιχνίδι ή γρίφος. Αποτελείται από τρεις ράβδους και διάφορους δίσκους διαφορετικών μεγεθών, οι οποίοι μπορούν να μετακινηθούν σε οποιαδήποτε ράβδο. Ο γρίφος ξεκινάει με τους δίσκους σε μια ενιαία στοίβα σε μια αύξουσα σειρά μεγέθους σε μία ράβδο. Η μικρότερη βρίσκεται στην κορυφή, κάνοντας έτσι ένα κωνικό σχήμα.

Ο στόχος του γρίφου είναι να μετακινηθεί ολόκληρη η στοίβα σε μια άλλη ράβδο, ακολουθώντας τους ακόλουθους απλούς κανόνες:

 Μόνο ένας δίσκος μπορεί να μετακινηθεί κάθε φορά.
 Κάθε κίνηση βασίζεται στη λήψη του ανώτερου δίσκου σε μία από τις στοίβες και στην τοποθέτηση του πάνω στην άλλη στοίβα ή σε μια άδεια ράβδο.
 Δεν μπορεί να τοποθετηθεί μεγαλύτερος δίσκος πάνω από μικρότερο δίσκο.

Με 3 δίσκους, το παζλ μπορεί να λυθεί σε 7 κινήσεις. Ο ελάχιστος αριθμός κινήσεων που απαιτούνται για την επίλυση ενός παζλ του Πύργου του Ανόι είναι 2 ν - 1, όπου ν είναι ο αριθμός των δίσκων.

 Παραδείγματα 

 n = 3 

Οι παρακάτω επτά κινήσεις είναι οι ελάχιστες δυνατές:

 n = 4 
Οι παρακάτω δεκαπέντε κινήσεις είναι οι ελάχιστες δυνατές:

 Ελάχιστο πλήθος βημάτων 

Αν  είναι το βέλτιστο πλήθος βημάτων για να μετακινηθούν  δίσκοι από την πρώτη στήλη στην τελευταία, τότε
 (βήματα για τους  δίσκους από την ) 
+ (μετακίνηση του μεγάλου δίσκου στην )
+ (βήματα για τους  δίσκους από την )
Δηλαδή, 
,
καθώς και 
.
Επομένως το βέλτιστο πλήθος των κινήσεων είναι μία γραμμική αναδρομική ακολουθία πρώτης τάξης με  και . Ο γενικός τύπος αυτής δίνει

 Υλοποίηση 

Ο παρακάτω κώδικας σε C++ τυπώνει τα βέλτιστα βήματα για  βήματα:

#include <fstream>
#include <iostream>
#include <vector>

// Η θέση του i-οστού δίσκου.
std::vector<int> pos;

void printSolution();

// Επιστρέφει την στοίβα διαφορετική των a, b.
int other(int a, int b) {
  if (a != 0 && b != 0) return 0;
  if (a != 1 && b != 1) return 1;
  return 2;
}

// Mετακινεί τους δίσκους 0, 1, ..., n από την στοίβα from στην to.
void solve(int n, int from, int to) {
  if (n == -1) {
    return;
  }
  solve(n-1, from, other(from, to));
  pos[n] = to;
  printSolution();
  solve(n-1, other(from, to), to);
}

int main() {
  int n = 3;
  pos.resize(n, 0);
  printSolution();
  solve(n-1, 0, 2);
  return 0;
}

void printSolution() {
  std::vector<std::vector<int>> disks_at_pos(3);
  for (int i = pos.size() - 1; i >= 0; --i) {
    disks_at_pos[pos[i]].push_back(i);
  }
  for (int x = 0; x < 3; ++x) {
    std::cout << x << " : ";
    for (auto disk : disks_at_pos[x]) {
      std::cout << disk << " ";
    }
    std::cout << std::endl;
  }
  std::cout << std::endl;
}

 Δείτε επίσης 
 Αναδρομή

 Παραπομπές 

Κατηγορία:Παζλ λογικής