30/09/2018, 19:10
Lỗi thuật toán quay lui sắp xếp quân hậu?
Code e viết như sau ạ:
program QUANHAU;
uses crt;
var a: array[0..8,0..8] of integer;
d,n: integer;
procedure Try(i: integer);
var p,q,j,k: integer;
begin
for p:=1 to 8 do
for q:=1 to 8 do
begin
(* Kiem tra hang ngang va cot doc, neu da co quan hau thi bo qua vi tri nay *)
j:=1;
while (j<=8) do
begin
if (a[p,j]=1) or (a[j,q]=1) then break;
inc(j);
end;
if j<9 then continue;
(* Kiem tra 2 duong cheo, neu da co quan hau thi bo qua vi tri nay *)
j:=-7;
while (j<=7) do
begin
if (p-j>0) and (p-j<9) and (q-j>0) and (q-j<9) then
if (a[p-j,q-j]=1) then break;
if (p+j>0) and (p+j<9) and (q-j>0) and (q-j<9) then
if (a[p+j,q-j]=1) then break;
inc(j);
end;
if j<8 then continue;
(* Neu vi tri (p,q) hien tai co the dat quan hau *)
(* Neu da du quan hau thi in ra cac vi tri *)
if i=n then
begin
inc(d);
for j:=1 to 8 do
for k:=1 to 8 do
if a[j,k]=1 then write('(',j,',',k,') ');
writeln('(',p,',',q,')');
end
(* Neu chua du thi tim vi tri cua quan hau tiep theo *)
else
begin
a[p,q]:=1; (* Danh dau vi tri da duoc dat quan hau *)
Try(i+1);
a[p,q]:=0; (* Bo danh dau vi tri nay *)
end;
end;
end;
begin
clrscr;
fillchar(a,sizeof(a),0);
write('n = '); readln(n);
d:=0;
Try(1);
writeln('Co ',d,' cach sap xep!');
end.
E không hiểu sao nó ra rất nhiều kết quả / ra sai ạ.
Anh chị nào nhìn ra thì khai sáng cho em với ạ.
E cảm ơn…
Bài liên quan
Bạn cần miêu tả đề bài
Thuật toán của bạn bị lăp vô hạn. DK dừng cho i? khi
i=n
? Có 8 hàng,8 cột, 15 đường chéo chính, 15 đường chéo phụ. khi một quân hậu ở vị trí(x,y)
nó sẽ kiểm soat các đường theo công thức:Bài toán là cho bàn cờ 8x8, in ra tất cả cách có thể đặt n quân hậu vào bàn cờ.
ý mình muốn dùng ma trận a để mô tả bàn cờ hiện tại. a[i,j] = 1 là có quân hậu.
mình chỉ muốn dùng 1 ma trận a thôi. mà sao điều kiện dừng của mình là i=n rồi mà sao nó cứ lặp vô hạn vậy? (với n bé như 1,2 thì nó hữu hạn, 3,4,… chắc cũng hữu hạn nhưng chạy lâu quá)