Giải thuật quay lui là thế nào??????

[ndphuong74]

Có ai hiểu giải thuật quay lui là như thế nào không? giúp mình với. Bài toán 8 hậu là bài toán điển hình của giải thuật quay lui vậy quay lui thể hiện ở đâu trong bài 8 hậu:
code bài 8 hậu:

/* Bai toan tam hoang hau */
#include <stdio.h>
#include<conio.h>
int dong[8], cot[8], cheoxuoi[15], cheonguoc[15];

int socach = 0;

void print ()
{
int i;
printf("\n");

if (socach %5==0)


getch();

for (i=0; i<8; i++)
{
printf("%3d", dong[i]);
}
}

void thu(int i)
{
int j;
for (j=0; j<8; j++)
{
if (cot[j] == 1 && cheoxuoi[i+j] ==1 && cheonguoc[i-j+7] == 1)
{
dong[i] = j;
cot[j] = 0;
cheoxuoi[i+j] = 0;
cheonguoc[i-j+7] = 0;
if (i<7)
thu(i+1);
else
{
print();
socach++;
}
cot[j] = 1;
cheoxuoi[i+j] = 1;
cheonguoc[i-j+7] = 1;
}
}
}

void tim()
{
int i, q;

for (i=0; i<8; i++)
{
cot[i] = 1;
dong[i] = -1;
}
for (i=0; i<15; i++)
{
cheoxuoi[i] = 1;
cheonguoc[i] = 1;
}
thu(0);
}

void main()
{
tim();
getch();
}

[kimduquan]

bạn thử dùng thêm quy hoạch động để làm thì nó sẽ chạy nhanh hơn.Mình chưa hiểu lắm về giải thuật của bạn.còn giải thuật quay lui thì đơn giản lắm ,khi bạn thực hiện 1 bước nào đó trong chương trình thì bạn lưu lại tham số đầu vào rồi bạn tiếp tục thực hiện bước tiếp theo nếu bước tiếp theo bị sai hoặc ko thực hiện được thì bạn làm lại bước đang làm( tất nhiên phải loại bỏ đi phương án sai đã làm).để cài đặt bài 8 hậu thì bạn làm như sau ,bạn đặt con hậu đầu tiên rồi tìm tất cả các vị trí ko bị chiếu bởi con hậu vừa đặt,lưu lại rồi gọi đệ quy dặt con hậu tiếp theo với điều kiện các vị trí của con hậu tiếp theo phải nằm trong bảng phương án của con hậu trước đó,sau khi bảng phương án ko còn phương án nào thì bắt đầu kiểm tra xem đã xếp được 8 hậu chưa ,nếu chưa thì quay lại dặt hậu với bảng phương án ban đầu đã bỏ đi phương án sai.

[ndphuong74]

Cái này là code mình tìm được trên mạng, nhưng mình không hiểu cho lắm. Mình cũng có nghĩ tới cách của bạn nhưng mình làm thì không biết phải quay lại như thế nào, bạn có code không cho mình tham khảo đi. Theo mình làm thì mình dùng 2 dòng for một dòng thì tăng theo dòng còn dòng kia thì tăng theo cột.
Trước tiên mình xét cot0: đặt quân hậu ở dong0 sau đó tăng dòng lên dong1,dong2,....dong7 không đặt được quân hậu.
Sau đó xét tiếp cot2: dong0,dong1 không đặt được dong2 đặt được
sau đó xét cột tiếp theo.....
Rồi tới cột thứ 5 là không đặt được quân hậu nào hết, tất cả các dòng đều bị khống chế bởi các quân hậu trước. Bây giờ dùng giải thuật quay lui để quay lại nhưng em không biết làm sao để quay lại. Mong bạn chỉ giúp..........thank!!!!!!!!

[kimduquan]

trời ơi code đó nó dài và khá rắc rối hồi trước mình viết ra mà bây giờ còn ko hiểu nổi tại sao mình viết được nữa.thật ra cùng 1 thuật toán nhưng sử dụng với từng cấu trúc dữ liệu khác nhau thì khác nhau ,đối với bài này thì mình khai báo 1 cấu trúc data chứa dữ liệu cho việc đặt 1 con hậu gồm có 3 thành phần 1 chứa số con hậu đã đặt ,t.phần 2 chứa bảng các phương án (vị trí)để đặt con hậu ,t.phần 3 chứa số phương án của bảng phương án,trong hàm đặt hậu ta đặt hậu bằng cách lấy phương án đầu tiên của bảng phương án lưu vào mảng kết quả ,rồi xóa phương án đó ra khỏi bảng phương án,tiếp theo ta tạo 1 bảng phương án mới bằng cách bỏ đi những phương án ko phù hợp(nghĩa là những vị trí trên bàn cờ bị con hậu vừa đặt chiếu tới),tăng số con hậu đã đặt lên 1 rồi tiếp tục gọi đệ quy với tham số truyền vào là bảng phương án mới cho đến khi ko còn phưong án nào thì ta bắt đầu xét :nếu số con hậu đã đặt <8 thì ta gọi đệ quy nhưng với tham số truyền vào là bảng phương án ban đầu đã bỏ đi 1 phưong án,còn nếu ko thì dừng chương trình.

[maivancuong46e3]

ai giúp mình với: mình cần biết định nghĩa thế nào là phương pháp quay lui? cảm ơn cac bạn nhiều nha.