Some time ago, Robin Landsbert sent me a suggestion for a Challenge based on a game he called Nim. In Robin’s version of the game, matchsticks were arranged in rows forming a triangle, one matchstick in the top row, two in the next, three in the next, etc. Two players take turns removing one or more matchsticks from any single row of the board. The object is to make your opponent take the last matchstick.

A little research suggests that this version of the game might not be very difficult. So, in the tradition of the Challenge, we will add a few twists that might make the game (and the Challenge) more interesting. First, we will arrange our matchsticks in a square grid instead of a triangular one, and allow players to remove matchsticks from either a single row or a single column on a given turn. Second, we will not put a matchstick in every position in the grid, leaving a small number of positions empty, perhaps on the order of 10%. Third, we will restrict a player’s moves to removing matchsticks with no intervening holes. That is, a player can remove the n+1 matchsticks in row r located in columns c through c+n only if a matchstick is present in each of those locations. And finally, we will play two versions of the game, one where the player taking the last matchstick loses the game, and one where the player taking the last one wins the game.

The prototype for the code you should write is:

The Challenge will be scored as a round robin tournament, or another fair scheduling mechanism. Each player will play first and play second against each scheduled opponent an equal number of times for each test case. Each player will play to win by taking the last matchstick, and play to win by making the opponent take the last matchstick, an equal number of times against each scheduled opponent for each test case. A player’s score will be dimension^2 points for each win, minus a penalty of 10 points per millisecond of execution time. You can earn a bonus of up to 25% of your score based on a subjective evaluation of the clarity of your code and commentary.

This will be a native PowerPC Carbon Challenge, using the Metrowerks CodeWarrior Pro 7.0 development environment. Please be certain that your code is carbonized, as I may evaluate this Challenge using Mac OS X. Unfortunately, this Challenge cannot accommodate alternative development environments, because pairs of solutions need to compete against one another in a single executable.

Test code for this Challenge is available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".