Nhờ giải thích thuật toán n hậu

E mới học về phần quay lui, bài đầu tiên em học là về bài toán quân hậu.
Đặt n quân hậu vào bàn cờ n*n, sao cho chúng không tấn công nhau. Thầy e có lời giải như này:

struct hau{
	int n, x[100], dem = 0;
	map<int,bool> R, D, T;
	void TRY(int k){
		
		if(k == n){
			cout << "\n" << ++dem << " : ";
			for(int i = 1; i <= k; i++) cout << " " << x[i];
			return;
		}
		for(int i = 1; i <= n; i++)
		if(R[i] == 0 && D[k+1-i] == 0 && T[k+1+i] == 0){
			R[i] = D[k+1-i] = T[k+1+i] = 1;
			x[k+1] = i;
			TRY(k+1);
			R[i] = D[k+1-i] = T[k+1+i] = 0;  //lui
		}
	}
	void sol(){
		cin >> n;
		TRY(0);
	}
};
int main()
{
	hau H;
	H.sol();
}

Mọi người có thể giải thích cho e cái đoạn

void TRY(int k){
		
		if(k == n){
			cout << "\n" << ++dem << " : ";
			for(int i = 1; i <= k; i++) cout << " " << x[i];
			return;
		}
		for(int i = 1; i <= n; i++)
		if(R[i] == 0 && D[k+1-i] == 0 && T[k+1+i] == 0){
			R[i] = D[k+1-i] = T[k+1+i] = 1;
			x[k+1] = i;
			TRY(k+1);
			R[i] = D[k+1-i] = T[k+1+i] = 0;  //lui
		}
	}

này hoạt động như nào với ah, e không hiểu lắm. E cảm ơn!

map<int,bool> thì thà dùng vector<bool> còn hơn :smiley: (rất là tối ưu) Hạn chế sử dụng std::map.

Đặt một quân hậu thì khóa cả cột và 2 đường chéo, rất hay.

4 Likes

Nhưng tại sao lại hạn chế sử dụng std::map ạ?

hàm try bạn cứ tưởng tượng khi đã đặt được 7 quân hậu đúng vị trí còn con thứ 8 đặt vào thì ko hợp lệ. Suy ra, con thứ 7 chưa đúng nên phải quay lui. Tức là thoát đệ quy nên mình phải gán nó lại bằng 0 tức là chưa đặt con thứ 7. Cứ thế quay lui cho tới khi đặt đc con thứ 8. Nhưng mà xong con thứ 8 rồi nó vẫn quay lui để tìm thêm lời giải khác.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?