Due: Tuesday September 26th BEFORE THE START OF CLASS
Revisions History:
Created January 23rd, 2014
Assignment Goals:
Question 1:
Hitori is a Japanese puzzle in the spirt of Sudoku, Wikipedia describes it as follows:"Hitori is played on a grid of squares. At the beginning, each cell contains a number. The goal is to paint out some cells so that there are no duplicate numbers in any row or column, similar to the solved state of a Sudoku puzzle (except with black squares added to the grid).
Orthogonal connections are important as well; painted-out (black) cells cannot be connected orthogonally, and the other cells must be connected orthogonally in a single group. (i.e. no two black squares can be adjacent to each other, and all un-painted squares must be connected, horizontally or vertically, to create a single shape.)"
An example, taken from the Wikipedia Hitori page (http://en.wikipedia.org/wiki/Hitori) is given below on the left, with its solution on the right..
Your task:
a) Create a java class called Hitori to represent a puzzle. It should maintain an array of "cell" objects and should contain at least the following public methods:
Hitori (String filename) - A constructor that reads a sample puzzle from the specified text file. To get you started I have created four sample puzzle files and a solution for the first. You may want to investigate the Scanner class to help you. In particular how to create a Scanner "Scanner scanner = new Scanner(new File(filename));" and how to read an integer, "scanner.nextInt();". Be sure to handle the "file not found" exception and any error in reading the file gracefully using Java's exception mechanism.display() - This method display the current state of the puzzle. You can either learn a little bit about Java Graphics and display the puzzle that way or write out a file in HTML format that uses a table to display the result. For example,
public void display() {
try {
PrintWriter out = new PrintWriter(new FileWriter("solution_" + filename + ".html"));
out.println("<html>" + "<body>" + "<table border=\"1\" cellspacing=\"1\">");
for (int row = 0; row < sizeRows; row++){
out.println("<tr>");
for (int col = 0; col < sizeCols; col++){
out.print(grid[row][col].displayCell());
}
out.println("</tr>");
}
out.println("</table>" + "</body>" + "</html>");
out.close();
} catch (IOException e) {e.printStackTrace();}
}
where the cell objects support the following method:
public String displayCell(){
if (isBlack())
return "<td width=\"50\" height=\"50\" align=\"center\" bgcolor=\"#000000\"><font size=\"6\" color=\"#808080\">" + value + "</font></td>";
else if (isWhite())
return "<td width=\"50\" height=\"50\" align=\"center\"><font size=\"6\">" + value + "</font></td>";
else
return "<td width=\"50\" height=\"50\" align=\"center\" bgcolor=\"#728FCE\"><font size=\"6\" color=\"#808080\">" + value + "</font></td>";
}
b) Now comes the interesting part! Add to your Hitori class a method called solve(int location) which uses recursion to complete a Hitori puzzle. To solve the puzzle use a brute force recursive method that tries all possibilities. The key recursive routine might look something like this:
public boolean solve(int location){
int row = location / sizeCols;
int col= location % sizeCols;
if ("beyond the end of the puzzle") //at end of puzzle
return true;
else { //Try to make the location "white"
"Set grid[row][col] to White";
if ("All conditions still ok" && "Can solve(location+1)")
return true;
else{ //Try to make the location "black"
"Set grid[row][col] to Black";
if ("All conditions still ok" && "Can solve(location+1)")
return true;
else { //This location can be neither white nor black
//therefore an error must have been made previously
//so set unknown and backtrack
"Set grid[row][col] to Unknown";
return false;
}
}
}
}
If you are unsure of how to go about designing a recursive enumeration you might want to look over the Maze_Search program.
c) Augment your program so that it reports timing statistics. If we call a "Trial" setting a single location either while or black, how many trials per second does you code make. Show the output of your timing results in your testing.
d) Will your code always find a solution? Argue why or why not.
e) Using big-oh notation describe the complexity of your method.
Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing!
Question 2:
Write a program that prompts the user for a year (e.g. 1945) and then prints a calendar for that year. The entire year should be laid out in 4 rows of months each consisting of 3 months. Each month should be printed in the following format.
January
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
You may use the code in the directory calPrinter as a starting point, but be sure to document it well and clean up any of the "bad programming habits" that you find in it. You also have to implement toString method in Month class.
Hint: Use a multidimensional array to store month objects. Implement a method called weekString in the month class that given an integer x between 0-5 returns the string representing the xth week. weekString(2) sent to the month object shown below should return "12 13 14 15 16 17 18". You can't change code until you understand it. Go over the calPrinter classes carefully before you begin.
Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing! What kind of special cases are important to test for?
Note: No late assignments will be accepted.