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

Cờ vua là một trò chơi giải trí xuất hiện từ khoảngthế 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.

pdf17 trang | Chia sẻ: vietpd | Lượt xem: 6721 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Đề tài Bài toán 8 quân hậu, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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 I