bài toán xếp hậu

Bài toán xếp xếp hậu là Việc bịa tám quân hậu trên bàn cờ vua kích thước 8×8 sao mang đến không tồn tại quân hậu này hoàn toàn có thể “ăn” được quân hậu không giống, hoặc rằng không giống lên đường ko quân hậu này với để di chuyển theo quy tắc cờ vua.

Lời giải của Việc là một trong cơ hội xếp tám quân hậu bên trên bàn cờ sao mang đến không tồn tại nhì quân này đứng bên trên thẳng hàng, hoặc nằm trong cột hoặc nằm trong đàng chéo cánh. Bài toán tám quân hậu hoàn toàn có thể tổng quát tháo hóa trở thành Việc đặt n quân hậu bên trên bàn cờ n×n(n ≥ 4).

Bạn đang xem: bài toán xếp hậu

Hình hình ảnh phía trên tế bào miêu tả một tiếng giải của Việc xếp 11 quân hậu bên trên 1 bàn cờ vua 11*11. Vậy tất cả chúng ta nằm trong hợp tác vô mò mẫm tiếng giải mang đến Việc này.

Giải bài toán xếp hậu vì chưng đệ quy vô C/C++

• Để tiện trình diễn tao sử dụng thay đổi i nhằm khắc ghi những mặt hàng kể từ bên trên xuống ( 1 cho tới n). Dùng thay đổi j nhằm khắc ghi những cột kể từ trái khoáy lịch sự nên ( 1 cho tới n );
• Các thành phần phía trên thẳng hàng với chỉ số mặt hàng vì chưng nhau;
• Các thành phần phía trên nằm trong cột với chỉ số cột vì chưng nhau;
• Để tiện mang đến việc in thành quả rời khỏi thì tao chỉ in rời khỏi chỉ số những cột tuần tự động bám theo những mặt hàng kể từ bên trên xuống.
• Điều khiếu nại để tại vị một quân hậu đích khu vực là không tồn tại 2 bên trên và một cột ( chỉ số cột không giống nhau). Không với 2 quân hậu này nằm trong phía trên một đàng chéo cánh.

Ý tưởng:

• Đầu tiên tao bịa quân hậu loại nhất vô những cột bên trên mặt hàng 1 ( với n cơ hội bịa ).
• Thử bịa quân hậu 2 vào cụ thể từng cột ở mặt hàng 2 sao mang đến không trở nên quân hậu 1 kiểm soát. Với từng địa điểm của quân hậu này tao lại test bịa quân hậu loại tía vô những cột sao mang đến không trở nên những quân hậu trước kiểm soát.
• Sau lúc để kết thúc quân hậu loại tám thì in rời khỏi một cơ hội bịa.

Code C

#include<stdio.h>
#include<math.h>
int a[20];
bool Ok(int x2,int y2){
	//kiểm tra cơ hội bịa với vừa lòng không
	for(int i = 1; i < x2 ;i++)
		if(a[i] == y2 || abs(i-x2) == abs(a[i] - y2) )
			return false;
	//Nếu đánh giá không còn những tình huống vẫn ko sai thì trả về true
	return true;
}

void Xuat(int n){
	//in rời khỏi một kết quả
	for(int i=1;i<=n;i++)
		printf(" %d",a[i]);
	printf("n");
}

void Try(int i,int n){
	for(int j = 1;j<=n;j++){
		// test bịa quân hậu vô những cột từ là 1 cho tới n
		if(Ok(i,j)){
			//nếu cơ hội bịa này vừa lòng thì khắc ghi vị trí
			a[i] = j;
                        //nếu bịa kết thúc quân hậu loại n thì xuất rời khỏi một kết quả
			if(i==n) Xuat(n);
			Try(i+1,n);
		}
	}
}

int main(){
	int n = 8;// ở phía trên bản thân mang đến Việc là 8 quân hậu bên trên bàn 8*8
	Try(1,n);
	return 0;
}

Sau Khi chạy thì tiếp tục rời khỏi những thành quả ( tôi chỉ copy một không nhiều thành quả thôi )

Xem thêm: viết đoạn văn kể lại một hoạt động ngoài trời

 1 5 8 6 3 7 2 4
 1 6 8 3 7 4 2 5
 1 7 4 6 8 2 5 3
 1 7 5 8 2 4 6 3

Mình phân tích và lý giải một không nhiều câu mệnh lệnh vô lịch trình trên

Xem thêm: mô hình hiện đại mô tả sự chuyển động của electron trong nguyên tử như thế nào

• ( x2, y2) là địa điểm nhưng mà quân hậu tiếp tục bịa vô. Như vậy tất cả chúng ta con người ta vẫn bịa kết thúc x2-1 quân hậu rồi.
• Để đánh giá quân hậu này còn có bị những quân hậu trước kiểm soát hay là không. Ta tiếp tục đánh giá theo lần lượt những quân hậu ở trước với quân hậu vừa phải mới mẻ bịa vô.
• Chỉ cần phải bị một quân hậu không giống kiểm soát thì địa điểm này sẽ không thể bịa vô ( return false).
• a[i] == y2 dùng nhằm đánh giá coi quân hậu này còn có ở và một cột với những quân hậu trước cơ.
• abs(i - x2) == abs( a[i] - y2 ) dùng để đánh giá coi quân hậu này còn có phía trên đàng chéo cánh của những quân hậu trước cơ hay là không. Các chúng ta cũng có thể vẽ hình rời khỏi và tự động minh chứng nhé !

Bài viết lách bản thân cho tới đó là kết thúc đẩy. Cám ơn chúng ta vẫn bám theo dõi !