Design a computer program to search for obstacles, if they exist, for Instant Insanity puzzles of size up to 26 cubes. If an obstacle exists find the smallest one. By obstacle I refer to a subset of cubes which cannot be part of any solution. I.e., any stacking of these cubes entails at least one side that has some color showing up two or more times. For instance if a given puzzle has two monochromatic cubes of the same color then that puzzle has an obstacle of size two. You have free reign over what type of algorithm to implement, and what type of programming language to use. A brute-force algorithm (depth or breadth first search through the tree of possible selections) may work fine for puzzles without solutions of size less than 10 cubes. But getting to size 26 the combinatorial explosion of possibilities may require a more nuanced approach. Note that observing that a particular color only shows up three times is not the same as identifying the smallest obstacle. For this project we are looking for obstacles, not solving puzzles that have solutions. Of course it is possible (although unlikely) that one of the randomly built puzzles below actually has a solution. In that case, simply provide the solution.

The routine I describe will fill in the colors in sequence: (cube1 opposite pair 1 left, cube1 opposite pair 1 right, cube1 opposite pair 2 left, cube1 opposite pair 2 right, cube1 opposite pair 3 left, cube1 opposite pair 3 right, cube2 opposite pair 1 left, cube2 opposite pair 1 right, cube2 opposite pair 2 left, , cube26 opposite pair 3 left, cube26 opposite pair 3 right).

Four puzzles that it must work for are the following:

The color-generating assignment formulae are:

1 + ((floor n??) mod 26), 1 ? n ? 156, for puzzle one,

1 + ((floor n??) mod 26), 1 ? n ? 156, for puzzle two,

1 + floor ??17 mod 26, 1 ? n ? 156, for puzzle three,

1 + floor ??19 mod 26, 1 ? n ? 156, for puzzle four.