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…

Gió viết 21:17 ngày 30/09/2018

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:

var hang: array[1..8]  of boolean;
cot: array[1..8]  of boolean;
cheo_chinh: arry[2..16]  of boolean;
cheophu: arry[-7..7]  of boolean;

................
{khi dat tai o (x,y)}
hang[y]:true;
cot[x]:=true;
cheo_chinh[x+y]:=true;
cheo_phu[x-y]:=true;



Sáng Béo viết 21:14 ngày 30/09/2018

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á)

Bài liên quan
0