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

Ένα μοντέλο του πύργου του Ανόι (με 8 δίσκους)

Μια κινούμενη λύση του πύργου του Ανόι για το T (4, 3)

Πύργος του Ανόι διαδραστική παρουσίαση στο Μουσείο Universum στην Πόλη του Μεξικού

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

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

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

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

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

n = 3

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

← Προηγούμενο βήμα ← Προηγούμενο βήμα Επόμενο βήμα → Επόμενο βήμα → 1

n = 4

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

← Προηγούμενο βήμα ← Προηγούμενο βήμα Επόμενο βήμα → Επόμενο βήμα → 1

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

Αν $x_{n}$ είναι το βέλτιστο πλήθος βημάτων για να μετακινηθούν $n$ δίσκοι από την πρώτη στήλη στην τελευταία, τότε

$x_{n}=$ (βήματα για τους $n-1$ δίσκους από την $1\to 2$)

+ (μετακίνηση του μεγάλου δίσκου στην $3$)

+ (βήματα για τους $n-1$ δίσκους από την $2\to 3$)

Δηλαδή,

$x_{n}=x_{n-1}+1+x_{n-1}=2x_{n-1}+1$,

καθώς και

$x_{1}=1$.

Επομένως το βέλτιστο πλήθος των κινήσεων είναι μία γραμμική αναδρομική ακολουθία πρώτης τάξης με $\lambda =2$ και $\omega =1$. Ο γενικός τύπος αυτής δίνει

${\begin{aligned}x_{n}&=2^{n-1}\cdot \left(1-{\frac {1}{1-2}}\right)+{\frac {1}{1-2}}\\&=2^{n}-1.\end{aligned}}$

Υλοποίηση

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

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

Δείτε επίσης

• Αναδρομή