# CS 1025 Computer Science Fundamentals I

Assignment 2

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

## 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

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

`
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

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.