Pawn battle

[Shotaro Yamazoe]

@admin
Thank you for your reply. I understand :)

[David McCloskey]

To those who were able to get high scores, what was your approach. The only thing I could come up with was to say that if you are adjacent to your opponents pawns and it's your turn, then you lose. Then by recursing, you could see if there was a winning set of moves from the current position. I had correctness, but iterating over all possible paths was no good in some corner cases which made my algorithm take too long for more than 5 columns.

[hellocopter]

Without trying to give away the solution, I'll suggest that you take a look at combinatorial game theory. With a bit of poking around, you'll find everything you need to solve this efficiently (plus a lot of other fun things along the way).

Related resources:

Wikipedia: http://en.wikipedia.org/wiki/Combinatorial_game_theory
TopCoder article on CGT: http://community.topcoder.com/tc?module ... rithmGames
Sample puzzle on SPOJ: http://www.spoj.pl/problems/CLK/

[David McCloskey]

Wikipedia: http://en.wikipedia.org/wiki/Combinatorial_game_theory
TopCoder article on CGT: http://community.topcoder.com/tc?module ... rithmGames
Sample puzzle on SPOJ: http://www.spoj.pl/problems/CLK/

Thanks for these. I wish description said "combinatorial game theory" instead of "game theory" which appears to be something completely different from what was actually required for the puzzle.

[davidb]

Thanks for these. I wish description said "combinatorial game theory" instead of "game theory" which appears to be something completely different from what was actually required for the puzzle.

Actually game theory is the right term, combinatorial game theory is a subset of it.
http://en.wikipedia.org/wiki/Game_theor ... rial_games

Giving the most specific term would be giving away the solution, that's why the terms used are more general.