Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Dùng backtracking lập trình bài 8 con hậu không chạy được?

  1. #1
    Ngày gia nhập
    08 2011
    Bài viết
    3

    Mặc định Dùng backtracking lập trình bài 8 con hậu không chạy được?

    Em dùng backtracking để làm bài 8 con hậu, viết xong chạy nhưng bị lỗi, ngồi chỉnh sửa cả buổi tối mà cuối cùng vẫn không được, em ko hiểu tại sao, mong các bro góp ý. em xin chân thành cám ơn
    Code của em ạ:

    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. int t[8];
    4. bool t2[22][22];
    5. void khoidau()
    6. {
    7.      for (int a = 7;a<15;a++)
    8.          for (int b = 7;b<15;b++)
    9.              t2[a][b]=1;
    10. }
    11. void an (int ngang, int doc)
    12. {
    13.      for (int a = 0;a<=7;a++)
    14.      {
    15.          t2[ngang][a+7]=0;
    16.          t2[a+7][doc]=0;
    17.          t2[ngang+a][doc+a]=0;
    18.          t2[ngang-a][doc+a]=0;
    19.          t2[ngang+a][doc-a]=0;
    20.          t2[ngang-a][doc-a]=0;
    21.      }
    22. }
    23. void inra ()
    24. {
    25.      for (int a = 0;a <= 7;a++)
    26.      {
    27.          cout << "Hau hang "<< a+1<<" o cot: "<<t[a]+1;
    28.          cout <<endl;
    29.      }
    30.      cout<<endl<<endl;
    31.      khoidau();
    32. }
    33. void backtrack(int i)
    34. {
    35.      for (int j = 0;j <= 7;j++)
    36.      {
    37.          if (t2[i+7][j+7])
    38.          {
    39.                  t[i]=j;
    40.                  an(i+7,j+7);
    41.                  if (i<7)
    42.                      backtrack(i+1);  
    43.                  else
    44.                      inra ();
    45.          }
    46.      }
    47. }
    48. int main()
    49. {
    50.     khoidau();
    51.     backtrack (0);                              
    52.     return 0;
    53. }
    Đã được chỉnh sửa lần cuối bởi darkangeldn : 24-08-2011 lúc 10:16 PM.

  2. #2
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Dùng back-tracking thì bao giờ cũng phải có phần undo, tức là phải đảm bảo sau khi back thì trạng thái giữ nguyên như cũ. Bạn thử viết lại đi nha gặp khó khăn mọi người sẽ giúp tiếp

    hint: dùng int t2[22][22], đánh dấu / undo bằng cách tăng / giảm giá trị của mỗi ô

  3. #3
    Ngày gia nhập
    08 2011
    Bài viết
    3

    hix, cảm ơn bác, nhưng hình như em có cho phần undo vào rùi mà?
    Code:
    if (i<7)
                         backtrack(i+1);  
                     else
                         inra ();
    khi i=7, nó sẽ inra, và trong inra có hàm khoidau đưa tất cả các ô trong ma trận 8x8 trung tâm về 1 như cũ
    Code:
    void inra ()
    {
         for (int a = 0;a <= 7;a++)
         {
             cout << "Hau hang "<< a+1<<" o cot: "<<t[a]+1;
             cout <<endl;
         }
         cout<<endl<<endl;
         khoidau();
    }

  4. #4
    Ngày gia nhập
    07 2011
    Bài viết
    160

    Rất tiếc, undo đó của bạn làm chưa đúng. Cần undo sau mỗi bước back, chứ không phải reset về trạng thái ban đầu khi tìm ra kết quả. Cái undo sai đó cần được bỏ đi.

    Mình sửa giúp bạn luôn:
    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. int t[8];
    4. int t2[22][22];
    5. void khoidau()
    6. {
    7.      for (int a = 7;a<15;++a)
    8.          for (int b = 7;b<15;++b)
    9.              t2[a][b]=0;
    10. }
    11. void an (int ngang, int doc, int d=1)
    12. {
    13.      for (int a = 0;a<=7;a++)
    14.      {
    15.          t2[ngang][a+7]+=d;
    16.          t2[a+7][doc]+=d;
    17.          t2[ngang+a][doc+a]+=d;
    18.          t2[ngang-a][doc+a]+=d;
    19.          t2[ngang+a][doc-a]+=d;
    20.          t2[ngang-a][doc-a]+=d;
    21.      }
    22. }
    23. void inra ()
    24. {
    25.      for (int a = 7;a < 15;a++)
    26.      {
    27.          cout << "Hau hang "<< a - 6 << " o cot: " << t[a]-6;
    28.          cout <<endl;
    29.      }
    30.      cout<<endl<<endl;
    31. }
    32. void backtrack(int i)
    33. {
    34.      for (int j = 7;j < 15;j++)
    35.      {
    36.          if (t2[i][j] == 0)
    37.          {
    38.                  t[i]=j;
    39.                  an(i,j);
    40.                  if (i<14)
    41.                      backtrack(i+1);
    42.                  else
    43.                      inra ();
    44.                  an(i,j,-1);
    45.          }
    46.      }
    47. }
    48. int main()
    49. {
    50.     khoidau();
    51.     backtrack (7);
    52.     return 0;
    53. }

    Side note:
    - Mình đã đồng nhất luôn sử dụng trong khoảng 7->15 và chỉ trừ đi (để về khoảng 1->8) khi in kết quả.
    - Nếu là bạn, mình sẽ không "căn ke" thật chuẩn giữa 7, 15 với 22
    Cứ khai báo t[30][30] rồi dùng trong khoảng từ 11->18 cũng chẳng tốn đáng hơn là bao mà dễ code, dễ nhìn hơn 1 tẹo (khi in ra thì trừ 10 cho tròn)
    - 2 lệnh set t2[ngang-a][doc+a]t2[ngang-a][doc-a] có vẻ hơi thừa (hàng ngang - a đã đi qua rồi).
    Đã được chỉnh sửa lần cuối bởi fbchicken : 25-08-2011 lúc 10:52 AM.

  5. #5
    Ngày gia nhập
    08 2011
    Bài viết
    3

    cảm ơn bác nhiều em hiểu rồi

Các đề tài tương tự

  1. Cách làm phần mềm Hỏi người dùng có chắc chắc tắt máy không:
    Gửi bởi Dlean7 trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 10-12-2012, 07:26 PM
  2. Kỹ thuật C++ Dùng đa luồng trong C++ sao lại chạy chậm đi! help??
    Gửi bởi vietduc trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 14-08-2011, 01:14 PM
  3. BackTracking Giải thuật tìm đường đi sao cho thời gian ngắn nhất?
    Gửi bởi y5k72pk trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 16-06-2011, 06:31 AM
  4. giải thích về backtracking?. Ai giúp mình với!!!
    Gửi bởi vanduong91 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 02-12-2010, 10:25 AM
  5. Có một chút trục trặc với 8 queens-backtracking!
    Gửi bởi PDV trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 13-12-2008, 06:36 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn