CSE 382 Algorithms and Data Structures

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Laboratory 6 - Klondike

Introduction

You and a group of friends have formed a (garage-based) company devoted to developing computer games and are negotiating with a major game publisher to form a business relationship.  The game publisher has all new game development teams develop a portable solitaire game before signing a development contract.  As a demo, you are to develop a version of the card game Klondike

Getting Started

Create a new directory called Klondike for the files belonging to this exercise,  and download Deck.javaLoadCard.javaOverlayPanel.java Overlay.java,  and cards.zip into it.  You may need to find a back side design for your cards. 

Implementing Stacks

Implement your Stack class as a linked list as shown in class.  You can implement the Stack class by extending your implementation of the List<E> interface;  This will allow you to inherit a number of methods.  Remember to invoke the superclass constructor in your constructor if you are overiding any of the inherited parameters or your superclass contains private parameters.  Also,  if you define any constructor for your class,  you must also define a default constructor as well. 

Field Summary
 
Fields inherited from class java.util.AbstractList
modCount
 
Constructor Summary
Stack()
          Creates an empty Stack.
 
Method Summary
 boolean empty()
          Tests if this stack is empty.
 E peek()
          Looks at the object at the top of this stack without removing it from the stack.
 E pop()
          Removes the object at the top of this stack and returns that object as the value of this function.
 E push(E item)
          Pushes an item onto the top of this stack.
 int search(Object o)
          Returns the 1-based position where an object is on this stack.
 


Klondike

The game requires a standard deck of 52 unique cards.  Both suits and ranks are important.  Ace is low only. 

There are four groups of piles.  The cards in all piles are face-up.  These piles are: 

A game begins as in Klondike with twenty eight cards being dealt randomly to the 7 tableau piles.  The first pile receives one card,  the second two cards,  and so forth with the seventh pile receiving seven cards.  The remaining cards are placed in the deck pile. 

The objective of the game is to move all of the cards to the foundation piles. 

Game Rules

Moving a card from one pile to another is viewed as a single,  atomic action.  However,  for the purposes of stating the rules,  it is viewed as taking a card from pile A,  subject to the taking rule for A,  and putting the card onto pile B,  subject to the putting rule for B. 

The game terminates when either all cards have been successfully moved to the foundation piles (a win) or the player quits (a loss).  The score indicates the number of cards which have been moved to a foundation pile. 


Dealing the Cards

For this purpose a prototype deck class is provided for dealing the cards,  although you may have to modify the parameters to the Card constructor.  The deck is "shuffled" by using a pseudo-random number generator to arrange the sequence of cards in the deck.  The Java system provides a pseudo-random number generator class called Random.  A pseudo random number generator object is initizialized when it is constructed by passing a long seed value.  A convenient source for this seed value is the system time in milliseconds.  Your program should accept this seed value as a parameter and use system time when the parameter is omitted. For testing purposes,  you must be able to replicate hands.  Once initialized,  a pseudo-random number generator object will return a pseudo random number between 0 and n-1 each time nextInt(n) is called. 


Generating Random Numbers

Sequences of apparently random numbers are frequently used for computer games and statistical models.  Java provides a class of objects which generate these sequences.  Although apparently random,  the sequences generated by these objects are completely determined by the value of the seed.  Consequently,  behavior driven by one of these pseudorandom number generators can be duplicated simply by passing the same seed when the generator is constructed.  If you want the generator to give a different sequnce each time your program is run,  then you must pass an independent seed value each time the generator is created. 

Constructor Summary
Random()
          Creates a new random number generator.
Random(long seed)
          Creates a new random number generator using a single long seed. 
 
Method Summary
 int nextInt(int n)
          Returns a pseudorandom,  uniformly distributed int value between 0 (inclusive) and the specified value (exclusive),  drawn from this random number generator's sequence.
 


Accessing the System Clock

You have been using the System class for some time now.  Like the Math class,  the System class contains static methods and is not used to construct objects.  The system calss provides access to a variety of system features such as the default inputut/output streams and the system clock. 

Method Summary
 long currentTimeMillis()
          Returns a pseudorandom,  uniformly distributed int value between 0 (inclusive) and the specified value (exclusive),  drawn from this random number generator's sequence.
 


Cards

A set of card images is provided as a zip archive, which should be installed in your project directory and unzipped. This will create a subdirectory named cards/ which contains the card images. Leave that structure intact so that you do not have to turn in card images with your project.

You will not be allowed to submit and use your own deck of cards. If you want cards/images added, you must email them to me and I will add them to everyone's deck.


How To


Requirements


Usage

The game is invoked by:
java  Klondike  [ seed ]
where seed is an optional initial random number seed used to initialize Deck.  When seed is omitted,  use the current system time to initialize the random number generator.  Hint:  this allows us to test your programs using the same card game. 


GUI References


GUI References

Phrases you should now understand:

StackEmptyPeekPopPushSearch

CollaborationYou will complete this project with your lab partner. 
ImplementationYou must implement your system as a Java application.  You may use Jgrasp.  Do not use netbeans or produce a Java applet. 
EnvironmentYour program must execute on the podium computer in our classroom.
Turn inYou must turn in both a report containing complete program sources and an executable electronic version of your program.


Last modified: 2008 FEB 11
bnostran@syr.edu