" />
  • Thứ Tư, 18/10/2006 09:20 (GMT+7)

    Thuật giải "mã đi tuần"

    Câu hỏi :
    Tôi đang cần tìm code và giải thuật bài toán "mã đi tuần"
     

    Trả lời :

    Chúng tôi đã giới thiệu chương trình giải bài toán "mã đi tuần" bằng ngôn ngữ Pascal trong số báo tháng 05/2003, bạn có thể tìm đọc lại. Sẵn đây, chúng tôi giới thiệu lại chương trình nhưng được viết bằng ngôn ngữ VC++ để có thể dịch và chạy trên Windows. Lưu ý là chúng tôi dùng giải thuật back-tracking dựa trên bước lặp cơ bản như sau: nếu con mã đang ở vị trí ô cờ (i,j) thì nó có thể đi tiếp 1 trong 8 khả năng khác nhau xung quanh ô (i,j) hiện tại, chúng ta sẽ lần lượt thử cho con mã đi từng khả năng, nếu được thì ta sẽ tiếp tục thử tìm đường đi cho vị trí mới của con mã, nếu cả 8 khả năng đều không đi được ta sẽ lùi con mã về vị trí ô cờ ngay trước đó rồi tiếp tục thử các khả năng chưa thử. Như vậy, con mã sẽ hoặc tiến 1 bước hoặc lùi 1 bước cho đến khi hoặc tìm được kết quả hoặc không còn khả năng nào để đi thì chương trình sẽ dừng lại. Chương trình dùng 2 biến dữ liệu chính là:

    - Biến Banco là 1 dãy 8*8 phần tử, mỗi phần tử miêu tả thứ tự nước đi của con mã (từ 0 tới 63), vị trí nào con mã chưa đi qua sẽ có giá trị đầu là -1 để phân biệt.

    - Biến Nuocdi là 1 danh sách 64 phần tử lưu giữ trình tự các vị trí ô cờ mà con mã đi qua từ vị trí xuất phát nào đó do user qui định, mỗi vị trí đi qua ta nhớ lại tọa độ (i,j) và chỉ số hướng đi đã thử. Tất cả chỉ số của các dãy đều bắt đầu từ 0.

    Qui trình viết chương trình bằng VC++ 6.0 như sau: chạy VC++, chọn menu File.New.Projects.Win32 Console Application, chọn vị trí thư mục chứa Project, nhập tên Project quản lý chương trình, chọn button OK để hiển thị cửa sổ Wizard. Chọn loại Project "An empty project" rồi nhấn button "Finish" tạo Project với các thông số vừa khai báo. Sau khi Project được tạo ra, bạn chọn menu File.New.Files, chọn mục "C++ Source File", nhập tên file (thí dụ là main) để tạo ra file mã nguồn với nội dung rỗng rồi nhập đoạn chương trình sau:

     //nội dung file chương trình
     #include <stdio.h>
     #include <conio.h>
     //Khai báo kiểu và hằng cần dùng
     typedef int BOOL;
     const TRUE=1;
     const FALSE=0;
     const MAX = 7;
     
     // Kiểu miêu tả thông tin của 1 bước đi
     typedef struct {
     int x, y;
     int huong;
     } ItemRec;
     
     // Định nghĩa các biến dữ liệu chính
     int Banco[MAX+1][MAX+1];
     ItemRec Nuocdi[(MAX+1)*(MAX+1)];
     int SoNuocdi;
     int SoNghiem;
     
     // Thủ tục khởi động các giá trị đầu của chương trình
     void Khoidong() {
     int i,j;
     SoNghiem = 0;
     for (i=0; i<=MAX; i++)
     for (j=0;j<=MAX; j++)
     Banco[i][j] = -1; // con ma chua di qua o [i,j]
     printf("Nhập tọa độ hàng chứa con mã : ");
     scanf("%d",&Nuocdi[0].y);
     printf("Nhập tọa độ cột chứa con mã : ");
     scanf("%d",&Nuocdi[0].x);
     Nuocdi[0].huong = 0;
     // Thiết lập nước đi đầu tiên của con mã
     SoNuocdi =0;
     Banco[Nuocdi[SoNuocdi].x][Nuocdi[SoNuocdi].y] = 0;
     }
     // In kết quả con mã đi trên bàn cờ
     void InKetqua() {
     int h,c;
     SoNghiem = SoNghiem + 1;
     printf("Cách đi thứ : %d\n",SoNghiem);
     for (h= 0; h <=MAX; h++) {
     // Hiển thị hàng lưới ngang bàn cờ
     for (c= 0; c<=MAX;c++) printf("+----");
     printf("+\n");
     // Hiển thị nội dung hàng thứ h bàn cờ
     for (c= 0; c<=MAX;c++)
     printf("| %2d ",Banco[h][c]);
     printf("|\n");
     }
     // Hiển thị hàng lưới ngang bàn cờ cuối cùng
     for (c= 0; c<=MAX;c++) printf("+----");
     printf("+\n");
     }
     
     // Thủ tục tìm nước đi kế tiếp
     // trả về FALSE nếu không tìm được và ngược lại
     BOOL TimNuocKe() {
     int x, y;
     BOOL RetVal;
     RetVal = FALSE;
     do { // lặp tìm nước đi kế tiếp đến khi tìm được hoặc hết cách đi
     while (RetVal==FALSE && Nuocdi[SoNuocdi].huong < 8) {
     switch (Nuocdi[SoNuocdi].huong) { //thử hướng đi hiện tại
     case 0 :
     x = Nuocdi[SoNuocdi].x + 2;
     y = Nuocdi[SoNuocdi].y - 1;
     break;
     case 1 :
     x = Nuocdi[SoNuocdi].x + 1;
     y = Nuocdi[SoNuocdi].y - 2;
     break;
     case 2 :
     x = Nuocdi[SoNuocdi].x - 1;
     y = Nuocdi[SoNuocdi].y - 2;
     break;
     case 3 :
     x = Nuocdi[SoNuocdi].x - 2;
     y = Nuocdi[SoNuocdi].y - 1;
     break;
     case 4 :
     x = Nuocdi[SoNuocdi].x - 2;
     y = Nuocdi[SoNuocdi].y + 1;
     break;
     case 5 :
     x = Nuocdi[SoNuocdi].x - 1;
     y = Nuocdi[SoNuocdi].y + 2;
     break;
     case 6 :
     x = Nuocdi[SoNuocdi].x + 1;
     y = Nuocdi[SoNuocdi].y + 2;
     break;
     case 7 :
     x = Nuocdi[SoNuocdi].x + 2;
     y = Nuocdi[SoNuocdi].y + 1;
     }
     if (0<=x && x<=MAX && 0<=y && y<=MAX && Banco[x][y]==-1) {
     // nếu được thì ghi nhận
     SoNuocdi = SoNuocdi + 1;
     Banco[x][y] = SoNuocdi;
     Nuocdi[SoNuocdi].x = x;
     Nuocdi[SoNuocdi].y = y;
     Nuocdi[SoNuocdi].huong = 0;
     RetVal =TRUE;
     } else // nếu không được thì thử hướng kế tiếp
     Nuocdi[SoNuocdi].huong = Nuocdi[SoNuocdi].huong + 1;
     } //end while
     if (RetVal==FALSE && SoNuocdi != 0) {
     // nếu không tìm được nước đi kế thì lùi con mã lại 1 bước
     Banco[Nuocdi[SoNuocdi].x][Nuocdi[SoNuocdi].y] = -1;
     SoNuocdi = SoNuocdi - 1;
     Nuocdi[SoNuocdi].huong = Nuocdi[SoNuocdi].huong + 1;
     }
     } while (!RetVal && SoNuocdi);
     return RetVal;
     }
     
     // Chương trình chính
     void main() {
     Khoidong();
     while (TimNuocKe())
     if (SoNuocdi == (MAX+1)*(MAX+1)-1) {
     // nếu tìm được 1 nghiệm
     InKetqua();
     getch();
     Banco[Nuocdi[SoNuocdi].x][Nuocdi[SoNuocdi].y] = -1;
     SoNuocdi = SoNuocdi -1;
     Nuocdi[SoNuocdi].huong = Nuocdi[SoNuocdi].huong + 1;
     }
     }

    Lưu ý backtracking thuộc loại giải thuật vét cạn nên thường có thời gian tính toán rất lớn, cụ thể với bài toán trên nếu kích thước bàn cờ là 8*8 thì các máy PC hiện tại (ngay cả Pentium IV 3,1GHz) cũng phải tốn nhiều năm mới chạy xong giải thuật. Do đó để tìm được kết quả thực sự, bạn nên chọn kích thước bàn cờ 4,5,6 là vừa (khai báo lại hằng MAX = 3,4,5).

    Chuyên mục: Lập trình