Bài toán xếp 8 quân hậu

Giới thiệu bài toán: Quân hậu trên bàn cờVua có thể ăn theo hàng, cột, đường chéochứa nó. Tìm cách đặt 8 quân hậu trên bàn cờsao cho không quân nào ăn được của quânnào
Nội dung trích xuất từ tài liệu:
Bài toán xếp 8 quân hậuBàitoánxếp8quânhậu1.Giới thiệu bài toán: Quân hậu trên bàn cờVua có thể ăn theo hàng, cột, đường chéochứanó.Tìmcáchđặt8quânhậutrênbàncờsao cho không quân nào ăn được của quânnào2.Ýtưởngthuậttoán:Mộtconhậuxếpởmộtvịtríbấtkỳtrênbàncờthìđểtìmđượcvịtrícủaconhậutiếptheotaphảixéttheo3hướngnhưhìnhsau: 1Môhìnhbàitoán Các con hậu tiếp theo phải được chọn ở các vị trí không nằm trên các đường dọc, đường ngang và đường chéo của con các con hậu trước. 2 Cácbướcgiảiquyếtbàitoán• Tatìmvịtríđểđặtchoconhậuthứi,vớiconhậu thứ i thì ta phải xét xem trên các hướng của nó sauđótìmtiếpvịtríchoconhậuthứi+1.• Nếu ở bước thứ i không tìm thấy vị trí đặt của conhậuthìchúngtaphảiquaylạixétđếnvịtrí kháccủaconhậuthứi–1.• Trườnghợpsuybiếncủabàitoánlàkhichúngta đã đặt cho con hậu thứ 8 có nghĩa là cả 8 con hậu đã được xếp trên bàn cờ và thoả mãn điều kiệnlàcácconhậukhôngthểănđượcnhau. 3 Bàitoántìmđườngđibằngchutrình HamiltonGiớithiệubàitoán:Mộtngườikháchdulịchmuốnđi thăm n thành phố được đánh số từ 1 đến n.Mạng lưới giao thông giữa n thành phố này là 2chiềuvàđượcchobởimatrậnA[i,j]trongđóA[i,j]=1nếucóđườngđigiữathànhphốivàthànhphốj, A[i,j] = 0 trong trường hợp ngược lại. Thiết lậpđườngđichongườikháchthôngbáotồntạiđườngđihoặckhôngtồntạiđườngđi. 4 Môhìnhbàitoán•Chúngtacófilecón+1dòngnhưsau: – Dòng1:Ghisốnguyêndươnglànthànhphố – Dòngi+1:(1≤i≤n):ghinsốnguyênkhôngâm A[i,1] A[i,2]…A[i,n] cho biết có đường đi hay khônggiữahaithànhphốivàj(1≤j≤n).•Kếtquảtồntạihaykhôngtồntạiđườngđi. 5 Kếtquả: 0 0 1 1 1 0 0 1 1 1  ChutrìnhHamiltonnhư sau: 1 1 0 1 1 1 1 1 0 1 132451 1 1 1 1 0 5 Cácbướcgiảiquyếtbàitoán• Tìmhếttấtcảmọikhảnăngcủađườngđi (Sau khi đi qua đường đi nào thì xoá bỏ đườngđiđó)vàkiểmtraxemđườngđinày cóquađủnđỉnhcủađồthịhaykhông. 6 ThủtụcmôtảthuậttoánProcedureHamilton(k:byte);vari:byte;Beginifk=n+1theninkqelsefori:=1tondoif(a[c[k1],i]>0)andnot(b[i])thenbegina[c[k1],i]:=0;c[k]:=i;b[i]:=true;hamilton(k+1);a[c[k1],i]:=1;c[k]:=0;b[i]:=false;end;End; 7