BÀI TOÁN ĐẶT HẬU
Mô tả bài toán: liệt kê tất cả phương án đặt n quân hậu trên bàn cờ vua cấp sao cho n quân hậu không được phép ăn nhau.
Ví dụ: cho bàn cờ vua cấp . Dưới đây là 1 phương án đặt quân hậu:
Mô tả bài toán: liệt kê tất cả phương án đặt n quân hậu trên bàn cờ vua cấp sao cho n quân hậu không được phép ăn nhau.
Ví dụ: cho bàn cờ vua cấp . Dưới đây là 1 phương án đặt quân hậu:
Code:
#include "conio.h"
#include "iostream.h"
#define max 20
char a[max]; //danh dau cot
char b[2*max-1]; //danh dau huong Dong-Bac
char c[2*max-1]; //danh dau huong Tay-Bac
int Luu[max]; //luu ket qua tim duoc
int n;
/*Khoi tao cac bien*/
void Init(){
cout<<"Nhap n = ";
cin>>n;
//tat ca cac cot chua duoc chon
for(int i = 0; i<n; i++)
a[i] = 0;
//tat ca cac huong chua duoc chon
for( i = 0; i<2*n-1; i++) {
b[i] = 0;
c[i] = 0;
}
}
/*Xuat ket qua ra man hinh*/
void Out(){
cout<<endl;
for(int i = 0; i<n; i++)
cout<<"("<<i+1<<","<<Luu[i]+1<<") ";
}
/*Chinh hop khong lap chap k*/
void Try(int i) {
if(i==n)
Out();
else {
for(int j = 0; j<n; j++)
if(a[j] == 0 && b[i+j] == 0 && c[i-j+n] == 0) {
a[j] = 1; //danh dau cot j
b[i+j] = 1; //danh dau huong Dong-Bac thu i+j
c[i-j+n] = 1; //danh dau huong tay-Bac thu j-i+n
Luu[i] = j; //luu vi tri dat hau (i,j)
Try(i+1); //tim vi tri dat hau tiep theo
a[j] = 0; //phuc hoi cot j
b[i+j] = 0; //phuc hoi huong Dong-Bac thu i+j
c[i-j+n] = 0; //phuc hoi huong tay-Bac thu j-i+n
}
}
}
/*Chuong trinh chinh*/
void main(){
clrscr();
Init();
cout<<"Dat Hau";
Try(0);
getch();
}