Đề tài Bài toán 8 quân hậu

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 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 1 SVTH: Trần Việt Hưng NỘI DUNG CHƯƠNG I: TỔNG QUAN 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, hoặc cột, hoặc 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 hoặc đườ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, hoặc 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. • Nếu ở bước thứ i không tìm thấy vị trí đặt của quân hậu thì chúng ta phải quay lại xét đến vị trí khác của quân hậu thứ i-1. 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 3 SVTH: Trần Việt Hưng • Trường hợp suy biến của bài toán là khi chúng ta đã đặt cho quân hậu thứ 8, nghĩa là cả 8 quân hậu đã được xếp trên bàn cờ và đúng với điều kiện. Chúng ta sẽ viết một hàm Try để giải quyết bài toán này. Công việc cần làm tại một thời điểm (một trạng thái của bàn cờ nào đó mà số quân hậu chưa đủ) là: • Đặt thêm một con hậu vào vị trí hợp lệ. • Gọi đệ quy để xử lý tương tự số hậu cần xử lý tiếp đã giảm 1. V. KẾ HOẠCH THỰC HIỆN Đề tài dự kiến hoàn thành sau 10 tuần, cụ thể như sau: • Tìm hiểu đề tài: 1 tuần. • Tìm hiểu cấu trúc dữ liệu và giải thuật sử dụng, vẽ lưu đồ: 2 tuần. • Viết code và kiểm thử: 4 tuần. • Viết báo cáo và hoàn chỉnh chương trình: 3 tuầ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 4 SVTH: Trần Việt Hưng CHƯƠNG II: CƠ SỞ LÝ THUYẾT I. BÀN CỜ VUA • Bàn cờ vua là một bảng hình vuông, gồm 8 dòng, và 8 cột, tạo ra 64 ô hình vuông với các màu đậm và nhạt xen kẽ nhau. • Đường chéo chính là đường chéo gồm các ô mà chỉ số dòng và chỉ số cột bằng nhau. • Đường chéo phụ là đường chéo đối xứng với đường chéo chính qua trục của bàn cờ. • Đườ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 2: Bàn cờ vua Hình 3: Minh họa các khái niệm trên bàn cờ vua 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 5 SVTH: Trần Việt Hưng II. ĐỆ QUY (RECURSION) Đệ quy (recursion) là phương pháp dùng trong các chương trình máy tính trong đó có một hàm tự gọi chính nó. Trong toán học và khoa học máy tính, các tính chất (hoặc cấu trúc) được gọi là đệ quy nếu trong đó một lớp các đối tượng hoặc phương pháp được xác định bằng việc xác định một số rất ít các trường hợp hoặc phương pháp đơn giản (thông thường chỉ một) và sau đó xác định quy tắc đưa các trường hợp phức tạp về các trường hợp đơn giản. Một hàm được gọi là đệ quy nếu bên trong thân hàm có lệnh gọi đến chính nó. Ví dụ: Người ta định nghĩa giai thừa của một số nguyên dương n như sau: n!=1* 2 * 3 *…* (n-1) *n = (n-1)! *n (với 0!=1) Như vậy, để tính n! ta thấy nếu n=0 thì n!=1 ngược lại thì n!=n * (n-1)! III. KỸ THUẬT QUAY LUI (BACKTRACKING) Kỹ thuật quay lui (Backtracking) như tên gọi của nó, là một quá trình phân tích đi xuống và quay lui trở lại theo con đường đã đi qua. Tại mỗi bước phân tích chúng ta chưa giải quyết được vấn đề do còn thiếu cứ liệu nên cứ phải phân tích cho tới các điểm dừng, nơi chúng ta xác định được lời giải của chúng hoặc là xác định được không thể (hoặc không nên) đi theo hướng này. Từ các điểm dừng này chúng ta quay ngược trở lại con đường mà chúng ta đã đi qua để giải quyết các vấn đề còn tồn đọng và cuối cùng ta sẽ giải quyết được vấn đề ban đầu. Quy trình đó thường được cài đặt bằng một hàm đệ quy mà trong đó mỗi thể hiện của hàm lấy thêm một biến và lần lượt gán tất cả các giá trị có thể cho biến đó, với mỗi lần gán trị lại gọi chuỗi đệ quy tiếp theo để thử các biến tiếp theo. Giải thuật quay lui tỏ ra hiệu quả trong những trường hợp mà ban đầu tưởng như có rất nhiều khả năng lựa chọn, nhưng sau đó chỉ một số ít khả năng là còn sót lại sau tiến trình kiểm tra xa hơn. Trong các bài toán xếp thời khóa biểu, chẳng hạn trong việc tổ chức các vòng đấu thể thao, sự lựa chọn thời gian cho một số trận đấu ban đầu thường là rất dễ, nhưng càng về sau, các ràng buộc sẽ làm giảm đáng kể các khả năng có thể. Trong bài toán “8 quân hậu”, ta sử dụng kỹ thuật quay lui “vét cạn”, nghĩa là phải đi tới tất cả các điểm dừng rồi mới quay lại. Phần tiếp theo đây chúng ta sẽ tìm hiểu cách hiện thực cụ thể cho bài toán này, để thấy được ý tưởng để quy và giải thuật quay lui là cốt lõi của bài toán ở dạng này. 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 6 SVTH: Trần Việt Hưng CHƯƠNG III: KẾT QUẢ - ỨNG DỤNG I. PHÂN TÍCH YÊU CẦU BÀI TOÁN 1. Cài đặt cấu trúc dữ liệu tổ chức bàn cờ Theo luật cờ vua, quân hậu ăn được quân khác nằm trên cùng hàng, cùng cột, và cùng đường chéo. Cho nên ta thấy mỗi cột chỉ có duy nhất một quân hậu. Như vậy ta có thể ký hiệu quân hậu ở dòng thứ i là i. lúc này i trở thành chỉ số dòng và việc chọn còn lại được tiến hành trên chỉ số cột, ta đặt là j. Trên bàn cờ ta thấy rằng tất cả các ô trên cùng một đường chéo cộng có tổng chỉ số i và j bằng nhau, tức là tổng chỉ số cột và chỉ số hàng. Còn các ô trên cùng đường chéo trừ thì có hiệu số i trừ j là không đổi. Bàn cờ có 15 đường chéo cộng và 15 đường chéo trừ. Như vậy, chúng ta có thể nắm giữ các ô chưa bị các quân hậu nhìn thấy bằng cách sử dụng 3 mảng: • int Cot[board_size]; với Cot[i]=1 có nghĩa là cột thứ i+1 chưa bị khống chế, Cot[i]=0 có nghĩa là cột thứ i+1 bị khống chế. • int CheoTru[2* board_size -1]; với CheoTru[i]=1 có nghĩa là đường chéo trừ thứ i+1 chưa bị khống chế, CheoTru[i]=0 có nghĩa là đường chéo trừ thứ i+1 bị khống chế. • int CheoCong[2* board_size -1]; với CheoCong[i]=1 có nghĩa là đường chéo cộng thứ i+1 chưa bị khống chế, CheoCong[i]=0 có nghĩa là đường chéo cộng thứ i+1 bị khống chế. Với cách chọn các biến như trên thì ta dễ dàng quản lý bàn cờ. Khi đặt quân hậu thì ta sẽ cấm các cột, hàng và các đường chéo cộng, chéo trừ mà quân hậu đó đứng. Tức là khi đặt hậu vào dòng i và cột j thì ta gán Cot[j-1]=0; CheoTru[i-j+7]=0; CheoCong[i+j-2]=0. Khi muốn bỏ không đặt quân hậu thì ta gán lại các giá trị bằng 1: Cot[j-1]=1; CheoTru[i-j+7]=1; CheoCong[i+j-2]=1. Cách làm như vậy rất thuận tiện và phù hợp khi ta phải thử quân hậu nhiều lần trong các trường hợp quay lui để thử lại vị trí hậu. 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 7 SVTH: Trần Việt Hưng CheoCong[i+j-2] CheoTru[i-j+7] Hình 4: Các vị trí trên bàn cờ được mô hóa theo các mảng CheoCong, CheoTru 2. Cài đặt thuật toán tìm kiếm sâu kết hợp quay lui Việc tìm kiếm vị trí đặt hậu được thiết kết bằng giải thuật đệ quy tìm kiếm sâu kết hợp quay lui, bằng cách thử từng vị trí quân hậu. Xét việc thử đặt quân hậu ở dòng thứ a: + Xét cột thứ b (b chạy từ 1 đến 8) của dòng a. Đặt i=a-1 và j=b-1, nếu vị trí (i, j) chưa bị khống chế (Nghĩa là: Cot[j]=1 && CheoTru[i-j+7]=1 && CheoCong[i+j]=1) thì ta đặt hậu ở vị trí (i, j) (Nghĩa là: ViTri[i]=b; Cot[j]=0; CheoTru[i-j+7]=0; CheoCong[i+j]=0). Nếu không đặt được trên dòng a thì chuyển sang bước 3. + Nếu đã đặt được 8 quân hậu thì dừng và đưa ra lời giải. Ngược lại, nếu chưa đủ 8 quân hậu thì ta đệ quy lại việc xét đặt quân hậu ở dòng thứ a+1. + Nếu chưa tìm được lời giải thì quay lui lại, bỏ vị trí vừa đặt (Thiết lập lại Cot[j]=1; CheoTru[i-j+7]=1; CheoCong[i+j]=1). 3. Hiển thị bàn cờ sau mỗi nước đi Việc hiển thị bàn cờ sau mỗi bước đi phụ thuộc vào thuật toán tìm kiếm sâu kết hợp quay lui đã trình bày ở trên. Bàn cờ ban đầu chưa có quân hậu nào. Quân hậu đầu tiên được người dùng tùy chọn và được hiển thị trên bàn cờ. Xét việc đặt quân hậu ở dòng tiếp theo (dòng thứ a): + Ở cột thứ b (b chạy từ 1 đến 8) của dòng a. Nếu vị trí (i,j) chưa bị khống chế thì ta hiển thị quân cờ ở vị trí này. Nếu không tìm được vị trí nào trên dòng a thì chuyển sang bước 3. + Nếu đã đặt được 8 quân hậu thì chương trình đã hiển thị thành công bàn cờ kết quả. Ngược lại, xét việc hiển thị quân hậu ở dòng thứ a+1. + Nếu chưa tìm được lời giải thì quay lui lại, xóa quân hậu vừa mới đặt . 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 8 SVTH: Trần Việt Hưng II. THIẾT KẾ GIẢI THUẬT Chương trình bao gồm hàm main() các chương trình con sau: • void LayMau(int i); • void ktdh(); • void KhoiTao(); • void SauDatHau(); • void VeBanCo(); • void VeHau(); Hàm vẽ quân hậu. • void DatQuanHau(int a, int b); Hàm đặt quân hậu tại dòng a, cột b. • void Try(int i); Hàm đệ quy, thực hiện đặt các quân hậu bắt đầu từ dòng i+1 cho đến khi đặt được 8 quân hậu và dừng khi không còn cách đặt nào khác. Các hàm LayMau, ktdh, KhoiTao, SauDatHau, VeBanCo, VeHau không chú trọng về giải thuật nên ta chỉ đi sâu vào các hàm DatQuanHau và hàm Try. 1. Hàm LayMau Hàm định nghĩa để lấy màu sử dụng trong màn hình thực thi. Với i có giá trị từ 0 đến 15 là thang màu trong hệ thống. Ví dụ: Gọi LayMau(15) để lấy màu trắng. 2. Hàm ktdh Khởi tạo đồ họa để sử dụng được màn hình Windows BGI. Mục đích của việc khởi động đồ họa là xác định thiết bị đồ họa (mh) và mốt đồ họa (mode) sẽ sử dụng trong chương trình. 3. Hàm KhoiTao Hiển thị các tiêu đề: Tên trường, tên khoa, tên đề tài niên luận, học kỳ, năm học, sinh viên thực hiện, giáo viên hướng dẫn, mô tả bài toán. Khởi tạo những giá trị ban đầu: Giá trị ban đầu cho các mảng Cot[i], CheoCong[i], CheoTru[i] có giá trị là 1 (nghĩa là chưa bị khống chế). Giá trị ban đầu cho mảng ViTri[i] là -1 (nghĩa là chưa xác định được vị trí). 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 9 SVTH: Trần Việt Hưng Nhận thông tin đầu vào (Input): Nhận thông tin về chỉ số dòng, chỉ số cốt muốn đặt cho quân hậu đầu tiên. Nếu sai yêu cầu người dùng nhập lại. 4. Hàm SauDatHau Hàm xử lý sau khi hoàn thành xong các lần đặt hậu ứng với một vị trí ban đầu. Nhận yêu cầu của người dùng có tiếp tục chương trình không rồi từ đó quyết định tiếp tục hay ngưng thực thi chương trình. Nếu tiếp tục chương trình thì gán lại các giá trị ban đầu và nhận lại thông tin đầu vào của chương trình (chỉ số dòng, chỉ số cột). 5. Hàm VeBanCo Sử dụng chế độ đồ họa để vẽ bàn cờ và một số trang trí khác trên màn hình Windows BGI. 6. Hàm VeHau Sử dụng chế độ đồ họa để vẽ quân hậu tại một vị trí nào đó trên bàn cờ. Hàm VeHau có 2 đối số. • Đối số thứ nhất: Dòng vẽ quân hậu. • Đối số thứ hai: Cột vẽ quân hậu. Ví dụ VeHau(2,3) cho phép ta vẽ quân hậu ở dòng 2, cột 3 của bàn cờ. 7. Hàm DatQuanHau Cho phép đặt quân hậu tại một vị trí nào đó trên bàn cờ. Hàm DatQuanHau có 2 đối số. • Đối số thứ nhất: Dòng đặt quân hậu. • Đối số thứ hai: Cột đặt quân hậu. Ví dụ DatQuanHau(2,3) cho phép ta đặt quân hậu ở dòng 2, cột 3 của bàn cờ. Với mỗi lần đặt quân hậu ta thực hiện các công việc: • Gán các giá trị để khống chế vị trí của quân hậu vừa đặt: ViTri[a-1]=b; Cot[b-1]=0; CheoTru[a-b+7]=0; CheoCong[a+b-2]=0. • Gọi lại hàm VeHau để vẽ quân hậu tại vị trị đang xét. 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 10 SVTH: Trần Việt Hưng Lưu đồ hàm đặt quân hậu (DatQuanHau): Hình 5: Lưu đồ hàm DatQuanHau 8. Hàm Try Tham số i của hàm Try là dòng bắt đầu việc xét đặt hậu. Trình tự thực hiện hàm Try(i) như sau: • Bước 1: Khởi đầu xét cột 1 (j=0) • Bước 2: Nếu j<8, thực hiện bước 3. Ngược lại, đưa ra kết quả và kết thúc. • Bước 3: Nếu ô tại vị trí đang xét (i, j) chưa bị khống chế thì chuyển sang với bước 4. Ngược lại, chuyển sang bước 8. • Bước 4: Đặt quân hậu vào vị trí đang xét. • Bước 5: Nếu chưa đặt đủ 8 quân hậu thì chuyển sang bước 6. Ngược lại, tăng số cách đặt hậu lên và chuyển sang bước 7. • Bước 6: Gọi đệ quy hàm Try với quân hậu ở dòng tiếp theo. • Bước 7: Bỏ quân hậu tại vị trí vừa đặt. • Bước 8: Tăng j lên 1 đơn vị (thực hiện với cột tiếp theo) và quay về bước 2. 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 11 SVTH: Trần Việt Hưng Lưu đồ giải thuật hàm Try: Hình 6:Lưu đồ hàm Try 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 12 SVTH: Trần Việt Hưng 9. Hàm main Trình tự thực hiện hàm main như sau: • Gọi hàm KhoiTao để khởi tạo các giá trị và nhận thông tin đầu vào. • Gọi hàm ktdh để khởi tạo chế độ đồ họa. • Gọi hàm VeBanCo để vẽ bàn cờ và trang trí. • Gọi hàm DatQuanHau để đặt quân hậu đầu tiên do người dùng lựa chọn. • Gọi hàm Try(row%8) để tiến hành đặt những con hậu tiếp theo cho đến khi bàn cờ đủ 8 quân hậu. • Thoát khỏi chế độ đồ họa. Lưu đồ chương trình chính: Hình 7:Lưu đồ chương trình chính 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 13 SVTH: Trần Việt Hưng III. GIỚI THIỆU CHƯƠNG TRÌNH Chương trình có giao diện khá thân thiện với người dùng. Chương trình chính là file EightQueens.exe, để chương trình này chạy được, phải cài đặt thêm thư viện đồ họa BGI. Hướng dẫn cài đặt thư viện đồ họa nằm trong file HuongDan.txt đi kèm. Khi chạy chương trình chính sẽ hiển thị giao diện: Hình 8: Giao diện chương trình chính Người dùng lần lượt nhập vào dòng và cột muốn đặt quân hậu đầu tiên lên bàn cờ. Sau khi nhập, chương trình được sẽ hiển thị trên màn hình đồ họa Windows BGI. Người dùng chọn màn hình Windows BGI và nhấn một phím bất kỳ để hiển thị xem kết quả, người dùng nhấn phím tiếp theo để xem kết quả kế tiếp. Hình 9: Màn hình kết quả 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 14 SVTH: Trần Việt Hưng Khi không còn cách đặt hậu nào ứng với vị trí quân hậu đầu tiên đã chọn, chương trình sẽ thông báo số cách đặt hậu và hỏi người dùng có muốn tiếp tục không. Hình 10: Màn hình sau khi đặt hậu Nếu người dùng chọn 1 (=có) thì chương trình sẽ quay lại như lúc ban đầu. Ngược lại, nếu người dùng chọn 0 (=không) thì chương trình sẽ hiện thông báo kết thúc. Hình 11: Kết thúc chương trình 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 15 SVTH: Trần Việt Hưng CHƯƠNG IV: KẾT LUẬN - ĐÁNH GIÁ I. KẾT QUẢ ĐẠT ĐƯỢC Sau hơn hai tháng nghiên cứu và tìm hiểu đề tài, cùng với sự hướng dẫn tận tình của các Thầy, Cô và sự giúp đỡ của bạn bè. Hôm nay, đề tài niên luận Bài toán “8 quân hậu” cơ bản đã hoàn thành và đạt được một số kết quả như sau: Về lý thuyết: • Nắm vững kiến thức lập trình C. • Rèn luyện được kỹ năng phân tích và thiết kế một chương trình. • Biết cách vận dụng cấu trúc dữ liệu để giải quyết một vấn đề. • Nắm vững được giải thuật tìm kiếm sâu kết hợp quay lui (Backtracking). • Biết cách viết một báo cáo khoa học hoàn chỉnh. Về lập trình: Đã cài đặt được chương trình Bài toán “8 quân hậu” với các chức năng đáp ứng được với yêu cầu ban đầu của đề tài như sau: • Hiểu và cài đặt được các thuật toán cũng như tổ chức được bàn cờ bằng ngôn ngữ C. • Hiển thị được bàn cờ sau mỗi bước đi; hiển thị được nhiều cách giải khác nhau với một vị trí lựa chọn ban đầu. • Chương trình chạy ổn định, giao diện thân thiện với người dùng và dễ sử dụng. • Chương trình được thiết kế dưới dạng các chương trình con độc lập nhau nên dễ dàng kiểm tra, sửa chữa cũng như phát triển chương trình. Ngoài ra, trong quá trình thực hiện niên luận, bản thân cũng đã học hỏi được rất nhiều điều bổ ích từ phía Thầy Cô và bạn bè cũng như rèn luyện tính cần cù, chịu khó, tự nghiên cứu. II. HẠN CHẾ Mặc dù có cố gắng để hoàn thành đề tài niên luận, nhưng đây là lần đầu tiên viết một chương trình hoàn chỉnh nên vẫn thiếu nhiều kinh nghiệm trong kỹ thuật lập trình cũng như trong cách tổ chức dữ liệu. Mặt khác, do thời gian hạn chế nên chương trình vẫn còn nhiều sai sót. Cụ thể như sau: 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 16 SVTH: Trần Việt Hưng • Về đồ họa, chưa cho phép người dùng chọn vị trí đặt hậu bằng chuột hay dùng bàn phím tương tác trực tiếp trên bàn cờ. • Chương trình chưa có nhiều chức năng cho người dùng lựa chọn và chức năng mang tính giải trí (như game mà người dùng có thể tự đặt hậu). III. HƯỚNG PHÁT TRIỂN Chương trình mặc dù đã đáp ứng những yêu cầu cơ bản về giải thuật, về đồ họa nhưng vẫn rất cần tiếp tục phát triển theo những hướng sau: • Phát triển thành bài toán trên bàn cờ vua lớn hơn (hoặc nhỏ hơn) 8x8 ô, với với số quân hậu lớn hơn (nhỏ hơn) 8, khi đó ta có bài toán n quân hậu. • Phát triển chương trình thành một game, người dùng có thể giải trí bằng cách tự đặt vị trí cho quân hậu. • Phát triển chương trình cho phép người dùng chọn vị trí đặt quân hậu đầu tiên ở vị trí bất kỳ trên bàn cờ bằng cách sử dụng chuột hoặc bàn phím tương tác trực tiếp lên bàn cờ. • Sử dụng các giải thuật khác như nhánh cận (Branch and Bound), tìm kiếm theo chiều sâu với Heuristic [shel], thuật toán tiến hóa (Genetic Programming) [jes] hay dùng mạng nơron [jace]... mang lại những hiệu quả khác nhau cho chương trình. • Sử dụng các ngôn ngữ lập trình khác (C++, C#, VB, Java…) để phát triển chương trình tốt hơn. TÀI LIỆU THAM KHẢO [1] GS. Lê Văn Ất. C++ và Lập trình hướng đối tượng. Chương 8. Nhà xuất bản Khoa học và Kỹ thuật. Hà nội, 1999. [2]ThS. Nguyễn Văn Linh. Giáo trình Giải Thuật. Chương 3. Đại học Cần Thơ. 2003. [1] PGS.TS Đỗ Xuân Lôi. Cấu trúc dữ liệu và giải thuật. Chương 1. Nhà xuất bản Giáo dục. 2005. 2n_h%E1%BA%ADu