CS 242 Spring 2012 : Assignment 1.0

This page last changed on Jan 29, 2012 by cemeyer2.

Assignment 1.0 – Queens on a Chessboard

Note, always remember to check this assignment description for Update markers over the course of the next few days for changes or clarifications to this assignment specification. If any major changes are made to this spec, we will announce them both on the front page of the course website as well as on the course piazza space.

Objectives:

  • Write unit tests to guide the development of a puzzle solver
  • Use your unit tests to prove that it works
  • You will write the tests before you implement the functionality
  • You will finish off this assignment by implementing the puzzle solver.
Both the unit tests and implementation for your program are due this week!

Goals:

  • Learn about Test-Driven Development
  • Learn the value of completely planning out a design before diving into its implementation
  • Learn how to write unit tests
  • Learn the basics of object-oriented design

Required Reading: Code Complete Chapter 22: Developer Testing

Even though the code for assignments is due on the Thursday the week following the release of the assignment, the readings are due for the lecture on the Monday of that week.
Questions that appear in lecture quizzes may come from the assigned reading, so it is in your best interest to complete it.

Language: Java with JUnit

For this assignment, you MUST either use the Eclipse IDE or IntelliJ IDEA (most likely community edition unless you want to buy a student license). Charlie, as well as a few other staff members, think IntelliJ totally ROCKS!

Both Eclipse and IntelliJ IDEA run on Windows, Mac, and Linux. Download links:

Since you are required to use Eclipse or IDEA to complete this assignment, we highly recommend that you use the Subversive Subversion plugin for Eclipse (SVN support comes with IDEA by default) to handle adding your code to Subversion and tracking changes. It is easier than the command line svn client, especially if you are new to Subversion. Instructions on how to set up and use the plugin can be found at Using Subversion From Eclipse (these directions are a few semesters old, so you may want to use them as a rough guide).

Tutorial: Testing with JUnit: http://www.vogella.de/articles/JUnit/article.html

Due Date

  • Reading and tutorial: Monday January 30th at 4:00pm CST
  • Code: Thursday February 2nd at 8:00am CST in Subversion
Your code must be committed to a folder in Subversion called Assignment1.0. This is so that we can easily find it and grade it. In the future, we will do code reading which will require accurate naming.

You should be able see your committed code at https://subversion.ews.illinois.edu/svn/sp12-cs242/NETID/Assignment1.0 (replacing NETID with your netid)

Queens on a Chessboard

This is a classic computer science problem that asks, what are the configurations that you can create such that n queens occupy n distinct spots on a n by n chess board such that no two queens can attack each other. This means that no two queens can share a row, a column, or a diagonal. There are solutions for all natural n except for 2 and 3. Play the game below to get a feel for how it works:

queens.swf
courtesy of http://www.coolmath4kids.com/math_puzzles/Logic-eightqueens/index.html

It may help to read the article on the source of all lies for some extra background information.

Your task for this week is to create a program that can solve this puzzle, namely we expect:

  • your program must be written in Java
  • you must write your tests before the implementation
  • you must use an IDE such as Eclipse or Intellij IDEA
  • your program must be console driven
  • your program must either prompt for or take an argument for n which is:
    • the size of the board
    • the number of queens to place on the board
  • your program must print out all of the solutions to the problem to console in a “nice” ASCII format
  • you must use a “smart” algorithm, that is, no brute-force solutions
    • for n=8, there are 4,426,165,368 possible arrangements of 8 queens on the board (64 choose 8)

Design Hints

We do not require any cookie cutter form for your code each week. That is, each week you will start from scratch and design and code everything yourself. For this first week, here are a few hints of what you should have:

  • public class Board
    • public boolean placePiece(int x, int y, Piece piece)
    • public boolean isValid()
    • public Piece getPieceAt(int x, int y)
    • public Set<Piece> getPieces()
    • public void reset()
    • public void print()
  • public abstract class Piece
    • public abstract boolean canAttack(int x, int y)
    • public int getX()
    • public int getY()
    • public int setX(int x)
    • public int setY(int y)
    • public Board getParentBoard()
    • public void setParentBoard(Board board)
  • public class Queen extends Piece
  • public abstract class PuzzleSolver
    • public abstract void solve(List<Piece> pieces) (feel free to change the return type)
  • public class NQueensSolver extends PuzzleSolver
  • public class ChessPuzzlesDriver
    • public static void main(String[] args)
This is by no means the only, best, or most complete way to design code for this assignment and you are free to do whatever design you wish, but this is a good start.
For this course, remember that there is a strict limit of 25 lines of code per function. To accomplish this, you will need to think smartly about how to decompose your solution into its smallest functional units, then use higher level functions to tie them together.

Testing

For this assignment, you must use Test-Driven Development (TDD). Here are the steps:

  1. Stub out your design. That is, write empty classes with empty methods. Add bogus return values where necessary, such as false for a boolean method, 0 for an int method, null for a method that returns an object, etc.
  2. Commit to Subversion.
  3. Write all of your tests. When you run your tests, the overwhelming majority of them should fail!
  4. Commit to Subversion
  5. Write your implementation. As you write your implementation, continually run your tests. They should slowly start to pass. Commit to Subversion as you implement.
We will grade your Subversion commit history to ensure that you have followed this methodology, so please follow these steps and commit often to earn full points.

Unit testing is a great way to ensure that, given an implementation, the code works correctly. This is enforced by creating small (unit) tests for each function. Each test should be able to call the function it is testing, and determine if the function worked according to specification.

This can be a funny concept at first, but it is really quite simple: If you know the input to a function, and you know how the function works, you should know exactly what the output of the function is. Since you know what the output should be before even calling the function, you can compare the output you get from making the function call to the expected output. If they match up, then the test has succeeded. Otherwise, it fails.

In general, one test is not sufficient to be confident in the correctness of a function. While it is better than nothing, a complete test suite would try all corner-cases, as well as the common case. For instance, if a function operates on positive integers, and it is called with a negative parameter, does it do the right thing? The success and failure of tests are completely defined by the person designing the application. Therefore, it is necessary to clearly understand what a function should do in order to test it.

Each test should be named in a fashion that clearly says what it does. Each test should be written in such a way that it is immediately apparent from the prose of its statements:

  • the objects it works on,
  • specific methods it tests,
  • an exceptions it calls or handles,
  • any preconditions and postconditions that must be met.

The test must also include comments that fully explain what it is testing.

An example of a valid JUnit test would look like (for an imaginary Phone object):

public class PhoneTests {
        //note these are jUnit 4 style tests, the naming convention is different for jUnit 3 style tests

        /**
	* The constructor is supplied with valid values so no exceptions should be thrown.
	*/
	@Test
	public void ValidConstructor1() throws Exception {
                String number = "1-555-555-5555"
                String name = "Charlie Meyer"
		Phone phone = new Phone(name,number);
		assertEquals(number, phone.getNumber());
                assertEquals(name, phone.getName());

	}

	/**
	* This test checks the case where the constructor is supplied a phone number with too many dashes.
	*/
        @Test(expected=InvalidPhoneNumberException.class)
	public void TooManyDashes() throws Exception {
                String number = "9-9-999-999-9999";
                String name = "Charlie Meyer";
		Phone phone = new Phone(name,number);
	}

        //more tests below of course, you can never have too many!
}

Good testing requires you to test for the unexpected. Every function should have at least one test. However to get full credit, you should write tests which cover all corner cases and other possibilities that your library may eventually encounter.

When writing your functions always keep in mind writing them so that they are easy to test. The more focused each individual function is, the easier it will be to test, and the more correct your code will be. Modularity is key to unit-testing. It may even be a good idea to split your library into multiple classes depending on the data structure you use as an internal representation for a maze.

There are some resources which aid in the unit testing process, such as JUnit for Eclipse. You are free to use these if you would like. Eclipse and JUnit are available on the EWS Linux computers, and an introduction to using JUnit with Eclipse is provided in this assignment description.

Introduction to Eclipse and JUnit

An example of JUnit 4 tests was shown above. Generally, developers put all unit tests for one type in one file, with multiple files of tests composing a test suite for the library or application. It will be much easier for you to keep things organized if you follow a similar pattern. Although Eclipse will let you run a single file containing JUnit tests directly, it takes a bit more effort to have Eclipse run all tests in all files at once (your test suite). For example, say I had tests for a Phone object in a file called PhoneTests and tests for an Address object in a file called AddressTests, I could have the Eclipse JUnit runner run them both by creating a file called something like ContactInfoTests and have it contain:

package contactInfo.tests;

import org.junit.runner.RunWith;
import org.junit.runners.Suite;

/**
 * Runs all tests for classes in the <code>contactInfo</code> package
 * @author Jerome Bell
 *
 */
@RunWith(Suite.class)
@Suite.SuiteClasses({AddressTests.class, PhoneTests.class})
public class ContactInfoTests {
}

If I was to then instruct Eclipse to run ContactInfoTests as a JUnit test, it would run all the tests in both the PhoneTests class and the AddressTests class. You might not need to, but you can chain it up even further if you divide your tests into subcategories and have a master suite file like:

package allTests;

import junit.framework.TestSuite;
import org.junit.runner.RunWith;
import org.junit.runners.Suite;
import contactInfo.tests.ContactInfoTests;
import persistence.tests.DatabaseInterfaceTests;

@RunWith(Suite.class)
@Suite.SuiteClasses({ContactInfoTests.class, DatabaseInterfaceTests.class})
public class RunAllTests extends TestSuite{
}
Things you should test for

You should test for several things to ensure full coverage:

  • successful construction of objects
  • each method an object has
    • usual use cases
    • corner cases

The usual use cases for each method should be straightforward to come up with. The corner cases will be tougher, and you will only receive full testing points if you have extensive corner case coverage. Examples of corner cases are:

  • What happens when you place a piece at invalid coordinates
  • What happens when a piece has invalid coordinates
  • What happens when methods unexpectedly return null
  • What happens when something is improperly modified
  • etc

This is not a complete list, you will need to brainstorm to come up with further ideas. Feel free to post your ideas on the course piazza space. You should have about the same number of lines of test code as you do implementation code.

Documentation

Everywhere possible, you must comment your code using Javadoc style. This means you must comment all classes, all methods, and all public fields. Use all tags possible, such as:

In addition, include a short README.txt that describes how to run your code.

Challenge!

If you complete all of functional requirements, you are free to try the challenges that accompany most of the assignments in this course. You are not obligated to do them, but they will usually add a “coolness” factor to your work. For this week, the challenge is to visualize the attack patterns of the queens on the chess board. For instance, if your code outputs:

+-+-+-+-+
| | |Q| |
+-+-+-+-+
|Q| | | |
+-+-+-+-+
| | | |Q|
+-+-+-+-+
| |Q| | |
+-+-+-+-+

You might want to visualize the attack paths like:

+---+---+---+---+
| - | - | Q | - |
+---+---+---+---+
| Q | / | | |  |
+---+---+---+---+
| / |   | | | Q |
+---+---+---+---+
|   | Q | | |   |
+---+---+---+---+

+---+---+---+---+
| | | / | Q |   |
+---+---+---+---+
| Q | - | - | - |
+---+---+---+---+
| | |  |   | Q |
+---+---+---+---+
| | | Q |  |   |
+---+---+---+---+

+---+---+---+---+
|   |  | Q | | |
+---+---+---+---+
| Q |   |  | | |
+---+---+---+---+
| - | - | - | Q |
+---+---+---+---+
|   | Q | / | | |
+---+---+---+---+

+---+---+---+---+
|   | | | Q |   |
+---+---+---+---+
| Q | | |   | / |
+---+---+---+---+
|  | | | / | Q |
+---+---+---+---+
| - | Q | - | - |
+---+---+---+---+

+-----+-----+-----+-----+
| -|  | -/||  Q  | -|  |
+-----+-----+-----+-----+
|  Q  | /-| | |- | -|/|
+-----+-----+-----+-----+
| /|-| -| | |-/ |  Q  |
+-----+-----+-----+-----+
| |-  |  Q  | |/-|  |- |
+-----+-----+-----+-----+

It’s up to you to determine how to complete this challenge, should you choose to accept it. This is just an idea.

Important Questions to Consider

Still confused or need help?

First, ask questions on the piazza space. If you have a question, there is a pretty good chance someone else has the some one and an even better chance that someone else in the class or one of the TAs will be able to answer it for you. If you are still having a problem, email your moderator or one of the TAs to get advice. Remember, its best to ask questions early on so they have time to be answered. Don’t wait until the last second to get started then realize that you are confused.

Requirements

We will bias clarity over cleverness in evaluating your code. You should adopt a “teaching” mindset, always asking yourself, “How would I change what I have written to make it as easy as possible for someone else to understand my code without my direct assistance?”

We will use the standard Grading rubric for this assignment.

Category Weight Notes
Basic Preparation 2 Ready to go at the start of section
Cleverness 2 The hardest points on the rubric
Code Submission 4 Submitted on time and to the correct location in the repository
Decomposition 6  
Documentation 6 Javadoc comments for each class and each function listing a brief summary, its parameters, and its return value
Effort 2  
Naming 4  
Overall Design 6  
Participation 6  
Presentation 2  
Requirements Satisfaction 6 Able to properly set up data structures
Requirements Satisfaction 8 Able to properly solve the n-queens problem
Requirements Satisfaction 4 Able to properly output the found solution(s)
Testing 18 Unit tests for all public functions, acceptable (>75%) coverage

queens.swf (application/x-shockwave-flash)
Document generated by Confluence on Mar 29, 2012 02:55

  1. No comments yet.

  1. No trackbacks yet.