CS 1025 Computer Science Fundamentals I
Assignment 2

Department of Computer Science
University of Western Ontario
Given: October 4, 2011
Due: October 17, 2011

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).

Introduction

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

an int field N, initialized to 3, and
an int[][] field named board that will be initialized as new int[N*N][N*N].

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.

The constructor

Sudoku();

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

void show();

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

void fill(String[] lines);

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.

Once this works, write

void fancyFill(String[] lines);

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.

Question 3. A Sudoku Verifier (15 points)

Write a method

boolean isSolution();

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

Sudoku solve();

that takes a partially filled Sudoku and constructs a correct solution, if one exists, or returns null if none exists.