12,512,130 members (54,199 online)
Add your own
alternative version

26.3K views
447 downloads
12 bookmarked
Posted

# matchstick game

, 7 Feb 2007
 Rate this:
Please Sign up or sign in to vote.
A very simple game

## 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.

## License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

## About the Author

 Technical Lead Yahoo! India
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...

 Pro Pro

## Comments and Discussions

 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: 1-Oct-16 2:26 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160929.1 | Last Updated 8 Feb 2007
Article Copyright 2007 by kbsbng
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid