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

[An_Nguyen (An Nguyễn)]

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!

[rogp10]

map<int,bool> thì thà dùng vector<bool> còn hơn (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.

[An_Nguyen (An Nguyễn)]

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

[Quoc_Tuan_Le]

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.

[rogp10]

Truy cập chậm hơn. Có giới hạn thì dùng vector cho nhanh.