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ã:
#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();
}