How to prove that only for you-know-what cells there exists an answer?

I brute-forced it (~30 mins as I used 1Gb RAM computer, so I had to calculate 1, 2, 3, ... n steps separately and store results on HDD for further path-tracing between reachable states).

Edited by author 09.09.2008 02:52

It's very easy task if you know the game "Soliter"))

can you tell more about that?

And how does this solitaire help to solve the problem?

yes, i don't see any relation with the solitarie. Although i've played many times (in the past)

Well, try coloring the cells of the field in numbers 3,5,6 so that in each row they repeat: 3,5,6,3,5,6,... and the top-left to bottom-right diagonals are always "one-color". Then play with possible moves and XORs of the values. Then change the direction of one-color diagonals and repeat all the reasoning. This will certainly help you.

This is solitaire he meant:
http://en.wikipedia.org/wiki/Peg_solitaire

Oh, you showed us the solution.