فهرست مطالب

"برج هانوی"

مقدمه🔗

برج‌ هانوی یکی از مسایل کلاسیک رشته‌ی کامپیوتر است و برای حل آن از روش «بازگشتی» استفاده می‌شود.

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

  1. n - 1 دیسک را با استفاده از میله‌ی سوم به میله‌ی دوم منتقل می‌کنیم.
  2. دیسک باقیمانده در میله‌ی اول را به میله‌ی سوم منتقل می‌کنیم.
  3. تعداد n - 1 دیسک از دیسک‌های موجود در میله‌ی دوم را با استفاده از میله‌ی سوم به میله‌ی اول منتقل می‌کنیم.
  4. دیسک باقیمانده در میله‌ی دوم را به میله‌ی سوم می‌بریم.
  5. تعداد n - 1 دیسک از دیسک‌های موجود در میله‌ی اول را با استفاده از میله‌ی سوم به میله‌ی دوم می‌بریم.
  6. دیسک باقیمانده در میله‌ی اول را به میله‌ی سوم منتقل می‌کنیم.
  7. [و همین روند را تا زمان حل مساله تکرار می‌کنیم.]

نکته

برای حل برج هانوی با n دیسک نیاز به 2n-1 جابجایی داریم. یعنی برای ۴ دیسک ۱۵ جابجایی انجام می‌شود.

در مورد برنامه🔗

این برنامه به زبان پایتون و با استفاده از کتابخانه‌ی pygame نوشته شده است. ساختار برنامه به صورت ساده و بدون استفاده از کلاس نوشته شده و متغیرها نیز سراسری‌اند. ثابت‌ها با حروف کاملا بزرگ تعریف شده‌اند.

کتابخانه‌ی pygame را با دستور زیر نصب کنید:

SHELL
$ pip install pygame

اگر در مورد دستور pip چیزی نمی‌دانید در مورد pip را بخوانید.

شیوه‌ی اجرای برنامه🔗

این برنامه توانایی حل مساله با هر تعداد دیسک را دارد منوط به این که سیستم شما قادر به محاسبه‌ و یافتن جواب باشد.

فرض کنید کد برنامه را داخل فایل hanoi.py ذخیره کرده‌ایم. به صورت پیش فرض ۵ دیسک در میله اول قرار می‌گیرد ولی در خط فرمان بعد از نام فایل می‌توانیم تعداد دیسک‌ها را به صورت زیر مشخص کنیم:

SHELL
$ python hanoi.py 13

در مثال بالا برج هانوی با ۱۳ دیسک حل می‌شود. تصویر زیر در زمان انجام بیست و هفتمین جابجایی دیسک‌ گرفته شده است. همان طور که مشخص است تا زمانِ انجامِ جابجاییِ هشت هزار و صد و نود و یکم که آخرین جابجایی و حل نهایی مساله است راه دور و درازی در پیش داریم!

"حل مسئله‌ی برج هانوی با ۱۳ دیسک"

ویدیوی زیر برنامه را در حال اجرا نشان می‌دهد. برای اینکه حجم ویدیو کم شود تعداد دیسک‌ها را به ۳ عدد محدود کرده‌ایم:

متغیرها و ثابت‌های مهم برنامه🔗

ثابت S🔗

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

S یک لیست 4 اندیسی است. اندیس‌های 0 تا 2 هر کدام یک object از نوع pygame.Rect هستند و به ترتیب نشان‌دهنده‌ی مختصات میله‌ی اول و میله‌ی دوم و میله‌ی سوم بر روی پنجره‌ی برنامه‌اند. S[3] هم یک object از نوع pygame.Rect است و نشان دهنده‌ی مختصات میله‌ی افقی واقع شده در پایین صفحه است.

به یاد داشته باشید!

در این‌جا مکان یک پیکسل نسبت به بالا سمت چپِ صفحه نمایش سنجیده می‌شود. هر pygame.Rect با 4 متغیر ساخته می‌شود. مختصات بالا سمت چپِ (topleft) pygame.Rect نسبت به بالا سمت چپِ صفحه نمایش و عرض و ارتفاع خود pygame.Rect.

متغیر a🔗

a ابتدای کلمه‌ی active است. یک لیست حاوی 3 زیر لیست که هر زیر لیست نشان‌دهنده‌ی دیسک‌های موجود در میله‌ی متناظر است. مثلا محتویات a[0] نشان‌دهنده‌ی دیسک‌های قرار گرفته در میله‌ی اول است. هر دیسک یک object از pygame.Rect است. یکبار در ابتدای برنامه تمام دیسک‌ها (object متناظر با هر دیسک) در متغیر a[0] (میله‌ی اول) قرار داده می‌شوند و سپس در طول برنامه این متغیر دستخوش تغییرات می‌شود.

متغیر m🔗

یک لیست شامل تمام جابجایی‌های لازم برای حل مساله است. محتویات این لیست توسط تابع hanoi فراهم می‌شود. هر عضو این لیست یک لیست دو عنصره است. اندیس اول نشان دهنده‌ی میله‌ی مبدا و اندیس دوم نشان دهنده‌ی میله مقصد است.

سایر متغیرها و ثوابت🔗

جدول زیر تعدادی دیگر از متغیرها و ثوابت برنامه را نشان می‌دهد. لازم به ذکر است که ثابت‌های دیگری نیز برای تنظیم رنگ صفحه و رنگ دیسک‌ها و رنگ میله‌ها و مانند این موارد تعریف شده‌اند که نیازی به ذکر آن‌ها در این جدول نیست.

ردیف نام متغیر توضیحات
1 N تعداد دیسک‌ها. به صورت پیش‌فرض ۵ است ولی با استفاده از آرگومان خط فرمان قابل تنظیم توسط کاربر است.
2 FREQ سرعت حرکت دیسک‌ها. در یک ثانیه حلقه‌های while بیشتر از FREQ بار اجرا نشوند.
3 number_of_moves تعداد جابجایی‌های انجام شده. بعد از هر جابجایی این متغیر یک واحد افزایش می‌یابد.
4 HBH horizontal bar height یا ارتفاع میله‌ی افقی.
5 DH disk height یا ارتفاع هر دیسک
6 DBD distance between disks یا فاصله‌ی بین دو دیسک مجاور در یک میله
7 dw disk width یا عرض دیسک. این متغیر برای دیسک بعدی مقداری کوچکتر می‌شود.
8 rdw reduce disk width. عرض هر دیسک به اندازه‌ی این متغیر از عرض دیسک قبلی‌اش کوچکتر می‌شود. متغیر dw را ببینید.

تابع‌های برنامه🔗

برنامه تنها دارای ۵ تابع است. یکی از توابع به نام print_program_info اطلاعات مربوط به برنامه را در کنسول نمایش می‌دهد و نقشی در حل مسئله ندارد.

تابع hanoi🔗

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

تابع move🔗

به ازای هر عنصر موجود در متغیر m (که نشان‌دهنده‌ی کلیه‌ی جابجایی‌های لازم برای حل مساله است) که یک لیست به صورت [init, dest] است، دیسک را از میله‌ی a[init] به a[dest] منتقل می‌کند. این جابجایی که باید به صورت گرافیکی انجام شود شامل سه مرحله است:

  1. حرکت دیسک به سمت بالا برای خروج از میله‌ی init
  2. حرکت به سمت چپ یا راست برای رسیدن به میله‌ی dest
  3. حرکت به سمت پایین برای فرود در میله‌ی dest. ممکن است میله‌ی مقصد خالی باشد که در این صورت دیسک در پایین‌ترین نقطه‌‎ی میله قرار می‌گیرد و یا اینکه دیسک یا دیسک‌هایی قبلا در میله‌ی مقصد وجود داشته باشند. در این صورت دیسک جدید باید در بالای آخرین دیسک قرار بگیرد.

هر حرکت بسته به این که عمودی یا افقی است یک واحد از x یا y مربوط به pygame.Rect دیسک مربوطه کم یا زیاد می‌کند. بعد از هر تغییر در آفست هر دیسک، تابع update_screen فراخوانی می‌شود. این تابع کل محتوا را مجددا بر صفحه ترسیم می‌کند.

تابع update_screen🔗

محتوای ثابت S و متغیرa و همچنین دو کادر متنی را بر روی صفحه نمایش می‌دهد. در هر بار فراخوانی کل صفحه مجددا ترسیم می‌شود. یعنی به این صورت نیست که بخشی از صفحه یا ویجیتی از ویجیت‌های موجود آپدیت شود، بلکه کل صفحه دوباره رونویسی می‌شود.

یکی از کادرهای متنی، تعداد حرکت‌های انجام شده تا آن لحظه را در بالا سمت راست و دیگری عبارت Tower of hanoi را در بالا وسط صفحه می‌نویسد.

تابع check_events🔗

این تابع مداوما برای بررسی event های رخ داده فراخوانی می‌شود. سه event مهم برای برنامه، فشار دگمه‌ی Esc، فشار دگمه‌ی Q و همچنین pygame.QUIT است. هر سه رویداد باعث توقف برنامه و بسته شدن پنجره می‌شود.

کد کامل حل مساله برج هانوی🔗

کد حل مساله‌ی برج هانوی را می‌توانید از کادر زیر دریافت کنید. اگر توضیحات را نخوانده‌اید، این کد به زبان پایتون است و از کتابخانه pygame استفاده می‌کند!

hanoi.py
""" The tower of Hanoi 
    _________________________________________________
    Sorry for my bad english!
    Writted with python and pygame module.
    Note : this program initially find a list of movements 
    for the problem and then moves the disk in order of the list
    of solution . Therefore you must execute the program
    with a suitable n disk.
    If we had n disks, the movements for solving the problem is
    (2 ^ n) - 1 .
    I advice you that you examine the program with maximum 
    of n = 15 .
    _________________________________________________

    Programmer  : Mohsen Safari
    Email       : safari.tafreshi@gmail.com
    Website     : dokaj.ir
"""

import pygame, sys, inspect

# Number of the disk in tower of hanoi
N = 5

# Number of ticks in one second
FREQ = 500

# If user has provided disk number in command line use it
if len(sys.argv) == 2 and int(sys.argv[1]) >= 3:
    N = int(sys.argv[1])
    if N > 16:
        print("Number of disk is too high.")
        print("If you are sure change code in line 32")
        sys.exit(1)


pygame.init()

BGCOLOR        = (209, 209, 209)
BARSCOLOR      = (  0, 104, 139)
DISKSCOLOR     = (205,  51,  51)
MOVEFONTCOLOR  = (255,   0, 255)
TITLEFONTCOLOR = (255,  64,   0)

SIZE = WIDTH, HEIGHT = (540, 350)

# A counter for counting number of disk moves.
number_of_moves = 0

BASICFONT  = pygame.font.SysFont("freesansbold", 20)
BIGFONT    = pygame.font.SysFont("freesansbold", 42)

SCREEN = pygame.display.set_mode(SIZE)
pygame.display.set_caption("Tower of Hanoi")

clock = pygame.time.Clock()

# Movements! in this list we store the moves of the disks
m = [] 

# horizonatl bar height and disk height
HBH = DH = 10

# Distance between two disk
DBD = 15

# Static elements: the 3 vertical bars and one horizental bar
S = [0, 0, 0, 0]

# s[3] is the horizontal bar
S[3] = pygame.Rect(20, HEIGHT - 20, WIDTH - 40, HBH)

# s[0] and s[1] and s[2] are the vertical bars 
for i in range(0, 3):
    S[i] = pygame.Rect(WIDTH / 3 * (i + 1) - 100, 100 , 10, S[3].top - 100)

# active_elements! each sublist show the disks in the corresponding bar
a = [ [], [], [] ]


# Adding all disks to a[0]
# For a[0] top offset the largest disk in first vertical bar(=S[0])
# is the top offset of the horizental bar(=S[3])
top =S[3].top - HBH 

# First disk width
dw = 150

# Reduce disk width.
# Next disk width must be "rdw" smaller than this disk
rdw = 30

while dw / N <= rdw :
    rdw = rdw - 1
    continue

for i in range(N) :
    a[0].append(pygame.Rect(S[0].centerx - dw / 2, top - HBH , dw, DH))
    top = top - DH - 5
    dw = dw - rdw
# end of the initial positioning!


# Show all elements on the screen.
# The content of the lists bellow are Rect and have
# their coordiantes and width and height 
# We simply show them on the screen.
def update_screen() :
    # check event queue for pygame.QUIT event!
    check_events()

    SCREEN.fill(BGCOLOR)
    for i in range(len(S)) :
        pygame.draw.rect(SCREEN, BARSCOLOR, S[i], 0)

    for i in range(len(a)) :
        for j in range(len(a[i])) :
            pygame.draw.rect(SCREEN, DISKSCOLOR, a[i][j], 0)

    # Print Number of moves on screen
    text = "Moves: {0}".format(number_of_moves)
    surf = BASICFONT.render(text, True, MOVEFONTCOLOR)
    rect = surf.get_rect()
    rect.topleft = (WIDTH - rect.width - 10, 0)
    SCREEN.blit(surf, rect)

    # Print Title of program on screen
    surf = BIGFONT.render("Tower of Hanoi", True, TITLEFONTCOLOR)
    rect = surf.get_rect()
    rect.center = (S[1].left, 30)
    SCREEN.blit(surf, rect)

    pygame.display.update()


def move() :
    # Note that in this place hanoi towers movements are completely calculated!
    # and these movements are stored in list "m".
    # Now we take each move and then move the disk to its destination bar.
    # Also note that in this function we only change the positions of
    # the disk in the screen and then call the update_screen function.
    # "update_screen" function show all elements on 
    # screen. all elements are lists: S and a

    # A counter for counting number of disk moves.
    global number_of_moves

    for i in range(len(m)) :
        # m[i][0] is starting bar and i is a number in (0,1,2)  
        init = m[i][0]

        # m[i][1] is the destination bar and i is a number(0,1,2)
        dest = m[i][1]

        if len(a[dest]) != 0:
            dest_y = a[dest][-1].top - DBD # DBD: distance between disks
        else :
            dest_y = S[3].top - HBH # HBH: horizontal bar height 

        # moves the disk to the top of the its bar!
        while a[init][-1].top > S[init].top - 30:
            clock.tick(FREQ)
            a[init][-1].move_ip([0, -1])
            update_screen()

        # Destination bar is at left of current bar or right of it????
        if a[init][-1].centerx < S[dest].centerx:
            # Destination bar is at right of current bar
            while a[init][-1].centerx < S[dest].centerx:
                clock.tick(FREQ)
                a[init][-1].move_ip([1,0])
                update_screen()
        else:
            # Destination bar is at the left of current bar
            while a[init][-1].centerx > S[dest].centerx:
                clock.tick(FREQ)
                a[init][-1].move_ip([-1,0])
                update_screen()

        # Move disk down in the destination bar
        while a[init][-1].centery < dest_y :
            clock.tick(FREQ)
            a[init][-1].move_ip([0, 1])
            update_screen()

        # Remove the moved disk from the its location
        # in bar "init" and add it to the dest bar
        a[dest].append(a[init].pop())       
        number_of_moves += 1        

# The hanoi towers function itself!
# All moves of the disks will be stored in the list 'm'
def hanoi(n, b0, b1, b2) :
    if n == 1 :
        # Store the move in the list m
        m.append([b0, b2])
    else :
        hanoi(n - 1, b0, b2, b1)
        # Store the move in the list m
        m.append([b0, b2])
        hanoi(n - 1, b1, b0, b2)

# Function for exit from the application
def check_events() :
    # Exit with click on close button
    for event in pygame.event.get() :
        if event.type == pygame.QUIT:
            sys.exit()

        # Exit with "Escape" button or "q" button
        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_ESCAPE or event.key == pygame.K_q:
                sys.exit()

# Info about this program
def print_program_info():
    print("Hanoi towers with pygame")
    print("------------------------")
    print("Programmer   : Mohsen Safari")
    print("Website      : dokaj.ir")

if __name__ == "__main__":
    # print information on console about this program
    print_program_info()

    # move hanoi towers program
    hanoi(N, 0,1, 2)

    # Now hanoi profram is solved. All the moves are in "m" variable
    # "m" means "moves"! In function we move all disks to its destination
    move()

    # Program is done. wait for quit event.
    while 1 :
        check_events()
نوشته شده در: 1402-02-09 (1 سال 3 هفته 2 روز پیش)

من محسن هستم؛ برنامه‌نویس PHP و Laravel و Zend Framework و پایتون و فلسک، ولی بیشتر تمرکزم روی لاراول است. این سایت را اولین بار با فلسک نوشتم ولی بعد تصمیم گرفتم آن را با لاراول نیز پیاده‌سازی کنم. هم نسخه‌ی فسلک و هم نسخه‌ی لاراول را می‌توانید روی گیت‌هابم پیدا و دانلود کنید.

برای ارتباط با من یا در همین سایت کامنت بگذارید و یا به dokaj.ir(at)gmail.com ایمیل بزنید.

در مورد این مطلب یادداشتی بنویسید.