Thanks to my friend Marissa, I have been mucking around with a game called Chat Noir for the past few days.
A quick run-down. We have an 11x11 grid, and the cat starts in the middle. You move first by blacking out one of the hexes, and the cat goes second (and so on). The cat cannot move onto black squares. Some squares start as black already. The goal is to prevent the cat from "escaping" the grid or, equivalently, getting to an edge hex. The cat always moves towards the closest piece of edge.
Is it always possible to capture the cat? My initial guess was "no", and then it turned into a "maybe". I am still not 100% sure.
I have two methods I am going to try now: I am going to try to solve the empty case (with no black squares at the beginning) and try to capture the cat. Either by finding the optimal strategy, or by having a computer prove it is possible. The beauty of this is that the cat's strategy is always known, so it makes the problem simpler.
However, in the general case, it is not necessarily true that a solution in the empty case will extend to the general case.
I am in the middle of coding up some simple strategies and enumerations of the game, and will report on my results in a few days. In that, it may take several days for some of them to run.
I don’t see what you mean that a solution to the empty case won’t extend. You can just pretend that the initial black squares are “free moves” where the cat doesn’t get a move. I think it’s obvious that if the empty case works, then free moves can’t possibly hurt.
That said, I suspect two things: a) the cat’s greedy strategy is not optimal (ie, you could have a smarter cat) and b) the general case isn’t solvable. I’m interested to see what you turn up.
If the problem is solvable for the square of 2n-1, it follows that it is also solvable for the square of 2n+1. I guess this is quite obvious with you. It means, however, that you only have to consider an infinite area. Put the cat at any starting point and see how far the cat could walk before you fence her in. This seems to me as a far easier way to get a quick result.
The only way I can figure it out is if you have a way of fooling the cat to move the wrong way and the turn back. I’m not sure I understand the cat strategy, cause as I see it, the cat will allways escape, nometter how far the edge.