USACO - The Clocks

Let's think about the problem statement more, what do we have?

We have a set of 9 clocks that we want them all to show 12 o'clock and we have a set of 9 different keys that we can push to change the time of a subset of clocks. For example key #1 can change the time of clocks ABDE, so if you press key #1 then clocks labeled A, B, D and E will show a new time which is 3 hours plus their previous time.

If you don't observe any facts in the problem statement, This problem can be modeled as a graph which you want to go from a 'start' node to a 'destination' node, and can be solved using BFS. How many nodes do we have? By 'node' I mean a set of 9 clocks each of which shows a specific time (12-3-6-9), so each clock has 4 situations and the number of nodes is equal to 4*4*...*4 = 4^9 = 262144 that's not too many for a graph to run BFS on it. So you run BFS from the start node and try to reach node(12,12,12 --- 12,12,12 --- 12,12,12) How many neighbors does a node have? Each node has 9 other neighbors through 9 different keys.

But as I told if you observe a simple fact you can see that each key has 4 different situations, so instead of running BFS to find the solution you can use recursion to decide how many times you want to push key #i, and check if you can change all the clocks to show 12 o'clock. I myself think the second solution is more cute than the first solution, there is also another solution which takes O(1) and needs much more insight about the problem.