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

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

Lời giải của vấn đề là 1 cơ hội xếp tám quân hậu bên trên bàn cờ sao mang lại không tồn tại nhị quân nào là đứng bên trên đứng thảng hàng, hoặc nằm trong cột hoặc nằm trong lối 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 vấn đề đặ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 điều giải của vấn đề 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 điều giải mang lại vấn đề này.

Giải bài toán xếp hậu tự đệ quy vô C/C++

• Để tiện trình diễn tao người sử dụng phát triển thành i nhằm ghi lại những sản phẩm kể từ bên trên xuống ( 1 cho tới n). Dùng phát triển thành j nhằm ghi lại những cột kể từ trái khoáy sang trọng nên ( 1 cho tới n );
• Các thành phần phía trên đứng thảng hàng với chỉ số sản phẩm tự nhau;
• Các thành phần phía trên nằm trong cột với chỉ số cột tự nhau;
• Để tiện mang lại việc in sản phẩm đi ra thì tao chỉ in đi ra chỉ số những cột tuần tự động theo đuổi những sản phẩm kể từ bên trên xuống.
• Điều khiếu nại để tại vị một quân hậu trúng điểm 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ào là nằm trong phía trên một lối chéo cánh.

Ý tưởng:

• Đầu tiên tao đặt điều quân hậu loại nhất vô những cột bên trên sản phẩm 1 ( với n cơ hội đặt điều ).
• Thử đặt điều quân hậu 2 vào cụ thể từng cột ở sản phẩm 2 sao mang lại không xẩy ra 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 demo đặt điều quân hậu loại tía vô những cột sao mang lại không xẩy ra những quân hậu trước kiểm soát.
• Sau lúc để hoàn thành quân hậu loại tám thì in đi ra một cơ hội đặt điều.

Code C

#include<stdio.h>
#include<math.h>
int a[20];
bool Ok(int x2,int y2){
	//kiểm tra cơ hội đặt điều với thỏa mãn nhu cầu 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 đi ra 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++){
		// demo đặt điều quân hậu vô những cột từ là một cho tới n
		if(Ok(i,j)){
			//nếu cơ hội đặt điều này thỏa mãn nhu cầu thì ghi lại vị trí
			a[i] = j;
                        //nếu đặt điều hoàn thành quân hậu loại n thì xuất đi ra một kết quả
			if(i==n) Xuat(n);
			Try(i+1,n);
		}
	}
}

int main(){
	int n = 8;// ở trên đây bản thân mang lại vấn đề 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 đi ra những sản phẩm ( tôi chỉ copy một không nhiều sản phẩm thôi )

Xem thêm: cho một mạch điện có nguồn điện không đổi khi điện trở ngoài của mạch tăng 2 lần

 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: ngữ văn 10 chân trời sáng tạo tập 2 trang 83

• ( x2, y2) là địa điểm nhưng mà quân hậu tiếp tục đặt điều vô. Như vậy tất cả chúng ta con người ta tiếp tục đặt điều hoàn thành 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 một vừa hai phải mới nhất đặt điều 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ể đặt điều 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 lối 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 đi ra và tự động chứng tỏ nhé !

Bài viết lách bản thân cho tới đó là kết giục. Cám ơn chúng ta tiếp tục theo đuổi dõi !