Đ tài xây d ng ch ng trình Game ề ự ươ
15-Puzzle
Sinh viên th c hi n:ự ệ
ØNguy n Văn Hùngễ
ØĐào Quang Ph ngươ
ØĐào Nh t Th nhậ ị
Tr ng đ i h c H i Phòngườ ạ ọ ả
Khoa Toán-Tin
Giáo viên h ng d n: Nguy n Ng c Kh ngướ ẫ ễ ọ ươ
1
N i dungộ
2
Gi i thi u Game 15-Puzzleớ ệ
ØGame 15-puzzle còn g i là Gem Puzzle, Boss Puzzle, Game of ọ
Fifteen, Mystic Square và nhi u tên khácề
ØLà trò ch i di chuy n trên m t khung bao g m các ô vuông đánh ơ ể ộ ồ
s theo th t ng u nhiên v i m t ô b thi uố ứ ự ẫ ớ ộ ị ế
ØTrò ch i này cũng t n t i trong các kíchơ ồ ạ
c khác nhau, đ c bi t nh h n là 8-Puzzleỡ ặ ệ ỏ ơ
3
Gi i thi u Game 15-Puzzleớ ệ
ØN u kích th c là 3 x 3 ô, trò ch i đ c g i là 8-Puzzle ho c 9-ế ướ ơ ượ ọ ặ
Puzzle, và n u là 4 × 4 ô, trò ch i đ c g i là 15-Puzzle ho c ế ơ ượ ọ ặ
16-Puzzle, đ c đ t tên t ng ng s l ng ô và s l ng c a ượ ặ ươ ứ ố ượ ố ượ ủ
không gian
ØM c tiêu c a trò ch i là đ t các ô theo tr t t b ng cách tr t ụ ủ ơ ặ ậ ự ằ ượ
các ô đ di chuy n không gian tr ngể ể ố
Øn-Puzzle là m t v n đ c đi n cho các thu t toán mô hình hóa ộ ấ ề ổ ể ậ
liên quan đ n ếđánh giá
4
Gi i thi u Game 15-Puzzleớ ệ
§Hàm đánh giá th ng đ c s d ng cho v n đ này bao g m ườ ượ ử ụ ấ ề ồ
đ m s ô đ t sai ch và tìm ki m t ng kho ng cách Manhattan ế ố ặ ỗ ế ổ ả
gi a m i kh i v i v trí c a nó trong c u hình m c tiêuữ ỗ ố ớ ị ủ ấ ụ
§T t c hàm đánh giá đ u đ c ch p nh n, nghĩa là, s l ng di ấ ả ề ượ ấ ậ ố ượ
chuy n nhi u s không đ c đánh giá cao nh m đ m b o t i ể ề ẽ ượ ằ ả ả ố
u cho các thu t toán tìm ki m nh t đ nh ch ng h n nh A*ư ậ ế ấ ị ẳ ạ ư
5