Find a minimal set of Pythagorean triples that cannot be coloured with three colours such that all triples have all three colours; see http://math.stackexchange.com/questions/1816353.

Question1816353.java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

public class Question1816353 {
	final static int max = 111;
	final static Random random = new Random ();
	static int [] colours = new int [max + 1];

	static List<int []> triples;
	
	public static void main (String [] args) {
		triples = new ArrayList<int[]> ();
		List<int []> allTriples = new ArrayList<int []> ();
		
		for (int a = 1;a <= max;a++)
			for (int b = a + 1;b <= max;b++)
				for (int c = b + 1;c <= max;c++)
					if (a * a + b * b == c * c)
						allTriples.add (new int [] {a,b,c});
		
		List<int []> requiredTriples = new ArrayList<int []> ();
		List<int []> optionalTriples = new ArrayList<int []> ();
		
		for (int i = 0;i < allTriples.size ();i++) {
			triples = new ArrayList<int []> (allTriples);
			triples.remove (i);
			(check () ? requiredTriples : optionalTriples).add (allTriples.get (i));
		}
		
		int [] types = new int [optionalTriples.size ()];
		Arrays.fill (types,1);
		for (int n = 0;n <= 8;n++)
			new Multiset (types).traverseSubsets (n,new MultisetHandler () {
				public void handle (int [] multiset,BigInteger multiplicity) {
					triples = new ArrayList<int []> (requiredTriples);
					for (int i = 0;i < multiset.length;i++)
						if (multiset [i] == 1)
							triples.add (optionalTriples.get (i));
					if (!check ()) {
						System.out.println ("minimal configuration (" + triples.size () + "):");
						for (int [] triple : triples)
							System.out.println ("(" + triple [0] + "," + triple [1] + "," + triple [2] + ")");
						System.out.println ();
					}
				}
			});

		outer:
		for (;;) {
			triples = new ArrayList<int []> (allTriples);
			int nfailures = 0;
			inner:
			for (;;) {
				int [] removed = triples.remove (random.nextInt (triples.size ()));
				if (check ()) {
					triples.add (0,removed);
					if (++nfailures > 20) {
						List<int []> left = new ArrayList<int []> (triples);
						for (int i = 0;i < left.size ();i++) {
							triples = new ArrayList<int []> (left);
							triples.remove (i);
							if (!check ()) {
								nfailures = 0;
								continue inner;
							}
						}
						int [] [] a = left.toArray (new int [left.size ()] []);
						Arrays.sort (a,new Comparator<int []>() {
							public int compare (int [] o1,int [] o2) {
								for (int i = 2;i >= 0;i--) {
									int diff = o1 [i] - o2 [i];
									if (diff != 0)
										return diff;
								}
								return 0;
							}
						});
						System.out.println ("minimal configuration (" + a.length + "):");
						for (int [] triple : a)
							System.out.println ("(" + triple [0] + "," + triple [1] + "," + triple [2] + ")");
						System.out.println ();
						continue outer;
					}
				}
				else
					nfailures = 0;
			}
		}
	}
	
	static int [] [] ps = {
		{1,2,3},
		{1,3,2},
		{2,1,3},
		{2,3,1},
		{3,1,2},
		{3,2,1}
	};
	
	static boolean check () {
		return recurse (0);
	}
	
	static boolean recurse (int i) {
		if (i == triples.size ())
			return true;
		
		int [] triple = triples.get (i);
		
		int c1 = colours [triple [0]];
		int c2 = colours [triple [1]];
		int c3 = colours [triple [2]];
		
		outer:
		for (int [] p : ps) {
			for (int j = 0;j < 3;j++)
				if (colours [triple [j]] != 0 && colours [triple [j]] != p [j])
					continue outer;
			for (int j = 0;j < 3;j++)
				colours [triple [j]] = p [j];
			boolean success = recurse (i + 1);
			colours [triple [0]] = c1;
			colours [triple [1]] = c2;
			colours [triple [2]] = c3;
			if (success)
				return true;
		}
		
		return false;
	}
}