Untitled

#include<iostream>

using namespace std;

int score[8][8];                                            // cách nhận biết một bài backtrack đó là kích thước ma trận nhỏ, thường là <20

int quanHau[8];                                            // luu cot cua quan hau
int tc, n, maxScore;
void reset(){
	for( int i = 0; i < 8; i++){
		quanHau[i] = 0;
	}
	maxScore = 0;
}

bool check(int row, int col){
	for ( int k = 0; k < row; k++){
		if ( quanHau [k] == col ) return false;              // vị trí này đã đặt quân hậu
		if ( row - k == quanHau[k] - col ) return false;      // kiểm tra theo hàng dọc và chéo
		if ( row - k == col - quanHau[k] ) return false;
	}
	return true;
}

void eightQueen(int index){                                  
	if( index == 8 ){                                 // với một bài backtrack cơ bản, ta luôn phải có điều kiện dừng
		int Score = 0;                                // đồng thời với một số bài tối ưu, ta còn cần điều kiện cắt nhánh
		for( int k = 0; k < 8; k++){
			Score += score[k][quanHau[k]];
		}
	if ( Score > maxScore ) maxScore = Score;
	}
	else{
		for( int j = 0 ; j < 8; j++){
			if( check(index , j) ){                   // chắc chắn 8 quân hậu sẽ đặt ở 8 hàng nên ta sử dụng index vừa là số quân hậu vừa là hàng
				quanHau[index] = j;
				eightQueen(index + 1);                // bình thường một bài backtrack sẽ còn có reset các biến, tuy nhiên bài này chưa cần. ta chạy tất cả trường hợp
			}
		}
	}
}


int main(){
 //freopen("input.txt", "r", stdin);
	int count = 1;
	int T;
	cin >> T;
	for( tc = 1; tc <= T; tc++){
		cout << "Case #" << tc << endl;
		cin >> n;
	for( int sobang = 0; sobang < n; sobang++){
   //reset
		reset();
		for( int i = 0; i < 8; i++){
			for( int j = 0; j < 8; j++){
				cin >> score[i][j];
			}
		}
   //function
   eightQueen(0);
   //output
   cout << maxScore << endl;
	}

	}

 return 0;
}