CS 1027 Computer Science Fundamentals II - Assignment 3: Solitaire
CS 1027 Computer Science Fundamentals II Assignment 3
Learning Outcomes
In this assignment, you will get practice with:
- Stacks
- Lists
- Interfaces
- Generics
- Advanced Algorithms
- Advanced Debugging
Introduction
A popular single-player card game is solitaire. In the game, there are many stacks of cards: the regular stacks (sometimes referred to as the tableau), and four initially empty foundation stacks that are later built up out of ascending consecutive cards of each suit. To win a game of solitaire, all cards must be moved to these foundation stacks. This assignment will revolve around a simplified solitaire that uses Domino tiles instead of cards. A set of Domino tiles consists of 28 rectangular game tiles (see Fig 1.) Each tile has a combination of two numbers which is unique to that tile. In a normal set, the highest number is six and the lowest is zero or simply blank.
Fig 1. A complete set of Dominoes (with 6 as the largest number). The tiles containing a 3 as the highest number are highlighted—they will be considered an example of a set that starts with a double [3:3] and goes down through [3:2] and [3:1] to [3: ].
In our simplified solitaire, called DomSolitaire, there will be an equal number of regular and foundation stacks with the exact number being determined by the largest number used. For instance, in Fig 2., there are four stacks of each type with the largest tile number used being 3. Each of the foundation stacks starts empty and will then get filled with tiles descending from doubles containing only tiles with that particular doubled number as its highest number.
Fig 2. A DomSolitaire with 3 as it’s biggest number. Notice that there are 4 empty foundations stacks and 4 regular stacks with sizes 1, 2, 3, and 4. If 4 was the biggest number used there would be 15 total tiles and 5 of each type of stack.
There are three types of moves: a move from a regular stack to a foundation stack, a move from a regular stack to a non-empty regular stack, and a move from a regular stack to an empty regular stack. Each of these moves is only permissible under certain conditions. A tile, T, on regular stack can move to a foundation stack either if T is a double tile which means that it can move to empty foundation or if T’s low number (e.g. [3:1] ‘s low number is 1) is one number below the low number of the top of the foundation corresponding to T’s high number (e.g [3:1] would have go to the foundation 3 and the [3:2] tile would have to be at the top of F3 for it to be able to move there). The next types of move only use the regular stack. A tile, T1, on top of a regular stack can move on to a non-empty stack with a tile, T2, on top if T1 and T2 share a number in common and T1’s other number is one up from that T2’s other number. The last type of move occurs if there is an empty regular stack. Any tile T, from that top of a regular stack with a blank can be moved to the empty regular stack. Fig. 3 shows some examples of permissible.
A B Fig 3. (A)Three types of permissible moves: A tile from a regular stack to a foundation e.g. move S2 to F3 is permissible since the [3:2] tile is one down from the [3:3] tile (also [3:2]’s high number is a 3 it belongs in the F3 stack); S2 to S3 is permissible since [3:2] shares a 3 with the S3’s [3:1] and it is one up; and S1 to S0 is permissible since S0 is empty and S1’s top has a blank.(B) Shows the result of the first and third moves.
The purpose of these moves is to completely empty the regular stacks having moved all the tiles into the foundation stacks: see Fig 4.
Fig 4. The final winning state of a game. F0 has 1 tile, F1 and 2 tiles ([1:1], [1: ]). F2 has 3 tiles ([2:2], [2:1], [2: ]), and F3 has 4 tiles ([3:3], [3:2], [3:1], [3: ]) whereas all the regular stacks S1-S4 are empty. To better illustrate the moves and the game, a complete game using is shown in Fig. 5. In this game, there are only 6 tiles comprising of tiles that have 2 as there largest number. The game take 9 moves: 6 moves from regular stacks to foundation (AEDFGHI), 2 moves from regular stacks to non-empty regular stacks(CE), and 1 move from a regular stack to an empty regular stack(B).
In this assignment, you are implementing a DomSolitaire game solution finder. Your code will attempt to find a sequence of moves that takes the initial setup with empty foundations and filled regular stacks to one with filled foundations and empty regular stack. There are two dimensions that determine the initial setup. One dimension is the number of Domino tiles used 3, 6, 10, 15, 21, and 28 which correspond to the highest number used on the tiles (1,2,3,4,5, and 6). For example, when 3 is the highest number there are 10 tiles as seen in Fig. 2. The more tiles tend to make the game more difficult. The particular set of tiles used in each game is determined at the start (see Domino.getSet(n)—for example getSet(3) was used for Fig. 2-4 and getSet(2) for Fig. 5) Another dimension is the initial ordering of the tiles in the regular stacks. The initial ordering is also determined at the start (See Domino.shuffle(seed) for details). Although many setups have solutions (are winnable), some setups will have no solutions.
Provided files
- ListADT.java
- UnorderedListADT.java
- UnorderedList.java
- StackADT.java
- EmptyCollecionException.java
- LinearNode.java
- StackArray.java
- Named.java ** interface for debugging
- StackLL.java ** note: implements Named
- Domino.java ** note: see above
- DomSolTests.java
The DomSolTests.java file will help to check if your java classes are implemented correctly. A similar file will be incorporated into Gradescope's auto-grader. Passing all the tests within DomSolTests.java does not necessarily mean that your code is correct.
Classes to Implement
For this assignment, you must implement two Java classes: Move and DomSolitaire. Follow the guidelines for each one below. In of these classes, you may implement more private (helper) methods and it is encouraged for readability and reducing duplication of code. However, you may not implement more public methods except public static void main(String[] args) for testing purposes (this is allowed and encouraged). You may not add instance variables other than the ones specified in these instructions nor change the variable types or accessibility (i.e. making a variable public when it should be private). Penalties will be applied if you implement additional instance variables or change the variable types or modifiers from what is described here.
Move.java
Move is a simple class that holds information about a particular move in a sequence of moves. It will also hold a name to potentially be useful in debugging. The class must have these private instance variables:
private StackADT<Domino> from
private StackADT<Domino> to
private boolean completed
private String nameThe class must have the following public methods:
public Move(StackADT<Domino> from, StackADT<Domino> to) [constructor]o calls the other constructor with name “m” ▪ hint: use this(from, to, "m");
public Move(StackADT<Domino> from, StackADT<Domino> to, String name)
[constructor]o sets the all the corresponding instance variables and sets completed to false
public void doIt()o pop an element in from and push it on to o sets completed to true
public void undoIt()o pop an element in to and pushes it on from o sets completed to false
public boolean isCompleted()o getter for completed
public boolean equals(Object obj)o returns false if obj is not an instance of Move o returns true if this from and to are the same as obj’s from and to (in terms of memory location)
public String toString()o constructs a string to represent this objects instance variable ▪ {name}{from}->{to}{? or !} • {name} is the instance name • {from} either the from’s toString() unless from implements Named in which case {from} is from’s getName() • {to} either the to’s toString() unless from implements Named in which case {to} is to’s getName() • {? or !} is ? if competed is false or ! if completed is true ▪ Examples: • mStack |top>[3:1] <|->S3? o “m” is the name of this move o “Stack |top>[3:1]” is the toString of from which must b a StackADT which is not a Named “S3” is the name of to (which is a Named StackADT) “?” means that this move is not completed testS0->F3!
“test” is the name of this move “S0” is the name of from (which is a Named StackADT) “F3” is the name of to (which is a Named StackADT) “!” means that this move is completed
DomSolitaire.java
This class is used to represent game stack and find the solution sequences. Since, the nature of this class may cause problems while developing the code, there may be a need to follow the progression of how things are changing. To help see what is going on you can add lines that look like if (debug) System.out.println(“method 1: current state “+ this); that can be activated by setting debug to true. The class must have these private instance variables:
private StackADT<Domino>[] foundation
private StackADT<Domino>[] stack
private String name
private boolean debugThe class must have the following public methods:
public DomSolitaire(int highestNum, int seed, String name) [constructor]
o sets up arrays of StackADT for both stack and foundation and fills them with
empty StackLL
