You are a cat. How do you swap?

Question

Number twenty-one cages containing mice, 1, 2, 3, etc., up to 21, and place them in the following order:

1 14 15 17 3 7 13 6 20 2 19 21 5 18 8 11 16 9 12 4 10 

• You start from a cage of your choice, calling that cage one, and count, one, two, three, etc., from left to right. Once you reach the end, you continue counting from the leftmost cage.

• When your count matches with the number on the cage, you have made a catch, and you can eat that mouse ^{_{(you're a cat)}}, and throw away the cage.

• Then start at the cage next to it ^{_{(or the leftmost cage, if you just caught the rightmost cage)}}, call that one, and try to make another catch, and so on.

Let's say you start at 18, calling that cage one, your first catch will be 19.

1 14 15 17 3 7 13 6 20 2 19 21 5 18 8 11 16 9 12 4 10 
                                 ^

Remove 19 and your next catch will be 10.

1 14 15 17 3 7 13 6 20 2    21 5 18 8 11 16 9 12 4 10 
                            ^  

Remove 10 and your next catch is 1.

1 14 15 17 3 7 13 6 20 2    21 5 18 8 11 16 9 12 4  
^

Remove the 1, and you cannot make another catch, even if you count up to 21.

  14 15 17 3 7 13 6 20 2    21 5 18 8 11 16 9 12 4  
  ^

Since you're very hungry, you want to catch all the twenty-one mice. But you'll soon figure out that this is not here possible - no matter which cage you start from.

But here's what you can do:

You can choose two cages and swap them before you begin. Then, if you start at the right place, you might be able to catch all twenty-one mice.

• You may never pass over a catch, i.e., you must always eat the mouse you caught, remove that cage and continue.

• You can always count up to 21, even if fewer cages are left.

What two cages would you swap, and which cage would you start counting from?

---

^{It would be great if you could include the strategy you used to get to the answer, unless you used brute force.}

Answer 1

I employed a brute force strategy, testing every possible swap with every possible starting position. I used the following Python code (Python 2.7):

cages = map(int, '1 14 15 17 3 7 13 6 20 2 19 21 5 18 8 11 16 9 12 4 10'.split())

swaps = ((i,j) for i in xrange(len(cages)) for j in xrange(len(cages)) if i > j)

for (i,j) in swaps:
    for start in xrange(len(cages)):
        l = list(cages)
        l[i], l[j] = l[j], l[i]  # perform the swap
        pos = start
        count = 1

        while (count <= 21) and l:
            if l[pos] == count:
                del l[pos]
                count = 0
            else:
                pos += 1

            if pos >= len(l):
                pos = 0

            count += 1

        if not l:  # if the list is empty, we've found one that works
            print 'swap', cages[i], 'with', cages[j], 'and start at', cages[start]

which produces the following output:

swap 6 with 13 and start at 14
swap 8 with 6 and start at 19
swap 10 with 14 and start at 16