問題D Hexagram

合同練習会

解法

DFS(深さ優先探索)です。12個の数字の合計が3の倍数にならないときや直線4つの数字が3の倍数にならないときに枝刈りできます。数字が全部異なるため回転・対称のものは全部で12通りあるので、重複して数え上げて最後に12で割るとよいです。

コード(C++)

#include <iostream>
using namespace std;

int a[12], b[12], sum, line;
bool memo[12];

int dfs(int pos = 0){
	// 合計が 3 の倍数でないときは解は 0 
	if( sum % 3 != 0 ) return 0;
	
	if( pos == 12 ){
		if( line != a[1] + a[8] + a[9] + a[11] ) return 0;
		if( line != a[5] + a[7] + a[10] + a[11] ) return 0;
		return 1;
	}
	
	if( pos == 4 ){
		line = a[0] + a[1] + a[2] + a[3];
		if( sum / 3 != line ) return 0;
	}else if( pos == 7 ){
		if( line != a[3] + a[4] + a[5] + a[6] ) return 0;
	}else if( pos == 9 ){
		if( line != a[0] + a[6] + a[7] + a[8] ) return 0;
	}else if( pos == 11 ){
		if( line != a[2] + a[4] + a[9] + a[10] ) return 0;
	}
	
	int res = 0;
	for(int i = 0 ; i < 12 ; i++ ){
		if( memo[i] ) continue;
		
		a[pos] = b[i];
		memo[i] = true;
		res += dfs(pos + 1);
		memo[i] = false;
	}
	return res;
}

int main(){
	while( cin >> b[0], b[0] ){
		sum = b[0];
		for(int i = 1 ; i < 12 ; i++ ){
			cin >> b[i];
			sum += b[i];
		}
		
		fill(memo, memo + 12, false);
		cout << dfs() / 12 << endl;
	}
}