Objective

This homework cover the following topics:

• Algorithm design
• Arrays
• MVC (Model-View-Controller) model of interaction.

In case you have not already noticed, this is an Open homework.  You must read the Open/Closed policy before working on this project.  The policy can be found at policy. 

Specifications

Sudoku Overview

For this project you will write a class named Sudoku, that implements the game logic associated with the popular puzzle game sudoku. The goal of the game is to complete a grid with numbers so that every row, column and 3 by 3 grid (differentiated by shading) has every digit from 1 to 9 inclusive.  The following is an example of a sudoku matrix:

More information about sudoku can be found in the following sites:

• wikipedia
• http://www.sudokupuzz.com (you can play the game at this site)
• http://www.sudoku.com

In this project the term "move" means entering a value into a square of the sudoku matrix.  A legal move is one where the number provided does not violates the sudoku rules.

Code Distribution

The project's code distribution is available by checking out the project named p1.  To access your cvs repository, you will need the following information:

The distribution includes a data directory with text files representing sudoku games and a package named cs132.p1.

data directory

This directory has text files representing sudoku games.  In the text file a period represents an empty square in the sudoku matrix. 

cs132.p1 package

      The following classes can be found in this package:

• Sudoku -This is the class you are expected to implement for this project.  In the Sudoku.java file you will find a shell for each of the public methods you are expected to implement.  The javadoc documentation for this project can be found at: doc/index.html.  Feel free to add any private data members and private methods you understand you need.

• TextUI - This is a class that makes use of the Sudoku class you will implement. You don't need to modify this class.  Executing the main method of this class, will randomly select one of the sudoku text files (present in the data directory) and solve the sudoku game. The class is used by the GraphicalUI class.

• GraphicalUI - Represents the GUI (Graphical User Interface) for the sudoku application.  Executing the main method of this class, will allow you to play sudoku through the GUI.  This class relies on the TextUI class to select the initial sudoku grid.  You don't need to modify this class. 

   

  While using the GUI keep in mind:

  • Once a number representing a valid move has been entered in a square it cannot be changed.

  • A red square means there are no legal moves for that entry.
  • The "Show Constrained Squares" option will display those squares which are currently empty, and for which there is only one legal move.
  • The "Show legal moves" option will display the valid moves for a particular square.
  • The "Copy board" button will create a new sudoku board which is a duplicate of the current one.

• PublicTests.java - This class represents the set of JUnit public tests.  These are the same public tests you will find in the submit server.

• StudentTests.java - File where you will put your own test cases.

Requirements

• At the top of your Sudoku.java file add a comment indicating what algorithm you used to determine legal moves.

• Make sure you put your own test cases in the StudentTests.java file.

• The Sudoku class must define and use the following data members:

  • data → two-dimensional array of integers representing the sudoku cell values.  The value 0 will represent an empty (blank) cell.

  • rowData → one-dimensional array of BitSet objects.  Each BitSet object provides information regarding the legal moves that has been completed for a row.

  • columnData → one-dimensional array of BitSet objects.  Each BitSet object provides information regarding the legal moves that has been completed for a column.

  • regions → two-dimensional array of BitSet objects.  Each BitSet object provides information regarding the legal moves that has been completed for each 3 by 3 grid. 

• Immediately after checking out the code distribution, make sure you can submit your project even if you have not implemented the project.  Do not wait until the day the project is due to submit your project for the first time.

• As with all programming assignments:

  • You must use meaningful variable names and good indentation.

  • You must avoid code duplication, by calling appropriate methods (rather than cutting and pasting code). You may define your own private utility methods to perform often repeated tasks.

• Verify that your project passes the submit server tests (https://submit.cs.umd.edu/)

Honor Section Requirements

For those students in cmsc132H, your project should satisfy all the requirements specified above and in addition:

• To get full credit, you need to implement an algorithm  that is smarter than the standard one of just looking to see what values are  prohibited because they occur in the same row, column or square. In  particular, on data/puzzle5.txt, you should be able to determine for the initial board position at least one location that is constrained to have only one possible value.

Submission

Submit your project using the submit project option associated with Eclipse.  Do not wait until the day before the project is due to check whether you can submit your project.

Academic Integrity

Please make sure you read the academic integrity section of the syllabus so you understand what is permissible in our programming projects.  We want to remind you that we check your project against other students' projects and any case of academic dishonesty will be referred to the University's Office of Judicial Programs.

Web Accessibility