You may work with a single partner on HW#2. You may not share code in any form with anyone other than your partner! Feel free to get ideas from sample JavaScript you can find on the WWW, but DO NOT submit code that you did not write. Submitting code you find on the web is a violation of the course policy on academic integrity and will result in (at a minimum) a zero for HW2 and a 2 letter grade drop for the course.

---

You need to create an HTML document (that includes JavaScript) that provides a Sudoku puzzle. Sudoku is a logic puzzle traditionally played on on 9x9 board, although this homework only requires a 4x4 board.

---

Sudoku Description

See the links above for a more complete description, this is just the basic idea...

Your web page will include the display of a 4x4 grid, in which the grid is split into 4 quadrants. There are a total of 16 cells that make up the grid. An empty grid is shown on the right.

The puzzle rules are that the user must place the digits 1,2,3 and 4 in the cells so that:

• each row contains all the digits 1-4
• each column contains all the digits 1-4
• each quadrant (2x2 box) contains all the digits 1-4

A new puzzle is not blank, but instead contains some cells with values already assigned. The work the user does is to fill in the blank cells without violating any of the above conditions. Once the user has successfully filled in all the cells without violating any of the rules, the puzzle has been solved.

For example, on the right is what a new puzzle might look like, this one has 5 cells already filled in. Some valid moves include:

Placing a three in the top left corner

Placing a one in the second row, third column

Some invalid moves include:

Placing a one in the top row, second column. This is not valid since there is already a one in the second column.

Placing a two in in the second row. There is already a two in the second row.

Placing a four in in the second row, third column. This is not valid since there is already a four in the upper-right quadrant.

Your 4x4 Sudoku puzzle must provide the following:

• Start a new game at any time (by pressing a button or some similar action). You need to use a random number generator to produce a different game each time! See notes below on constructing new games.

• Enforce the rules. A player must not be able to place a digit in any way that violates the rules.

• You can allow players to clear any cells that they have filled in, but your don't have to support this. A player can never remove or change any digit that was placed by the computer in the original puzzle.

• Recognize when someone has won and provide some indication that the user is brilliant. You canb pop up an alert, or arrange for a message to appear in the web page, or flash colors or whatever... The point is, your program must recognize when the puzzle has been solved.

Implementation and UI Notes

You decide how the user makes moves. You can capture keyboard events with onKeyPress, or have the user use the mouse - anything is fine (although it must be easy to understand how to make moves!).

You decide what happens when the user tries to make an invalid move (alert, message, flashing colors, etc...).

You should definitely be using CSS!

How to create a new game

You can't just randomly assign digits to random places on an empty board and assume that it will be possible to solve the puzzle. For example, this puzzle has no solution.

The general strategy is to create a completed puzzle so that you know it can be solved, then simply remove a bunch of digits. All the user sees is the new board, you don't display the original (with the complete solution). You must be able to provide some randomness to this process, that is, you need to generate a completed puzzle that is in part, based on some random placement of digits.

It is a fairly complex process to generate a complete 9x9 Sudoku solution (this actually requires a computer program that can solve a Sudoku puzzle), but it's much simpler for a 4x4 puzzle. Below are instructions that will provide one way of generating a completed 4x4 Sudoku puzzle:

1.

Generate a random permutation of the digits 1-4 and place these digits in the top quadrant. For example, if the permutation generated was (1,3,4,2) the resulting partial puzzle would look like this. Since this involves placing each digit only once, there is no possibility of any illegal placement.

2.

Shift the permutation generated in step 1 one position, so if you had (1,3,4,2) you now get (3,4,2,1). Use this new order to place digits in the lower right quadrant. There is no possible conflict, since the digits in these quadrants don't fall in the same row or column as the digits in the top left quadrant.

3.

Finding the right digit to place in each of the remaining cells is now easy. For example, placing a 1 in the upper right quadrant can be done by finding the row (either row 1 or row 2) that does not contain a 1 already in it, and the column (either column 3 or 4) that does not already contain a 1 in it. The process is basically the same for the other 7 cells.

What to submit and how to submit

You need to submit your HTML file to the WebCT dropbox labeled "hw2". If your page references any images, you must also submit those files, and your HTML document must use relative URLs!. We will be viewing your submissions on our machines, not on yours, so if you have something like the image tag shown below we won't see your images and you will lose points!:

<img src="file://c:/eiw/blah.gif">

IMPORTANT!!!: If you work with a partner, you should only have one person submit, and the HTML file must include the names of both team members (this must appear when we view your page in a broswer, we don't want to have to hunt through the code for this).