Click here to Skip to main content
Click here to Skip to main content

matchstick game

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

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

Share

About the Author

kbsbng
Technical Lead Yahoo!
India 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.
Follow on   Twitter   Google+

Comments and Discussions

 
Bugbuffer over load? PinmemberMember 1022081320-Aug-13 6:01 
GeneralRe: buffer over load? Pinmemberkbsbng15-Sep-13 2:00 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin 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
Web01 | 2.8.141216.1 | Last Updated 8 Feb 2007
Article Copyright 2007 by kbsbng
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid