University of Washington, CSE 190 M, Spring 2008
Homework Assignment 4: Fifteen Puzzle
due Wednesday, April 30, 2008, 11:00pm electronically

Background Information:

The "Fifteen puzzle" (more generally called the Sliding Puzzle) is a simple classic game consisting of a 4x4 grid of numbered squares with one square missing. The object of the game is to arrange the tiles into numerical order by repeatedly sliding a square that neighbors the missing square into its empty space.

The main task for this assignment is to write the JavaScript code for a web page fifteen.html that plays the Fifteen Puzzle. Your page must match the appearance and behavior specified in this document, though some variations and add-ons will be described.

You will also submit a background image of your own choosing. Your game should be configured to display this background image underneath its tiles. You can choose any image you like, so long as its tiles can be distinguished on the game board.

In total you will turn in the following files:

• fifteen_script.js, the JavaScript code for your web page
• background.jpg, your background image, suitable for a puzzle of size 400x400px

You will not submit any .html or .css file, nor directly write any XHTML or CSS code in this assignment. Instead, we will provide you with the XHTML and CSS code to use, which should not be modified. (You should download these files to your machine while you're writing your JavaScript code, but your code should work with the provided files unmodified.) To modify the page's behavior and content, write JavaScript code that interacts with the page using the DOM. To modify its appearance, write appropriate DOM code to change styles of onscreen elements by setting classes, IDs, and/or style properties on them.

Appearance Details:

In the center of the page is a set of tiles representing the playable Fifteen Puzzle game. Each tile is 100x100 pixels in total size, with a 2px black border around all four of its sides. (This leaves 96x96 pixels visible area inside the tile.) Each tile displays a number from 1 to 15 in 32pt text using the default sans-serif font available on the system. When the page loads, initially the tiles are arranged in their correct order, top to bottom, left to right, with the missing square in the bottom-right. The tiles also display a chunk of the image background.jpg, assumed to be located in the same folder as your page. (A CSS class named puzzlepiece has been created for you that represents these styles, but nothing on the existing page uses this class. If you want any onscreen elements to use this class, you'll have to set it using DOM code.)

Your background image appears on the 15 puzzle pieces because it is set as the background-image of each puzzle piece. By adjusting the background-position on each div, you'll be able to show a different piece of the background on each of the 15 puzzle pieces.

Centered underneath the puzzle tiles is a Shuffle button that can be clicked to randomly rearrange the tiles of the puzzle. The last content on the page is a right-aligned paragraph containing two links to the W3C validators and JSLint. These are the same images and links as used in the previous assignments. The images should not have borders.

All other style elements on the page are subject to the preference of the web browser. The screenshots in this document were taken on Windows XP in Firefox 2.0, which may differ from your system.

Behavior Details:

When the mouse button is pressed on a square of the puzzle, if that square is next to the blank square, it is moved into the blank space. If the square on which the mouse was pressed does not neighbor the blank square, no action occurs. Similarly, if the mouse is pressed on the empty square or elsewhere on the page, no action occurs.

Whenever the mouse cursor hovers over a square that can be moved (that is, one that neighbors the blank square), its appearance should change. Its border coler should change from black to red. Its text should become bold and underlined and should become drawn in a purple color of #660066. (A CSS class named puzzlepiecehover already exists that represents these styles.) Once the cursor is no longer hovering over the square, its appearance should revert to its original state. Hovering the mouse over a square that cannot be moved has no effect.

When the Shuffle button is clicked, the tiles of the puzzle are randomized. The tiles must be rearranged into a solvable state. Note that many states of the puzzle are not solvable; for example, it has been proven that the puzzle cannot be solved if you switch only its 14 and 15 tiles. We suggest that you generate a random solvable puzzle state by repeatedly choosing a random neighbor of the missing tile and sliding it onto the missing tile's space. A few hundred such random movements should produce a shuffled board. Your shuffle algorithm should be relatively efficient; if it takes more than a second to run, you may lose points.

The game takes no special action when the puzzle has been won, that is, when the tiles have been rearranged into their correct order.

For CSE Majors:

CSE majors must do at least two (2) of the following additional features. Please choose which features you want to implement and place a comment at the top of your JS file stating which features you have implemented. If you have another feature you'd like to do that is not on the following list, please ask the instructor and we may allow it to substitute for one of the features below.

• Ability to slide multiple squares at once: In many implementations of this game, if you click aany square in the empty square's row or column, even ones more than one spot away from the empty square, all squares between it and the empty square slide over. This is a nice way to let the user make multiple similar moves without manually clicking each tile.
• Game time and end-of-game: The game is more fun if you can actually detect when the user has "won" it. Keep track of the game time and number of moves, and when the puzzle has been rearranged into the original order, tell the user that he/she has won. Also show the best time/moves on the screen.
• Animations and/or transitions: Instead of each tile immediately appearing in its new position, make them animate. You can do any sort of animation or other styling you like, as long as the game ends up in the proper state after a reasonable amount of time.
• Multiple backgrounds: Provide several background images (at least 4) to choose from. The game should choose a random background on startup, and should have a UI (such as a select box) by which the player can choose a different image while playing. You can host your additional backgrounds on the Webster server.

Please note that you must make any additional features without modifying the XHTML or CSS files directly; each must be done entirely through JavaScript code. CSE non-majors may also choose to implement these features, but they will receive no bonus for doing so. Such features in a non-major's program will be ignored for grading so long as they do not break any existing core functionality.

Implementation and Grading:

We suggest the following development strategy for this assignment:

• Make the fifteen puzzle pieces appear in the correct positions with the correct parts of the background showing through.
• Write code that determines whether a given piece can currently move or not. Use this to implement the highlighting style that occurs when the user's mouse hovers over tiles that can be moved. This will require you to keep track of where the empty square is at all times.
• Write the code that moves tiles from their current location to the empty square's location. Only move tiles that can be moved (ones that neighbor the empty square).
• Write the shuffling algorithm.

Submit your assignment online from the turnin area of the course web site. For reference, our solution has 112 lines of JavaScript including blank lines and comments.

For full credit, your JavaScript code should pass the provided JSLint tool with no errors reported (when the Recommended options are checked). You should also follow reasonable stylistic guidelines similar to those you would follow on a CSE 14x programming assignment. In particular, you should avoid redundant code, minimize the number of global variables, utilize parameters and return values properly, correctly use indentation and spacing, and place a comment header on top of the file and atop every function explaining that function's behavior. You should only use material that has been discussed during the first four weeks of the course or shown in the first four textbook chapters and lecture slides unless given permission by the instructor.

Three aspects of your JavaScript style deserve particular emphasis. The first is that you should minimize redundant code. The second is that you should exercise good procedural decomposition, breaking down lengthy operations into multiple functions. The third is that you should not use JavaScript as a substitute for CSS. As much as possible, your JavaScript code should set elements to use stylistic information in CSS stylesheets rather than manually setting every individual style property in your JS code.

Implement the behavior of each onscreen control using JavaScript event handlers defined in your script file. For full credit, you must write your code using unobtrusive JavaScript, so that no JavaScript code, onclick handlers, etc. are embedded into the XHTML code.

Here are some hints to help you solve particular aspects of the assignment:

• It may be helpful to you to store the puzzle pieces into an array and/or give id values to each square of the board, such as "square_2_3" for the square in row 2, column 3, so that you can more easily access these squares later in your JavaScript code. (Such id values would need to change as squares moved on the board.)
• Recall that you can convert a String into an integer using the parseInt function. This function also works for Strings that begin with an integer and end with non-numeric content. For example, parseInt("100px") returns the number 100.
• Recall that you can generate a random number from 0 to MAX, or randomly choose between MAX choices, by saying Math.floor(Math.random() * MAX).

You may be able to find Fifteen Puzzle games written in JavaScript on the internet. Please do not look for or examine source code of any such games. Examining such code or submitting it (or your own code derived from it) in any form is a violation of our course academic integrity policy. We have done searches to find several of the most common such games and will include them in our automatic similarity detection.

Part of your grade will also come from successfully uploading your files to the Webster web server. You should place your files into your public web space in a subdirectory named hw4, so that it is possible to navigate to your page by entering the following URL into the browser:

• https://webster.cs.washington.edu/your_uw_netid/hw4/fifteen.html

Please do not place a solution to this assignment online on a publicly accessible (not password protected) web site. Doing so is a violation of the course academic integrity policy.

Except where otherwise noted, this document's contents are © Copyright 2008 Marty Stepp / Jessica Miller and licensed under Creative Commons Attribution 2.5 License.