matchstick game

• Download demo - 73.4 Kb
• Download source code - 0.5 Kb

Introduction

This is a project for a very simple game.

The rules

1. We start with 21 matchsticks.
2. The player and the computer take turn in picking up the matchsticks.
3. In each turn, up to 4 matchsticks can be picked.
4. In each turn, at least one matchstick has to be picked.
5. Only an integral number of matchsticks can be picked.
6. The player who ends up picking the last matchstick loses the game.

The solution

There are two solutions I would like to discuss:

1. Using the recursive function int win(int n):

   int win(int n)
   {
          int i;
          if(n==6) return 0;
          if(n<=5) return n-1;
          for(i=1;i<=4;i++)
                if(win(n-i-1)&&win(n-i-2)&&win(n-i-3)&&win(n-i-4))
                       return i;
   }

2. A very simple solution: Say the user picks x matchsticks in his/her turn. Let the computer pick 5-x matchsticks in its turn.

Discussing the solutions

The first solution is the one the used in the codes provided in the download link. It uses a recursive function and is hence less efficient in terms of time. However, it is the solution we can think of for any game of this sort. On the other hand, the second solution is very simple. This shows that how certain problems can have damn simple solutions. But, finding these simple solutions is not that easy. In fact, I came to know of the second solution only after I used the first one. However, for any game of this sort, we cannot expect a solution resembling the second one.

The first solution uses following ideas:

1. The computer can win by choosing r-1 matchsticks, where r is remaining number of matchsticks when it is the computer's turn, if r<=5.
2. The computer may lose if it is left with 6 matchsticks in its turn. Because say the computer now chooses x matchsticks, then the user may win choosing 5-x matchsticks.
3. When it is the computer's turn, if i is a number 1=<i<=4 such that whatever be the number of matchsticks the user picks after the user plays his/her future turns, the computer can win by choosing a certain number in each of its turn, then the computer can proceed by picking i matchsticks. To find out i, we use recursive calls to win function. Say win(n-i-1),win(n-i-2), win(n-i-3) and win(n-i-4), where n is remaining number of matchsticks, are all greater than 0, then the computer can pick i matchsticks, because there is a way the computer can win whatever be the number of matchsticks the user picks in his/her future turns.

A point to remember

Here we assume that a number such as i does exist. And this assumption is true and that's why we can ensure that the computer wins in each game. If this is not true, we have to modify the procedure to find the best possible number of matchsticks that may be removed.

Summary

1. We can know how recursive functions can be used.
2. We may see how very simple solutions exist to some problems.