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

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

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

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

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

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

### n = 3

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

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

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

Αν x_n είναι το βέλτιστο πλήθος βημάτων για να μετακινηθούν n δίσκοι από την πρώτη στήλη στην τελευταία, τότε
:x_n =  (βήματα για τους n-1 δίσκους από την 1\to2) 
::::+ (μετακίνηση του μεγάλου δίσκου στην 3)
::::+ (βήματα για τους n-1 δίσκους από την 2\to3)
Δηλαδή, 
:x_n = x_{n-1} + 1 + x_{n-1} = 2x_{n-1} + 1,
καθώς και 
:x_1 = 1.
Επομένως το βέλτιστο πλήθος των κινήσεων είναι μία γραμμική αναδρομική ακολουθία πρώτης τάξης με \lambda = 2 και \omega = 1. Ο γενικός τύπος αυτής δίνει
:
\begin{align}
x_n 
 & = 2^{n-1} \cdot \left(1 - \frac{1}{1 - 2} \right) + \frac{1}{1 - 2} \\
 & = 2^n - 1.
\end{align}

## Υλοποίηση

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


```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;
}
```


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

## Παραπομπές


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