<p>In the game of Nim, we have multiple "stacks" of "coins." Two players take turns taking as many coins as they please (at least one, though) from a single stack. The object is to take the last coin. It turns out that the (time-efficient) solution to a particular configuration deals with the parity of the binary representation of the number of coins in each stack. </p>
<p>I chewed on this problem for a while, and came up with my own problem: consider an m x n lattice of coins. Two players take turns taking as many coins as they please from a single row OR column. How can one determine whether an arbitrary board is a "winning" board or a "losing" board? (The empty board is considered a losing board.) </p>
<p>I've "solved" the problem in Prolog using recursive descent, but that's a ridiculous way to solve a board (solving a 15 x 15 board would take until the Second Coming). Dynamic programming promises a faster solution, but it uses an excessive amount of memory: 2 ^ (m x n) bits.</p>