►Commonwealth School CS 3
Introduction to Class-based Program Design
▼Assignments
►Assignment 15: Arrays
On this page:
Sieve of Eratosthenes
Sudoku
8.6
    contents  ← prev  up  next → 

Assignment 15: Arrays

Goals: Practice working with arrays and hashes.

You should submit one .java file containing the solution to this problem.

Be sure to properly test your code and write purpose statements for your methods. A lack of tests and documentation will result in a lower grade! Remember that testing requires you to make some examples of data in an examples class.

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to some fixed \(n\). It works as follows:

  1. Write down all numbers 2, 3, 4... \(n\).

  2. Take the smallest unmarked number \(p\) (initially 2), and mark off every multiple of \(p\) higher than it.

  3. Let \(p\) be the next highest unmarked number, and repeat step 2. If there is no such number, stop.

  4. Every unmarked number remaining is prime.

Using an array, implement the Sieve of Eratosthenes. Encapsulate your answer as an iterator of integers, which given some integer n, will iterate over all primes up to and including n.

Note: your answer should not use division, modulus, or multiplication.

Hint: A good way to indicate whether or not some item in an index-based collection is marked is to use a boolean[].

Sudoku

Sudoku is a famous puzzle in which a 9x9 grid must be filled with the digits from 1 to 9 such that no row, column, or 3x3 subgrid (lying along the thirds of the outer grid) contains any repeats.

Develop a static method that determines if a given int[][] is a valid solution to some Sudoku puzzle. Be sure that it meets all of the constraints mentioned above. Abstract away duplicate logic whenever possible.

Note that you are not writing a Sudoku puzzle solver, which given an unfinished Sudoku puzzle outputs a solution, but a Sudoku solution verifier.

Hint: Look at the previous hint for an efficient way to mark off whether or not all numbers between 1-9 have been seen in a collection of 9 integers. Beware out of bounds errors!

    contents  ← prev  up  next →