13,194,662 members (87,171 online)
alternative version

#### Stats

30K views
12 bookmarked
Posted 7 Feb 2007

# matchstick game

, 7 Feb 2007
 Rate this:
A very simple game

## Introduction

This is a project for a very simple game.

## The rules

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.

A list of licenses authors might use can be found here

## Share

I've studied info. sc. engg. from Sir MVIT, Bangalore.

I'm interested in programming.

Some of my technical blogs:

http://perl-blog.kbsbng.com/
http://java-blog.kbsbng.com/

I also enjoy writing some webpages such as http://sites.google.com/site/plantencyclopedia/

More about me at http://www.kbsbng.com and http://blog.kbsbng.com.

## You may also be interested in...

 First Prev Next
 buffer over load? Member 1022081320-Aug-13 5:01 Member 10220813 20-Aug-13 5:01
 Re: buffer over load? kbsbng15-Sep-13 1:00 kbsbng 15-Sep-13 1:00
 Last Visit: 31-Dec-99 18:00     Last Update: 19-Oct-17 7:28 Refresh 1