ورود به سایت

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

ثبت نام ×

لطفا فرم را پر کرده و ثبت نام کنید!

حل مساله برج هانوی با پایتون و pygame

مقدمه

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

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

باید همه‌ی این دیسک‌ها را با استفاده از میله‌ی دوم به میله‌ی سوم منتقل کنیم، اما در هیچ مرحله‌ای نباید دیسک بزرگتر روی دیسک کوچکتر قرار بگیرد. شیوه‌ی حل مساله به روش بازگشتی به صورت زیر است:
  • n - 1 دیسک را با استفاده از میله‌ی سوم به میله‌ی دوم منتقل می‌کنیم. (الف)
  • دیسک باقیمانده در میله‌ی اول را به میله‌ی سوم منتقل می‌کنیم.
  • تعداد n - 1 دیسک از دیسک‌های موجود در میله‌ی دوم (الف) را با استفاده از میله‌ی سوم به میله‌ی اول منتقل می‌کنیم. (ب)
  • دیسک باقیمانده در میله‌ی دوم را به میله‌ی سوم می‌بریم.
  • تعداد n - 1 دیسک از دیسک‌های موجود در میله‌ی اول (ب) را با استفاده از میله‌ی سوم به میله‌ی دوم می‌بریم.
  • دیسک باقیمانده در میله‌ی اول را به میله‌ی سوم منتقل می‌کنیم. (ج)
  • [و همین روند را تا زمان حل مساله تکرار می‌کنیم.]

برای حل مساله‌ی برج هانوی با n دیسک نیاز به 2 ^ n - 1 جابجایی داریم. یعنی برای 4 دیسک 15 جابجایی انجام می‌شود.

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

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

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

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

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

Bash
$ python hanoi.py 13

در مثال بالا برج هانوی با 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 تعداد دیسک‌ها. به صورت پیش‌فرض 5 است ولی با استفاده از آرگومان خط فرمان قابل تنظیم توسط کاربر است.
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 را ببینید.

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

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

تابع hanoi

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

تابع move

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

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

تابع update_screen

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

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

تابع check_events

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

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

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

Python
""" 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		: safarionline.ir
	Mobile		: +98-935-507-18-59
"""
 
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 31")
		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		: safarionline.ir")	
	print("Mobile		: +989355071859")
 
 
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()

نظر شما



 
 
 
لینک‌های مفید