Bài toán " 8 quân hậu "

Chia sẻ: Lam Phuong Huyen | Ngày: | Loại File: DOC | Số trang:15

Thêm vào BST

Báo xấu

822
lượt xem 128
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đặ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 côn khác (theo luật cờ vua ) không kể đến màu sắc , nghĩa là phải đặt các quân hậu sao cho không có hàng , cột hoặc đường chéo nào ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán " 8 quân hậu "

Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ TRƯỜNG ĐẠI HỌC TRÀ VINH KHOA KỸ THUẬT VÀ CÔNG NGHỆ BỘ MÔN CÔNG NGHỆ THÔNG TIN NIÊN LUẬN I TIN HỌC Đề tài NL06_2009: BÀI TOÁN “8 QUÂN HẬU” Giáo viên hướng dẫn : Thầy. Ngô Thanh Huy Nhóm sinh viên cùng thực hiện: Phan Thị Ngọc Nhi 210108064 Nguyễn Thành Quang 210108039 Quách Nguyễn Diễm Thu 210108063 Lớp Cao Đẳng Tin Học Niên Luận I : NL06_2009 Trang 1
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN VÀ GIÁO VIÊN CHẤM ----  ---- ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ .. .......................................................................................................................................... ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ ............................................................................................................................................ Trà Vinh, ngày….. tháng…. năm 2010 Niên Luận I : NL06_2009 Trang 2
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ Xin chân thành cảm ơn quý thầy cô Trường Đại học Trà Vinh đã tạo điều kiện thuận lợi cho chúng em thực hiện niên luận này. Xin chân thành cảm ơn quý thầy cô bộ môn Công Nghệ Thông Tin đã trang bị cho chúng em những kỹ năng lập trình cơ bản. Chúng em xin chân thành cảm ơn Thầy Ngô Thanh Huy đã tận tình hướng dẫn chúng em trong suốt thời gian thực hiện đồ án niên luận . Mặc dù đã cố gắng hoàn thành trong phạm vi và khả năng cho phép nhưng chắc chắn sẽ không tránh khỏi những thiếu sót. Chúng em kính mong nhận được sự cảm thông và góp ý của quý thầy cô và các bạn. Niên Luận I : NL06_2009 Trang 3
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ MỤC LỤC Phần 1 : GIỚI THIỆU ĐỀ TÀI 1.1 Giới Thiệu Tổng Quan : Đặ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 (theo luật cờ vua) không kể đến màu sắc, nghĩa là phải đặt các quân hậu sao cho không có hàng, cột hoặc đường chéo nào trên bàn cờ có hơn 1 quân hậu. Niên Luận I : NL06_2009 Trang 4
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ 1.2 Giới Hạn Chương Trình : Chương trình được thiết kế giới hạn trên bàn cờ 8x8 ô, giao diện Dos đơn giản không có sử dụng đồ họa. 1.3 Mục Tiêu Cần Đạt : Phải đặt được 8 con hậu lên bàn cờ và bảo đảm chúng không thể ăn lẫn nhau theo luật cờ vua quốc tế. Hiển thị bàn cờ với số quân cờ đã được sắp xếp. Hiển thị lần lược từng ván một để dễ xem, và kiểm tra. Phải tìm ra đủ đáp án của bài toán. Phải chính xác, thời gian thực thi chương trình nhanh. 1.4 Hướng Giải Quyết : Theo luật cờ vua, một hoàng hậu có thể chiếm các quân khác nằm ở cùng dòng, hay cùng cột, hay cùng đường chéo; Do đó suy ra rằng mỗi cột chỉ chứa một hoàng hậu, và việc chọn chỗ cho hoàng hậu thứ j có thể giới hạn được ở cột thứ j, và quá trình chọn vị trí cho hoàng hậu thứ j sẻ được tiến hành tìm kiếm từ dòng 0 đến dòng 7 của cột j. Dùng các hàm để đơn giản hóa việc lặp lại công việc tìm vị trí Hậu. Phần 2 : CƠ SỞ LÝ THUYẾT 2.1 Các Định Nghĩa : • Bàn cờ là một bảng vuông 8x8, nên ta dung một mảng 2 chiều với kích thước [8,8] để tổ chức bàn cờ. • Các ô nằm theo chiều ngang là các dòng, các ô nằm dọc gọi la các cột. Niên Luận I : NL06_2009 Trang 5
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ • Đường chéo chính là đường chéo mà các hiệu số dòng và cột bằng nhau. • Đường chéo phụ là đường chéo mà các tổng số dòng và cột bằng nhau. • Đường chéo Trừ là đường chéo song song với đường chéo chính. • Đường chéo Cộng là đường chéo song song với đường chéo phụ. Hình ảnh minh họa đường chéo Trừ và đường chéo Cộng Đường chéo Trừ của ô a[i][j] là đường chéo chứa các phần tử a[i-k][j-k] khi k tăng bắt đầu từ 1. Ví dụ như hình bên dưới ta có ô a[i][j] là a[4][3] với k=1 thì ta được ô a[3][2] tương tự khi k tăng lên nữa thì ta được các ô nằm trên cùng đường chéo với ô a[4][3] là: a[3][2],a[2][1],a[1][0]. đường chéo Trừ 0 1 2 3 4 5 6 7 0 1 2 X 3 4 5 6 Niên Luận I : NL06_2009 Trang 6
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ 7 đường chéo Cộng Đường chéo Cộng của ô a[i][j] là đường chéo chứa các phần tử a[i+k] [j-k] khi k tăng bắt đầu từ 1. Ví dụ như hình bên trên ta có ô a[i][j] là a[4][3] với k=1 thì ta được ô a[5][2] tương tự khi k tăng lên nữa thì ta được các ô nằm trên cùng đường chéo với ô a[4][3] là: a[5][2],a[6] [1],a[7][0]. 2.2 Thuật Toán : Đệ qui là phương pháp tính toán dựa vào việc gọi lại hàm nhiều lần. Trong đó mỗi lần gọi hàm thì các đối số trong hàm sẽ giảm đi và cuối cùng là kết thúc hàm khi không còn giá trị nào để gọi nửa tức hàm đã tối giản. Phần 3 : PHÂN TÍCH - HIỆN THỰC 3.1 Công Cụ Lập Trình : Ngôn ngữ lập trình C, với các phần mềm : Visual C++ Borland C++ 3.1 Turbo C++ 3.0 Nhưng chúng em đã chọn Turbo C++ 3.0 để viết chương trình này. 3.2 Giới Thiệu Chương Trình : 3.2.1 Giao diện chương trình : Niên Luận I : NL06_2009 Trang 7
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ Chương trình có giao diện Dos đơn giản, thân thiện, dễ dùng. Có những phím tắt giúp cho quá trình sử dụng được thuận tiện với các phím tắt : Bấm ESC để thoát chương trình. Bấm phím bất kì để hiện các bàn cờ đã được sắp xếp. Niên Luận I : NL06_2009 Trang 8
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ Bấm phím bất kì để lần lượt hiện các bàn cờ đã được sắp xếp. 3.2.2 Các modules chương trình con :  Các ký hiệu được định nghĩa trong chương trình: TRUE: có giá trị là 1 FALSE : có giá trị là 0 BOARDSIZE : có giá trị là 8 DIAGONAL (2*BOARDSIZE-1) : cách tính đường chéo queenCol[BOARDSIZE] : vị trí thẳng đứng của con Hậu colFree[BOARDSIZE] : xét chiều thẳng đứng có free (rỗng) hay không upFree[DIAGONAL] : xét đường chéo lên có free (rỗng) hay không downFree[DIAGONAL] : xét đường chéo xuống có free (rỗng) hay không  Các hàm được định nghĩa trong chương trình: void addQueen() : đặt hậu vào vị trí, kiểm tra hậu có đặt được hay không nếu được thì gọi hàm xuất hậu (writeBoard), ngược lại thì gọi lại Niên Luận I : NL06_2009 Trang 9
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ chính nó. Bước gọi lại hàm addQueen là cấu trúc đệ qui của bài. Kết quả trả về dưới dạng tọa độ. void writeBoard() : là hàm xuất kết quả ra màn hình bằng thao tác chuyển từ tọa độ của addQueen sang đồ họa nhờ vào cấu trúc Switch...Case, với mỗi tọa độ là một dòng, tương ứng với số con hậu đang đặt. 3.3 Chương Trình và Lưu Đồ Giải Thuật : 3.3.1 Hàm addQueen() 3.3.1.1 Chương trình: Hàm nhận giá trị là vị trí của một phần tử trong bàn cờ vua do cấu trúc duyệt mảng trong thân chương trình chính đã tạo ra. Đầu tiên tăng số dòng chứa hậu lên một, tiếp theo dùng vòng lặp để duyệt từng phần tử cột trong hàng hiện tại. Nếu tìm được vị trí thích hợp để đặt hậu thì thay đổi giá trị của các hàm xét đường chéo, ngang, dọc thành đã tồn tại một hậu (false). Kế tiếp xét nếu số con hậu đã đủ tám con thì sẻ tiến hành gọi hàm writeBoard() để in bàn cờ, ngược lại số hậu chưa đủ thì sẽ tiếp tục tìm thêm số hậu còn thiếu bằng việc gọi lại hàm addQueen(). Việc gọi lại hàm addQueen sẽ được thực hiện n lần. Đây cũng là phần đệ quy của bài toán này. Trong trường hợp hậu vừa đặt không hợp yêu cầu, tức là hậu ăn nhau thì ta phải hủy vị trí vừa đặt hậu, quay về một bước đồng thời cũng trừ ra một con hậu hiện tại. 3.3.1.2 Lưu đồ: Niên Luận I : NL06_2009 Trang 10
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ BEGIN addQueen for (col=0;col
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ tọa độ từ 0 đến 7 tương ứng. 3.3.2.2 Lưu đồ: BEGIN writeBoard() for(i=0;i
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ BEGIN Tạo bàn cờ Duyệt Vị Trí Trống Gọi Hàm addQueen() Gọi Hàm writeBoard() Xuất Kết Quả END Niên Luận I : NL06_2009 Trang 13
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ Phần 4 : KẾT LUẬN – ĐÁNH GIÁ 4.1 Kết Quả Đạt Được : Giải thuật tìm ra được 736 cách đặt Hậu tương ứng với 92 bàn cờ. Là tất cả các giải thuật của bài toán. Thời gian xử lý của bài toán tương đối nhanh chóng, đạt được yêu cầu về phần cứng, máy tính cấu hình thấp vẫn chạy được. Có thêm kiến thức về phương pháp đệ quy, quay lùi. Học được cách làm việc theo nhóm tập thể. Học được cách thảo luận nhóm. Nắm vững hơn phương pháp lập trình theo hàm. Học thêm cách tìm kiếm thông tin trên internet. 4.2 Hạn Chế : Do hạn chế về kiến thức lập trình cũng như thời gian thực hiện chương trình nên kết quả đạt được còn nhiều hạn chế. Chưa tận dụng hết độ mạnh của C về đồ họa nên giao diện của chương trình không đẹp. Bài toán tám quân hậu có 92 lời giải khác nhau. Nếu không phân biệt các lời giải là ảnh của nhau qua phép đối xứng, phép quay bàn cờ thì chúng chỉ có 12 lời giải đơn vị. Chưa tìm ra được phương pháp rút gọn giải thuật hơn nữa để nâng cao chất lượng chương trình. 4.3 Hướng Phát Triển : Cần ghép thêm đồ họa để giao diện chương trình sinh động hơn. Chương trình có thể mở rộng ra thành bài toán 10 quân hậu hoặc l ớn hơn nữa nhưng thời gian để đặt được hết số quân hậu vào bàn cờ là rất lâu vì phải xét quân Hậu rất nhiều lần. Có thể cho người dùng nhập số quân Hậu tùy ý. Niên Luận I : NL06_2009 Trang 14
Trường Đại Học Trà Vinh Khoa Kỹ Thuật và Công Nghệ Dựa trên giải thuật đã có để xây dựng đồ họa cho chương trình. Cần phải tối ưu hơn nửa giải thuật. TÀI LIỆU THAM KHẢO [1] Cấu trúc dữ liệu và giải thuật. Đỗ Xuân Lôi. Chương 3. Nhà xuất bản Khoa học và Kỉ thuật, Hà Nội 1996. [2] Cấu trúc dữ liệu và giải thuật. Đoàn Trọng Huấn. Trường Đại học Trà Vinh. [3] Phương pháp giải các bài toán trong tin học. Trần Đức Huyên. Trang 33 – 39. Nhà xuất bản giáo duc. Tháng 4 – 2001. [4] Bài giảng Nhập môn lập trình. Khoa Kỹ Thuật - Công Nghệ, Đại Học Trà Vinh. [5] Một số tài liệu tham khảo trên mạng internet Link: http://vi.wikipedia.org/wiki/Quay_lui http://ddth.com http://congdongcviet.com http://cuasotinhoc.vn http://wikiversity.org Niên Luận I : NL06_2009 Trang 15