Objective

This homework will give you practice with one-dimensional arrays and with the MVC (Model-View-Controller) model.

Overview

For this homework you will implement a puzzle game.  The objective of the game is to order a random set of numbers so that an increasing sequence of values is generated.  Your task is to implement the engine that controls the game, that is, the code that modifies the state of the game based on user input and detects when the user has ordered the set of numbers.  This homework will be graded as follows:

• 75% - Implementation
• 15% - Pseudocode
• 10% - Time log

In this homework we will use the terms "cell" and "puzzle piece" to refer to the same entity.

Specifications

You will write a program that lets a user play a simple one-dimensional puzzle (see figures below).  The puzzle consists of a sequence of cells, each with a string of text.  The user can move the cells according to the following rules:

1. Clicking on any non-blank cell will shift that cell and all cells between that cell and the blank cell towards the blank cell.  This will result in the cell you clicked on becoming blank.
2. Clicking on a blank cell will swap the two cells on either side of the blank cell.
3. Clicking on a blank cell at the left end of the puzzle will swap the last cell with the second one.
4. Clicking on a blank cell at the right end of the puzzle will swap the second to last cell with the first one.

The player's goal is to arrange the text in to it's natural order (i.e., in increasing order - "0, 1, 2, 3, 4, ...").  The puzzle should start with a sequence of randomly generated unique numbers out of [0, n-2], assuming n cells.  When the game starts it will prompt the user for the number of cells to use for that particular run.  You can assume that the number of cells will be greater or equal than three.

Code Distribution Classes

• Puzzle - This class represents the game.  If you want to play the game you will need to create an instance of this class.  The class prompts the user for the number of cells to use, and then create instances of support classes needed for the game.  This class has a main method which starts the game for you.  You must not modify this class.
• PuzzleGUI - This class implements the graphical user interface.   You must not modify this class.
• PuzzleEngineInt - This interface defines what we call the engine of the puzzle.  Any class implementing this interface will be considered a puzzle engine, that is, a class that controls the state of the game.  The class will implement methods that generate a random puzzle, change the state of the puzzle based on a cell selection and detects when the puzzle is in a state representing an ordered sequence.  You must not modify this interface. 
• PuzzleEngine - This class implements the PuzzeEngineInt interface.  This is the class you must implement for this homework.  It has as field an array of String objects named "cells". More information about what is expected from each method can be found in the API documentation.  
• Tester - A class that illustrates how we can play the puzzle game without the GUI.  Its purpose is to reinforce the advantages of the MVC model.  You don't need to use this class for the homework but you should understand it.

Your Assignment

You must implement the following three methods defined in PuzzleEngine.java. Note that the supplied  getContents() method is already complete.  For each method (except getContents()) we have define code so that you can create an instance of the Puzzle class and can see how the interface and the PuzzleEngine class are related.  You should try to execute the game with the PuzzleEngine class we have provided in order for you to understand the mechanics of the system. Proceed to implement the PuzzleEngine class once you have a clear understanding of the interaction among puzzle game classes.

Methods to Implement

public void generatePuzzle(int numCells);

generatePuzzle() creates the initial "model" of the puzzle.  Given the number of cells the puzzle should have, it must initialize the "cells" instance variable to an array of "numCells" strings where one of the strings is blank ("") and the others are unique random numbers in the range [0, numCells-2].  You should use the code "(int)(Math.random() * maxValue)" to generate a random number in the range [0, maxValue-1].  You must think about how to generate the sequence of random numbers so that none are repeated.  It could be the case (specially for a small number of cells) that the randomly generated sequence of number is already sorted.  For this homework you can ignore this scenario, however you should think how you would manage such situation.

You will also need to convert the integers you generate into a Strings to be stored as element of the "cells" array.  You can convert an integer into a String by using the Integer.toString() method which takes an integer as a parameter and returns a string.  An example is:

String s;
int i = 5;
s = Integer.toString(5);

public void cellSelected(int cellIndex);

cellSelected() - Completes the processing associated with selecting the puzzle piece (cell) with index value "cellIndex".  The cells array is modified according to the game rules.

public boolean isSolutionCorrect();

isSolutionCorrect() determines if the current puzzle is in a correct solution state and returns true if the puzzle is correct.  The puzzle will be considered solved (i.e., solution is correct) if the state of the puzzle represents an ordered sequence of values, regardless of where the blank cell is located.  For example, the following represent correct solutions (the 'E' stands for the empty cell):

E   0  1  2  3

0  1  2  E  3

0  1  2  3  E

0  E  1  2  3

Requirements

• You must use meaningful variable names and good indentation. 
• You must not change the signature of any of the methods.
• Remember to provide pseudocode for the methods specified in the pseudocode file present in the code distribution.

Sample Run

After starting the game and entering 5

After pressing OK

After selecting empty cell 

After selecting second cell

After selecting second cell

Challenge Problems

Write a method called "solve()" to solve the puzzle.  There are three classes of solutions you might try.  In each case, solve should repeatedly call cellSelected() within a while loop, and continue until isSolutionCorrect() returns true.  You should test your solution for increasing puzzle sizes (starting at size 3), and for size, count how many times cellSelected was called.  Then print a table showing the number of clicks for each puzzle size.  The three approaches you might try are:

1. Random.  Just click on random squares until you get the correct solution.  You may find that this solution gets slow very quickly as the size of your puzzle increases.
2. At each step, calculate a "fitness function" for each potential click based on some metric of fitness that you devise.  Then, actually click on the cell with the highest fitness.
3. Think about how you as a human solve the problem, and isolate the algorithm you use to solve it efficiently.  Implement that algorithm.

Ideally, you would implement all 3 approaches and compare the efficiency of each approach (by looking at the results you printed in your table).

Submission

Submit your project using the submit project option associated with Eclipse.  Remember to complete your time log before submitting your homework.  You must submit all the classes associated with your homework, including the supporting classes (e.g., PuzzleGUIl) representing the picture infrastructure. (This is what should happen automatically when you use the 'submit' option in Eclipse.)

Web Accessibility