co_phu_thuy_nho258
New Member
Link tải luận văn miễn phí cho ae Kết nối
MỤC LỤC
MỤC LỤC . 0
NỘI DUNG . 1
CHƯƠNG I: TỔNG QUAN . 1
I. LỜI MỞ ĐẦU . 1
II. MÔ TẢ BÀI TOÁN. 1
III. MỤC TIÊU CẦN ĐẠT . 2
IV. HƯỚNG GIẢI QUYẾT . 2
V. KẾ HOẠCH THỰC HIỆN . 3
CHƯƠNG II: CƠ SỞ LÝ THUYẾT . 4
I. BÀN CỜ VUA . 4
II. ĐỆ QUY (RECURSION) . 5
III. KỸ THUẬT QUAY LUI (BACKTRACKING) . 5
CHƯƠNG III: KẾT QUẢ - ỨNG DỤNG . 6
I. PHÂN TÍCH YÊU CẦU BÀI TOÁN . 6
1. Cài đặt cấu trúc dữ liệu tổ chức bàn cờ . 6
2. Cài đặt thuật toán tìm kiếm sâu kết hợp quay lui . 7
3. Hiển thị bàn cờ sau mỗi nước đi . 7
II. THIẾT KẾ GIẢI THUẬT . 8
1. Hàm LayMau . 8
2. Hàm ktdh . 8
3. Hàm KhoiTao . 8
4. Hàm SauDatHau . 9
5. Hàm VeBanCo . 9
6. Hàm VeHau . 9
7. Hàm DatQuanHau . 9
8. Hàm Try . 10
9. Hàm main . 12
III. GIỚI THIỆU CHƯƠNG TRÌNH . 13
CHƯƠNG IV: KẾT LUẬN - ĐÁNH GIÁ.15
I. KẾT QUẢ ĐẠT ĐƯỢC . 15
II. HẠN CHẾ . 15
III. HƯỚNG PHÁT TRIỂN . 16
TÀI LIỆU THAM KHẢO . 16
I. LỜI MỞ ĐẦU
Cờ vua là một trò chơi giải trí xuất hiện từ khoảng thế kỷ thứ VI và ngày càng trở
nên phổ biến trên thế giới. Bên cạnh việc chơi cờ giải trí, người ta còn suy nghĩ ra
nhiều bài toán xung quanh bàn cờ vua. Một trong những bài toán phổ biến về cờ vua
đó là bài toán “8 quân hậu”. Đây cũng là một trong nhưng bài toán nổi tiếng và quen
thuộc đối với người lập trình.
Bài toán 8 quân hậu được đưa ra vào năm 1848 bởi kỳ thủ Max Bezzel, nhiều nhà
toán học (trong đó có Gauss và Georg Cantor) đã có các công trình nghiên cứu về bài
toán này và tổng quát nó thành bài toán xếp hậu. Các lời giải đầu tiên được đưa ra bởi
Franz Nauck năm 1850, ông cũng đã tổng quát hóa bài toán này thành bài toán n quân
hậu.
Trong đề tài này, người viết sẽ cài đặt một cấu trúc dữ liệu để tổ chức bàn cờ và
cài đặt một thuật toán để máy tính tìm ra đủ 8 vị trí đặt quân hậu trên bàn cờ.
II. MÔ TẢ BÀI TOÁN
Đặt 8 quân hậu trên bàn cờ vua 8x8 sao cho không có quân hậu nào có thể tấn
công được con khác không kể đến màu sắc. Theo luật cờ vua thì một con hậu có thể
nhìn thấy những con cờ khác nằm trên hàng, hay cột, hay hai đường chéo chứa nó.
Nghĩa là phải đặt các quân hậu sao cho không có hàng, cột hay đường chéo nào trên
bàn cờ có hơn 1 quân hậu.
Hình 1: Hai cách đặt 8 quân hậu phù hợp điều kiện bài toán.
Niên luận I – Bài toán “8 quân hậu” Học kỳ II – Năm học 2010-2011
GVHD: ThS. Võ Huỳnh Trâm 2 SVTH: Trần Việt Hưng
III. MỤC TIÊU CẦN ĐẠT
Sau khi hoàn thành đề tài, cần đạt được những mục tiêu sau:
• Trước tiên phải hiểu được luật chơi cờ vua, cũng như cách tổ chức bàn cờ trên
thực tế.
• Nắm vững một ngôn ngữ lập trình để sử dụng giải quyết bài toán.
• Nắm vững lý thuyết cơ bản về cấu trúc dữ liệu và giải thuật để cài đặt bàn cờ
và cách đặt các quân hậu.
• Nắm vững và cài đặt được giải thuật tìm kiếm sâu kết hợp quay lui
(Backtracking) để giải quyết bài toán này.
• Hiển thị bàn cờ sau mỗi bước đi dưới dạng đồ họa.
• Dịch chương trình sang file thực thi.
IV. HƯỚNG GIẢI QUYẾT
Bất kỳ ai khi thử tìm lời giải cho bài toán tám quân hậu thường ngay lập tức bị
cuốn vào việc tìm cách đặt những con hậu lên bàn cờ một cách ngẫu nhiên, hay theo
một quy tắc nào đó. Và với cách nào đi nữa thì một điều chắc chắn là con hậu đặt sau
sẽ không bao giờ được nhìn thấy con hậu đã đặt trước đó. Bằng cách này, nếu may
mắn một người có thể đặt được cả tám quân hậu thỏa yêu cầu bài toán. Nếu không
may, một con hậu phải được lấy đi để đặt lại vào những chổ khác và việc tìm lời giải
được tiếp tục.
Để biểu diễn, cài đặt bàn cờ vua bằng ngôn ngữ lập trình, thoạt tiên ta nghĩ tới là
dùng mảng 2 chiều để biểu diễn vị trí từng ô vuông trong bàn cờ. Cách biểu diễn đó là
đúng, tuy nhiên trong trường hợp bài toán 8 quân hậu này, nếu ta dùng cách đó thì
không được tối ưu, sẽ dẫn tới các thao tác cồng kềnh trong việc thử các quân hậu, ở
đây ta không lập trình toàn bàn cờ vua hoàn hảo để chơi. Ta chỉ sử dụng quân hậu cho
nên chỉ cần quan tâm tới ô ở 2 giá trị, đó là ô đó có quân hậu nào khống chế (ô cấm),
hay chưa không chế (ô được phép). Nói một cách khác là một ô cờ sẽ nhận một trong
2 giá trị là cấm hay được phép, khi cài đặt vào chương trình ta sẽ dùng hai giá trị nào
đó để máy tính hiểu được hai trạng thái này.
Các bước giải quyết bài toán:
• Tại bước thứ i, ta tìm vị trí để đặt quân hậu thứ i vào ô chưa bị khống chế.
Sau đó tìm tiếp vị trí cho quân hậu thứ i+1.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỤC LỤC
MỤC LỤC . 0
NỘI DUNG . 1
CHƯƠNG I: TỔNG QUAN . 1
I. LỜI MỞ ĐẦU . 1
II. MÔ TẢ BÀI TOÁN. 1
III. MỤC TIÊU CẦN ĐẠT . 2
IV. HƯỚNG GIẢI QUYẾT . 2
V. KẾ HOẠCH THỰC HIỆN . 3
CHƯƠNG II: CƠ SỞ LÝ THUYẾT . 4
I. BÀN CỜ VUA . 4
II. ĐỆ QUY (RECURSION) . 5
III. KỸ THUẬT QUAY LUI (BACKTRACKING) . 5
CHƯƠNG III: KẾT QUẢ - ỨNG DỤNG . 6
I. PHÂN TÍCH YÊU CẦU BÀI TOÁN . 6
1. Cài đặt cấu trúc dữ liệu tổ chức bàn cờ . 6
2. Cài đặt thuật toán tìm kiếm sâu kết hợp quay lui . 7
3. Hiển thị bàn cờ sau mỗi nước đi . 7
II. THIẾT KẾ GIẢI THUẬT . 8
1. Hàm LayMau . 8
2. Hàm ktdh . 8
3. Hàm KhoiTao . 8
4. Hàm SauDatHau . 9
5. Hàm VeBanCo . 9
6. Hàm VeHau . 9
7. Hàm DatQuanHau . 9
8. Hàm Try . 10
9. Hàm main . 12
III. GIỚI THIỆU CHƯƠNG TRÌNH . 13
CHƯƠNG IV: KẾT LUẬN - ĐÁNH GIÁ.15
I. KẾT QUẢ ĐẠT ĐƯỢC . 15
II. HẠN CHẾ . 15
III. HƯỚNG PHÁT TRIỂN . 16
TÀI LIỆU THAM KHẢO . 16
I. LỜI MỞ ĐẦU
Cờ vua là một trò chơi giải trí xuất hiện từ khoảng thế kỷ thứ VI và ngày càng trở
nên phổ biến trên thế giới. Bên cạnh việc chơi cờ giải trí, người ta còn suy nghĩ ra
nhiều bài toán xung quanh bàn cờ vua. Một trong những bài toán phổ biến về cờ vua
đó là bài toán “8 quân hậu”. Đây cũng là một trong nhưng bài toán nổi tiếng và quen
thuộc đối với người lập trình.
Bài toán 8 quân hậu được đưa ra vào năm 1848 bởi kỳ thủ Max Bezzel, nhiều nhà
toán học (trong đó có Gauss và Georg Cantor) đã có các công trình nghiên cứu về bài
toán này và tổng quát nó thành bài toán xếp hậu. Các lời giải đầu tiên được đưa ra bởi
Franz Nauck năm 1850, ông cũng đã tổng quát hóa bài toán này thành bài toán n quân
hậu.
Trong đề tài này, người viết sẽ cài đặt một cấu trúc dữ liệu để tổ chức bàn cờ và
cài đặt một thuật toán để máy tính tìm ra đủ 8 vị trí đặt quân hậu trên bàn cờ.
II. MÔ TẢ BÀI TOÁN
Đặt 8 quân hậu trên bàn cờ vua 8x8 sao cho không có quân hậu nào có thể tấn
công được con khác không kể đến màu sắc. Theo luật cờ vua thì một con hậu có thể
nhìn thấy những con cờ khác nằm trên hàng, hay cột, hay hai đường chéo chứa nó.
Nghĩa là phải đặt các quân hậu sao cho không có hàng, cột hay đường chéo nào trên
bàn cờ có hơn 1 quân hậu.
Hình 1: Hai cách đặt 8 quân hậu phù hợp điều kiện bài toán.
Niên luận I – Bài toán “8 quân hậu” Học kỳ II – Năm học 2010-2011
GVHD: ThS. Võ Huỳnh Trâm 2 SVTH: Trần Việt Hưng
III. MỤC TIÊU CẦN ĐẠT
Sau khi hoàn thành đề tài, cần đạt được những mục tiêu sau:
• Trước tiên phải hiểu được luật chơi cờ vua, cũng như cách tổ chức bàn cờ trên
thực tế.
• Nắm vững một ngôn ngữ lập trình để sử dụng giải quyết bài toán.
• Nắm vững lý thuyết cơ bản về cấu trúc dữ liệu và giải thuật để cài đặt bàn cờ
và cách đặt các quân hậu.
• Nắm vững và cài đặt được giải thuật tìm kiếm sâu kết hợp quay lui
(Backtracking) để giải quyết bài toán này.
• Hiển thị bàn cờ sau mỗi bước đi dưới dạng đồ họa.
• Dịch chương trình sang file thực thi.
IV. HƯỚNG GIẢI QUYẾT
Bất kỳ ai khi thử tìm lời giải cho bài toán tám quân hậu thường ngay lập tức bị
cuốn vào việc tìm cách đặt những con hậu lên bàn cờ một cách ngẫu nhiên, hay theo
một quy tắc nào đó. Và với cách nào đi nữa thì một điều chắc chắn là con hậu đặt sau
sẽ không bao giờ được nhìn thấy con hậu đã đặt trước đó. Bằng cách này, nếu may
mắn một người có thể đặt được cả tám quân hậu thỏa yêu cầu bài toán. Nếu không
may, một con hậu phải được lấy đi để đặt lại vào những chổ khác và việc tìm lời giải
được tiếp tục.
Để biểu diễn, cài đặt bàn cờ vua bằng ngôn ngữ lập trình, thoạt tiên ta nghĩ tới là
dùng mảng 2 chiều để biểu diễn vị trí từng ô vuông trong bàn cờ. Cách biểu diễn đó là
đúng, tuy nhiên trong trường hợp bài toán 8 quân hậu này, nếu ta dùng cách đó thì
không được tối ưu, sẽ dẫn tới các thao tác cồng kềnh trong việc thử các quân hậu, ở
đây ta không lập trình toàn bàn cờ vua hoàn hảo để chơi. Ta chỉ sử dụng quân hậu cho
nên chỉ cần quan tâm tới ô ở 2 giá trị, đó là ô đó có quân hậu nào khống chế (ô cấm),
hay chưa không chế (ô được phép). Nói một cách khác là một ô cờ sẽ nhận một trong
2 giá trị là cấm hay được phép, khi cài đặt vào chương trình ta sẽ dùng hai giá trị nào
đó để máy tính hiểu được hai trạng thái này.
Các bước giải quyết bài toán:
• Tại bước thứ i, ta tìm vị trí để đặt quân hậu thứ i vào ô chưa bị khống chế.
Sau đó tìm tiếp vị trí cho quân hậu thứ i+1.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links