CS 1025 Computer Science Fundamentals I
Department of Computer Science
University of Western Ontario
Given: September 27, 2012
Due: October 22, 2012 (extended 5 days)
This assignment is out of a total of 60 points.
By answering the bonus questions, you can get up to 120 points out of 60.
These bonus points can be used to make up for points missed on other assignments (other assignments in this course only, however).
Sudoku is a number-placing puzzle played on 9x9 board. It is
described in the Wikipedia article
http://en.wikipedia.org/wiki/Sudoku. This assignment is based on creating and manipulating Sudokus.
For each of the questions below, hand in
- an implementation
- documentation of the class and each method
- the output
Question 1. The Sudoku Class (30 points)
Create a class called Sudoku that has
Each array element board[i][j] will either contain an integer between 1 and 9, inclusive, to represent a square with a number in it, or will contain 0, indicating an empty square.
- an int field N, initialized to 3, and
- an int field named board that will be initialized as new int[N*N][N*N].
should initialize board to be an array
of size N*N (i.e. 9) in which each element is an array of size N*N in which each element is initialized to 0.
The class should have the methods
- void setSquare(i,j, val); // Sets board[i][j] = val.
- int getSquare(i,j); // Gets the value of board[i][j]
The class should also have the method
that prints the Sudoku out using System.out.print. A Sudoku s would be displayed by calling s.show(). The 3x3 sub-blocks should be separated using the characters "|", "-" and "+", and empty squares should be printed with dots, not zeros. Example:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 8 9 | . . . | . 6 .
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
Write the Sudoku class with the desired constructor and methods, show that it works with appropriate test cases, and document it properly.
Question 2. A Fill Function and a Nicer Fill Function (15 points)
Write a method
in the Sudoku class that takes an array of N*N Strings.
Each string represents a row and has N*N characters, each of which is either a digit or period. Periods indicate empty squares. For example, if N=3, then the input array will have 9 strings with 9 characters each.
void fill(String lines);
Once this works, write
that additionally allows blanks and the characters "|", "-", "+". These additional characters are ignored if they appear. Lines made up entirely of these characters are also to be ignored.
void fancyFill(String lines);
Question 3. A Sudoku Verifier (15 points)
Write a method
that checks whether a Sudoku contains a valid solution. That is, that
- it is completely filled,
- each row contains each of the numbers 1 to N*N (= 9) exactly once,
- each column contains each of the numbers 1 to N*N exactly once,
- each of the NxN (3x3) blocks contains each of the numbers 1 to N*N exactly once.
Question 4 [BONUS]. Big Sudoku (20 points)
Generalize your Sudoku class to work with bigger or smaller sizes.
Whatever value N has, the arrays and strings should have N*N elements, taking values from 1..N*N. Test this with N=1, N=2, N=3, N=4.
Question 5 [BONUS]. Solver (40 points)
Add a method
that takes a partially filled Sudoku and constructs a correct solution, if one exists, or returns null if none exists.