• Chủ Nhật, 21/12/2003 16:48 (GMT+7)

    Câu hỏi :
    Tôi có 1 số tài liệu nói về thuật toán quay lùi (backtracking) dùng để giải 1 số bài toán dùng phương pháp đệ quy, tuy nhiên tôi gặp khó khăn khi áp dụng viết chương trình “Mã đi tuần”. Mong chỉ giúp giải thuật để giải quyết bài toán này và mã nguồn bằng ngôn ngữ Pascal. Bài toán “Mã đi tuần” như sau: giả sử có con mã được đặt ở ô (i,j) trên bàn cờ 8x8 ô trống, hãy tìm tất cả các cách đi của con mã với điều kiện là mỗi cách đi, con mã phải đi hết đúng 64 ô cờ và mỗi ô cờ, con mã chỉ đi qua đúng 1 lần.

    Trả lời :
     

    Chúng tôi nghĩ là giải thuật backtracking giải bài toán “Mã đi tuần” đã được trình bày trong tài liệu mà bạn đọc. Và nếu nắm vững giải thuật thì về nguyên tắc bạn sẽ dịch được giải thuật ra chương trình máy tính dùng ngôn ngữ mà bạn ưa thích. Sau đây chúng tôi liệt kê chương trình Pascal giải bài toán này theo yêu cầu của bạn, lưu ý là giải thuật 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ì tốt, 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ử. 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), nếu 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.

    Program MadiTuan;

    {Chỉ số hàng cột lớn nhất của bàn cờ : thường là 7}

    Const Max = 7;

    {Kiểu dữ liệu chứa thông tin của 1 bước đi}

    Type ItemRec = Record

         x, y : Integer;

         huong : Integer;

    End;

    { Các biến dữ liệu chính}

    Var Banco: Array [0..7,0..7] of Integer;

        Nuocdi: Array [0..63] of ItemRec;

        SoNuocdi : Integer;

        cach : Integer;

    {Thủ tục khởi động các giá trị đầu của chương trình}

    Procedure Khoidong;

    Var i,j : Integer;

    Begin

      cach := 0;

      for i:=0 to Max do

         for j:= 0 to Max do

             Banco[i,j] := -1;

       write(‘Nhập tọa độ hàng chứa con mã : ‘);

       readln(Nuocdi[0].y);

       write(‘Nhập tọa độ cột chứa con mã : ‘);

       readln(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;

    End;

     

    {In kết quả con mã đi trên bàn cờ}

    Procedure InKetqua;

    Var h,c : Integer;

    Begin

       cach := cach + 1;

       writeln(‘Cách đi thứ : ‘,cach);

       for h:= 0 to Max do begin

          { Hiển thị hàng lưới ngang bàn cờ }

          for c:= 0 to Max do write(‘+——’);

          writeln(‘+’);

          { Hiển thị nội dung hàng thứ h bàn cờ }

          for c:= 0 to Max do

             write(‘| ‘,Banco[h,c]:2,’ ‘);

          writeln(‘|’);

       end;

      {Hiển thị hàng lưới ngang bàn cờ cuối cùng}

       for c:= 0 to Max do write(‘+——’);

       writeln(‘+’);

       {readln;}

    End;

     

    {Thủ tục tìm nước đi kế tiếp}

    Function TimNuocKe : Boolean;

    Var x, y : Integer;

        RetVal : Boolean;

    Begin

        RetVal := False;

        Repeat {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) and (Nuocdi[SoNuocdi].huong < 8) do begin

                Case Nuocdi[SoNuocdi].huong of  {thử hướng đi hiện tại}

                0 : begin

                     x := Nuocdi[SoNuocdi].x + 2;

                     y := Nuocdi[SoNuocdi].y - 1;

                     end;

                1 : begin

                     x := Nuocdi[SoNuocdi].x + 1;

                     y := Nuocdi[SoNuocdi].y - 2;

                     end;

                2 : begin

                     x := Nuocdi[SoNuocdi].x - 1;

                     y := Nuocdi[SoNuocdi].y - 2;

                     end;

                3 : begin

                     x := Nuocdi[SoNuocdi].x - 2;

                     y := Nuocdi[SoNuocdi].y - 1;

                     end;

                4 : begin;

                     x := Nuocdi[SoNuocdi].x - 2;

                     y := Nuocdi[SoNuocdi].y + 1;

                     end;

                5 : begin

                     x := Nuocdi[SoNuocdi].x - 1;

                     y := Nuocdi[SoNuocdi].y + 2;

                     end;

                6 : begin

                     x := Nuocdi[SoNuocdi].x + 1;

                     y := Nuocdi[SoNuocdi].y + 2;

                     end;

                7 : begin

                     x := Nuocdi[SoNuocdi].x + 2;

                     y := Nuocdi[SoNuocdi].y + 1;

                     end

                End;

                if (0<=x) and (x<=Max) and (0<=y) and (y<=Max) and (Banco[x,y]=-1) then begin

                {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;

               end else

                    {nếu không được thì thủ hướng kế tiếp}

                     Nuocdi[SoNuocdi].huong := Nuocdi[SoNuocdi].huong + 1;

            end;

            if (RetVal=False) and (SoNuocdi <> 0) then begin

                {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;

            end

       until RetVal or (SoNuocdi = 0);

       TimNuocKe := RetVal;

    End;

     

    {Chương trình chính}

    Begin

        Khoidong;

        while TimNuocKe do begin

            if SoNuocdi = (Max+1)*(Max+1)-1 then begin

                 {nếu tìm được 1 nghiệm}

                  InKetqua;

                  Banco[Nuocdi[SoNuocdi].x,Nuocdi[SoNuocdi].y] := -1;

                  SoNuocdi := SoNuocdi -1;

                  Nuocdi[SoNuocdi].huong := Nuocdi[SoNuocdi].huong + 1;

            end

        end

    End.

    Lưu ý giải thuật 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ì giải thuật sẽ phải xét 864 = 2192 hướng đi, các máy PC hiện tại (ngay cả Pentium IV 3,1GHz) cũng phải tốn hàng tỉ tỉ 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