مسئله‌ی معروف برج‌های هانوی یک معمای ریاضی است که در سال 1883 توسط ریاضی‌دان فرانسوی ادوارد لوکاس مطرح شد. 3 میله داریم:
  - A میله‌ی مبداء (Source)
  - B میله‌ی کمکی (Auxiliary)
  - C میله‌ی مقصد (Destination)
در میله‌ی A تعدادی مهره از بزرگ به کوچک بر روی هم انباشته شده و تشکیل یک برج را داده‌اند، بطوری‌که مهره‌ی بزرگتر در زیر قرار دارد. شکل زیر یک برج هانوی با 3 مهره را نشان می‌دهد:

هدف، انتقال کل برج (مهره‌ها) به میله‌ی مقصد C با حفظ ترتیب آنهاست. البته قواعد زیر را باید در نظر بگیرید:
  - در هر بار فقط یک مهره را می‌توانید جابه‌جا کنید
  - در هر حرکت، فقط مهره‌ی بالایی هر میله امکان حرکت دارد
  - درحین انتقال حق ندارید مهره‌ی بزرگ‌تر را برروی مهره‌ی کوچک‌تر قرار دهید

البته این‌کار باید با کمترین تعداد حرکت انجام شود و قصد داریم الگوریتمی ارائه دهیم که برای هر تعداد مهره ( n مهره) جواب بهینه را پیدا کند. برای مسئله‌ی 3 مهره که در شکل بالا نشان داده شده، جواب بهینه بصورت زیر است:

حالت شروع	حرکت اول: انتقال مهره‌ی 1 از میله‌ی A به میله‌ی C
حرکت دوم: انتقال مهره‌ی 2 از میله‌ی A به میله‌ی B	حرکت سوم: انتقال مهره‌ی 1 از میله‌ی C به میله‌ی B
حرکت چهارم: انتقال مهره‌ی 3 از میله‌ی A به میله‌ی C	حرکت پنجم: انتقال مهره‌ی 1 از میله‌ی B به میله‌ی A
حرکت ششم: انتقال مهره‌ی 2 از میله‌ی B به میله‌ی C	حرکت هفتم: انتقال مهره‌ی 1 از میله‌ی A به میله‌ی C

در زیر یک پیاده سازی بازگشتی (با رویکرد تقسیم و غلبه) به زبان C++ آورده شده‌است:

1#include <iostream>
2using namespace std;
3void Move(int n, char srcPeg, char trgPeg, char tmpPeg) {
4  if (n == 1)
5    cout << "Move disk #1 from peg "
6      << srcPeg << " to " << trgPeg << endl;
7  else {
8    Move(n - 1, srcPeg, tmpPeg, trgPeg);
9    cout << "Move disk #" << n << " from peg "
10      << srcPeg << " to " << trgPeg << endl;
11    Move(n - 1, tmpPeg, trgPeg, srcPeg);
12  }
13}
14void main() {
15  int n;
16  cin >> n;
17  Move(n, 'A', 'C', 'B');
18}

پیشنهاد می‌شود برای دریافت جزئیات بیشتر، مطلب مربوط به رویکرد تقسیم و غلبه با محوریت حل مسئله‌ی برج‌های هانوی را ببینید.

در اینجا تابع Move() بصورت بازگشتی مسئله را حل می‌کند. به این‌ترتیب که ابتدا بررسی می‌کند که اگر فقط یک مهره داریم، آن را انتقال می‌دهد درغیر این‌صورت، ابتدا n-1 مهره‌ی بالایی را به میله‌ی کمکی منتقل می‌کند، سپس مهره‌ی بزرگ‌تر را به تنهایی در سرجای خود قرار می‌دهد و در آخر n-1 مهره‌ی قبلی را به همین شکل و با همین رویکرد جابه‌جا می‌کند. خروجی برنامه برای 3 مهره به شکل زیر است که همان ترتیب مراحل نشان داده شده در تصاویر بالاست:

3
Move disk #1 from peg A to C
Move disk #2 from peg A to B
Move disk #1 from peg C to B
Move disk #3 from peg A to C
Move disk #1 from peg B to A
Move disk #2 from peg B to C
Move disk #1 from peg A to C

نکته‌ی اول اینکه برای ارائه‌ی راه‌حل، نوشتن حداقل داده‌ها در خروجی کفایت می‌کند. مثلا الزامی برای نوشتن نام میله‌ی مبداء وجود ندارد، چرا که وقتی می‌گوییم مهره‌ی شماره‌ی 1 را به میله‌ی C انتقال بده، بازیکن می‌داند و واضح است که مهره‌ی شماره ‌1 هم‌اینک در کدام میله قرار دارد. یا اینکه فقط می‌توان شماره‌ی میله‌ی مبداء و مقصد را نوشت و از ذکر شماره‌ی مهره صرف‌نظر کرد، چون بازیکن می‌داند که از میله‌ی مبداء فقط مهره‌ی بالایی را می‌تواند جابجا کند. نکته‌ی بعدی دنباله‌ی شماره‌ی مهره‌های جابجا شده است که برای مثال بالا (اعداد سبز رنگ) عبارت است از:

1, 2, 1, 3, 1, 2, 1

و برای یک مسئله‌ی نمونه‌ی دیگر با 4 مهره عبارتست از:

1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1

من این دنباله را دنباله‌ی هانوی گذاشته‌ام که خواص بسیار جالبی دارد و در این وب سایت نیز مسئله‌های مختلفی در مورد آن وجود دارد.

برای آشنایی بیشتر با دنباله‌ی هانوی، مسئله‌ی تابع خط‌کش و مسئله‌ی دنباله‌ی اعداد یک در میان را ببینید.

برای درک بهتر روش حل، تصویر متحرک زیر را که برای حل مسئله با 3 مهره است را ببینید :

برای مشاهده تصویر متحرک بر روی تصویر کلیک کنید

در زمان دانشجویی خودم، یادمه که استادمون برای درس برنامه‌نویسی مقدماتی، حل این مسئله را خواسته بودند و من هم تصمیم گرفتم بصورت گرافیکی (البته تحت DOS) آن را طراحی کنم. شما می‌توانید سورس کامل آن که به زبان C++ نوشته شده‌است را از اینجا دانلود کنید. تصویر متحرک بالا خروجی همین برنامه می‌باشد.

ملاحظه می‌کنید که استفاده از روش تقسیم و غلبه، به حل آسان مسئله کمک می‌کند. شما می‌توانید برای مشاهده‌ی تحلیل الگوریتم تقسیم و غلبه‌ی برج‌های هانوی به این مطلب مراجعه کنید. حال می‌خواهیم این مسئله را با روش غیربازگشتی حل کنیم با ما همراه باشید.

پیشنهاد می‌شود برای کسب دانش بیشتر در حوزه‌ی تحلیل کارایی الگوریتم‌ها و به‌عنوان تمرین درس طراحی الگوریتم‌ها، مطلب مربوط به تحلیل الگوریتم تقسیم و غلبه‌ی برج‌های هانوی را ببینید.

ادامه دارد...