Take-home labs are graded to provide you with feedback. However, the marks do not contribute to your final grade. Instead, one mark (attempt-mark) is awarded for each assignment -- and this mark goes into the computation of your final grade -- on the following conditions:
This lab requires you to do two exercises.
You are advised to review the material covered in chapters 1 through 11 and read Programming Style, Design and Marking Guidelines before attempting this lab assignment. You should not use syntax or constructs not yet covered in lectures; you shouldn't need to and may even be penalized for doing so (if the objective of the assignment is undermined). If in doubt, please ask for clarification in lecture or in the IVLE discussion forum.
Remember to spend some time thinking about the algorithm for each exercise and write out the pseudo-code on your own before you start typing in your program.
A word of advice: Code incrementally. Do not type in the whole program (especially when it is long) and then compile it. Instead, type your program in bits and pieces and compile it frequently. Try to maintain a compilable program even while you are working on it. Submitting a compilable program that partially works is better than submitting an un-compilable one. This last point especially applies to your sit-in labs and practical exam.
Note that:
For more information on CourseMarker, please refer to CS1101 Labs page.
For this lab, the number of submissions is set to 10. Only your last submission will be graded.
If you have any questions, you may post your queries in the IVLE discussion forum. Do not post your programs (partial or complete) in the forum before the deadline!
Write a program TextProcess.java to perform the following:
You are given the following code to be completed:
Bubble Sort is covered in Week 10, which is one week after the release of this lab. However, all you need to do is to adapt the following bubbleSort() method which sorts an integer array in increasing order. This method is also found in Week 10's Powerpoint file.
// Bubble Sort routine on an integer array 'numbers'.
// Sort the array in ascending order.
public static void bubbleSort(int[] numbers) {
int temp;
for (int last = numbers.length-1; last > 0; last--) {
for (int i = 0; i < last; i++) {
if (numbers[i] > numbers[i+1]) {
// swap numbers[i] with numbers[i+1]
temp = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
}
}
}
}
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first two lines (in green) below are commands issued to compile and run your Java programs if you are using in-line commands, for example, on UNIX. If you are not, you may ignore them.
$ javac TextProcess.java
$ java TextProcess
Enter start of replacement string: A
Enter end of replacement string : Z
Enter text, terminated by an empty line.
abcdAefghZijk
zyxAwvZutsArqpZonm
ggggAZhhhh
123A456Z789Z0
GGGGAZHHHH
123AZ0
GGGGAZHHHH
abcdAZijk
ggggAZhhhh
zyxAZonm
Second sample run:
$ java TextProcess
Enter start of replacement string: :
Enter end of replacement string : #
Enter text, terminated by an empty line.
#123:456;789+012#345:678;901+234
:a:b:c#d#e#f:g
#123:#345:678;901+234
:#f:g
Third sample run:
$ java TextProcess Enter start of replacement string: ABC Enter end of replacement string : XY Enter text, terminated by an empty line. abcdefghijklmnopqrstuvwxyz AXYZBCABCDEFXGHXYZ AXYZBCABCXYZ abcdefghijklmnopqrstuvwxyz
Fourth sample run:
$ java TextProcess
Enter start of replacement string: @@
Enter end of replacement string : @@
Enter text, terminated by an empty line.
**@@@@@@$$
PQ@@hhhh@RS
A@BC@@DEF
**@@@@$$
A@BC@@DEF
PQ@@hhhh@RS
Submit your program TextProcess.java through CourseMarker.
Sudoku is a popular logic-based number placement puzzle. The 9×9 board has 9 rows, 9 columns and 9 sections of 3×3 cells. The objective is to fill the board so that each row, each column and each section contains the digits from 1 to 9. There is only one unique solution. Figure 1 below, taken from Wikipedia: Sudoku, shows a Sudoku puzzle and its solution. (There are numerous websites on Sudoku, surf the Internet to explore!)
Figure 1. A Sudoku puzzle and its solution.
In this exercise, we shall solve mini-Sudoku puzzles on a 4×4 board. The board consists of digits from 0 to 4 where 0 represents a blank cell. The solver needs to replace all the 0s with the correct values (1 - 4).
You are given the following codes to be completed:
Sudoku.java
The class Sudoku defines a mini-Sudoku puzzle, using a two-dimensional 4×4 integer array as its data member. You are to complete the following methods (without changing the given method headers):
You may include additional method(s) to make your program more modular.
We will only give you the simplest Sudoku puzzles to solve. These puzzles are such that at any time, there is at most one blank cell (0) in a certain row, a column, or a 2×2 section. Hence, you are able to fill in the blank cells progressively until the whole board is filled.
One very simple algorithm for solve() is described below. We shall call it algorithm A.
Repeat the following until no more blank cells can be filled:
For each row, check whether there is a single 0. If so, replace that 0 with the obvious value.
For each column, check whether there is a single 0. If so, replace that 0 with the obvious value.
For each 2×2 section, check whether there is a single 0. If so, replace that 0 with the obvious value.
We will use an example to illustrate algorithm A. Figure 2a below shows a puzzle with seven blank cells, labelled from A to G for easy reference.
|
|
|
|
| Figure 2a. A Sudoku puzzle. | Figure 2b. | Figure 2c. | Figure 2d. The solution. |
After examining each row, we cannot fill in any blank cell as none of the rows has a single blank cell.
We proceed to examine every column. In the first column, we find that we can fill E with 2, and in the fourth column, B with 4, as shown in Figure 2b.
We proceed to examine every 2×2 section. We find that we can fill D with 1, F with 1, and G with 4. See Figure 2c.
The puzzle is still not solved, so we repeat the process. As we examine the rows this time, we find that we are able to fill A with 2, and C with 4. This gives the solution as shown in Figure 2d.
There are many possible algorithms to solve Sudoku puzzles. Let me show you another one below (let's call it algorithm B).
Repeat the following until no more blank cells is found:
Scan the board from top to bottom, and for each row from left to right.
For each blank cell encountered:Examine the row, column and section the blank cell is in,
if only one value for that blank cell fits, fill it with that value.
As algorithm B is more general than algorithm A, it is able to solve puzzles that the latter could not. For example, Figure 3 is one puzzle that can be solved by algorithm B but not by algorithm A. The solution is the same as Figure 2d. Of course, as a simple algorithm, algorithm B still does not solve all Sudoku puzzles (which is beyond the scope of CS1101.)
Figure 3. Another Sudoku puzzle.
However, as stated above, all puzzles given for this exercise are such that at any time you are able to find a row, column, or 2×2 section with only at most one blank cell, so puzzles like Figure 3 will not be given. Hence, you need only implement algorithm A, and not algorithm B or any other more complex algorithm.
In your solve() method, you may use ArrayList if you wish to.
PlaySudoku.java
PlaySudoku.java is an application program on the Sudoku class. Study the given partial code and complete the readBoard(Scanner) method.
The sample runs below show the user's inputs. 16 values are entered by the user, with 0 (zero) representing a blank cell.
(If you are programming in your sunfire UNIX account, or using line commands, you may simplify the data entry by creating a text file that contains the input data, then use the input redirection "<" to feed the data into your program. For example, create a text file sudoku.in that contains the 81 input values, and then type java PlaySudoku < sudoku.in to run the program.)
Sample run using interactive input (user's input shown in blue; output shown in bold purple). Note that the first three lines (in green) below are commands issued to compile and run your Java programs if you are using in-line commands, for example, on UNIX. If you are not, you may ignore them.
$ javac Sudoku.java $ javac PlaySudoku.java $ java PlaySudoku Enter the board, using 0 to indicate a blank cell: 1 0 3 0 3 0 0 2 4 3 2 1 0 0 0 3 The Sudoku puzzle solved: 1 2 3 4 3 4 1 2 4 3 2 1 2 1 4 3 (blank line here)
Second sample run:
$ java PlaySudoku Enter the board, using 0 to indicate a blank cell: 0 1 3 2 2 0 1 0 1 0 0 3 3 4 2 1 The Sudoku puzzle solved: 4 1 3 2 2 3 1 4 1 2 4 3 3 4 2 1 (blank line here)
Submit your programs Sudoku.java and PlaySudoku.java through CourseMarker.
The suggestions below are for your own practice and are not to be submitted.
Write a more general solver to solve more complex Sudoku puzzles. Then extend your algorithm to the original 9×9 Sudoku board. Have fun!
For a 4×4 board, we can interactively enter the 16 input values. How about a 9×9 board? It will be too tedious to enter the 81 input values interactively. This is where file (Chapter 12 File Input and Output) comes in. Rewrite your program to read the input values from a text file.
The deadline for submitting all programs is 26 October 2009, Monday, 23:59hr. Late submissions will NOT be accepted.