Algorithm to find solution to puzzle

It is a graph theory maximum flow problem.

Suppose that every circle is a node in the graph. Additionally introduce 2 special nodes: TOP and BOTTOM. Connect circles with these nodes if they intersect with TOP/BOTTOM side. Connect nodes corresponding to circles with each other if the circles intersect.

Now you need to find a minimum cut in this graph, having TOP as source and BOTTOM as sink or vice versa. You can use Max-flow_min-cut_theorem to solve it. What it states is that Minimum-cut problem is equivallent to Max-flow problem. You can find details on how to solve Max-Flow problem on TopCoder.

As we can go through each node only once, we should convert the nodes into a directed edge of capacity one with in-node and out-node for each circle. The max-flow algorithm will solve the problem on the resulting graph and take into account the fact that we are removing circles rather than connections between circles. It is always a better decision for this problem to remove a node in a graph rather than edge, as we can always remove any edge by removing a node. Removing a node additionally can result in removing more than one edge.

By the way, a similar problem can be found on Uva Online Judge. It a good idea to try solve this task on the judge, then you will be sure that your solution is correct.

In trying to visualize what Leonid wrote, I made the following diagram.

For a graph translation, something like this might work.

Make a wall(the blue lines) between two circles if they overlap. Don't forget to add in the top and bottom border as well. This creates a couple of regions. These will be all the nodes of the graph.

Next we have to find the edges, the cost of going from one node to another. Take two neighbour regions (sharing a wall.) Then by brute force, or what ever clever method you come up with, determine the cost of moving from this region to the other. If you remove a circle, that means, you remove all the walls that go to that circle. If this makes the two regions into one region, the cost of the edge is 1. If you need to remove two circles(all the walls they have) to combine the two regions, the cost is 2. Etc.

Some of the edges(green) are drawn. We have to go from the start region, to the end region. You now got a everyday weighted graph.

I think this can be improved a lot, but I leave that as an exercise =)

In this case minimum is 3.

Warning, picture is drawn by hand, I did forget a few walls, edges and regions. For illustration purposes only.