MNS.java

/*
 * Single Round Match 148 Round 1 - Division I, Level Two 
 * http://www.topcoder.com/stat?c=problem_statement&pm=1744&rd=4545
 */
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class MNS {

	private int combos = 0;
	private Set<String> note = new HashSet<String>(30);
	
	private boolean checkMagick(int[] x) {
		int n = x[0] + x[1] + x[2];
		
		for (int i = 3; i < 9; i += 3) {
			if (n != (x[i] + x[i+1] + x[i+2])) return false;
		}
		for (int i = 0; i < 3; i++) {
			if (n != (x[i] + x[i+3] + x[i+6])) return false;
		}
		return true;
	}
	
	private static int[] toArray(List<Integer> list) {
		int[] a = new int[list.size()];
		for (int i = 0; i < a.length; i++) {
			a[i] = list.get(i);
		}
		return a;
	}
	
	private void solve(List<Integer> numbers, List<Integer> square) {
		if (numbers.isEmpty()) {
			assert square.size() == 9;
			final String key = square.toString();
			//System.out.println(square);
			if (!note.contains(key) && checkMagick(toArray(square))) {
				note.add(key);
				combos++;
			}
		} else {
			for (int i = 0; i < numbers.size(); i++) {
				List<Integer> numbers2 = new ArrayList<Integer>(numbers);
				List<Integer> square2 = new ArrayList<Integer>(square);
				square2.add(numbers2.get(i));
				numbers2.remove(i);
				solve(numbers2, square2);
			}
		}
	}
	
	public int combos(int[] numbers) {
		List<Integer> numbersList = new ArrayList<Integer>(numbers.length); 
		for (int i = 0; i < numbers.length; i++) numbersList.add(numbers[i]);
		solve(numbersList, new ArrayList<Integer>(0));
		return combos;
	}

}