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

Bài toán xếp xếp hậu là Việc đặ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ày rất 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 sở hữu để di chuyển theo quy tắc cờ vua.

Lời giải của Việc 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ày đứ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 rất 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 mô tả một điều 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 nhập mò mẫm điều giải mang lại Việc này.

Giải bài toán xếp hậu bởi vì đệ quy nhập C/C++

• Để tiện trình diễn tao người sử dụng thay đổi i nhằm khắc ghi những sản phẩm 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 ngược quý phái nên ( 1 cho tới n );
• Các thành phần phía trên đứng thảng hàng sở hữu chỉ số sản phẩm bởi vì nhau;
• Các thành phần phía trên nằm trong cột sở hữu chỉ số cột bởi vì 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 gót 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 vị trí 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 sở hữu 2 quân hậu này 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 nhập những cột bên trên sản phẩm 1 ( sở hữu 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 biến thành 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 nhập những cột sao mang lại không biến thành những quân hậu trước kiểm soát.
• Sau lúc đặt 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 sở hữu 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 nhập những cột từ 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ì đánh dấu 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;// ở phía trên bản thân mang lại 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 đ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: tác giả tác phẩm tôi đi học

 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 nhập lịch trình trên

Xem thêm: rận mu sinh ra từ đâu

• ( x2, y2) là địa điểm nhưng mà quân hậu tiếp tục đặt điều nhập. Như vậy tất cả chúng ta con người ta đang đượ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á thứu tự những quân hậu ở trước với quân hậu vừa vặn mới mẻ đặt điều nhập.
• 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 nhập ( 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ó thể vẽ hình đi ra và tự động minh chứng nhé !

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