Homework 11

...

: Sudoku Solver

HW 11 Due: Friday 10 16 April 2009 2010 at 119:59:59 pm

HW 12 Due: Friday 17 April 2009 at 11:59:59 pm

Overview

This project is not about Tic-Tac-Toe nor Othello. It uses a 2-person game design as a vehicle to teach:

<ul>

<li>

OO Abstraction

<li>

The OO Design Process

<li>

Fundamental Principles of OOP.

</ul>

In this homework project and the next one (HW 12), you are given a nearly complete 2-person board game framework
and asked to write a few of its components, plug them in and obtain a program that can run Tic-Tac-Toe (HW 11) and Othello (HW 12) with different types of players (human and computer), using a variety of strategies to compute the next move while
playing the games.

The given game framework abstracts and decouples the different components in a game and specifies them in terms of interfaces with only pure abstract behaviors. For example, the rules of a game is abstracted and encapsulated in an interface called IBoardModel . ABoardModel is a specific implementation of this interface using the state pattern. Developing a program for a particular board game is a matter of writing a concrete subclass of ABoardModel and plugging it into the framework. Nothing in the framework is changed!

<hr>

Resources

Othello Game rules:

<a href="http://www.pressmangames.com/instructions/instruct_othello.html" target="_blank">

...

am

The Sudoku Game

Sudoku is a 9*9 grid-based puzzle in which the goal is to place numbers from 1 to 9 in the grid squares taking into account specific constraints. The 9 * 9 puzzle grid can be seen as divided into 9 sub-grids of size 3*3. The 3 main conditions in the classic version of Sudoku state are that each square in the grid contains a number from 1 to 9 and a number cannot be repeated:

• In any line
• In any column
• In any on the 3*3 sub-puzzles

For more information of the game of Sudoku, visit: http://en.wikipedia.org/wiki/Sudoku

A Sudoku puzzle as needed for this assignment may not be well formed and in general may have no solutions or multiple solutions.

The assignment

The purpose of this assignment is to build a Java solver that finds all of the different solutions of the game using a constraint-based approach.

In a constraint-based approach, each square is viewed as a variable that can take on multiple values from a given set. A partial (intermediate) solution is one in which at least one variable has more than one possible value. A final solution is one which each variable has exactly one value (all the sets are singletons).

The required solution (built on the basis of the support code provided) should work as follows. At each step, the program will evaluate a partial solution. Initially, this partial solution corresponds to the input Sudoku puzzle (a 9*9 matrix that is partially filled) in which the values of some squares are known and others are unknown.

To find all solutions for a partial solution, we have to keep track of all the possible values for each square in the grid. (In the support class, the Sudoku grid is modeled by an array of Rows. The Row class contains an ArrayList of HashSets, one HashSet of Integers for each square from that row. The HashSet contains possible values for the square.

To find final solutions from a partial solution, one should look for a square with multiple possible values, generate the different partial solutions by specifying that the square contains one of the values (and impose the restrictions specified by the rules of Sudoku on the content of the other squares), and then recurse for each of these possible solutions until no square has more than one possible value. If square becomes empty, then it will not lead to a final solution. If all squares have exactly one value, then we have a final solution.

The support code provided contains a DrJava project and a few simple Junit tests. Download the code from here.

Your assignment is to implement:

• the method findSolution in the PartialSolution class.
• at least 5 more tests (3 for findSolution, 1 for isDeadEnd, 1 for isFinal).

Extra credit

For extra credit, improve the implementation of setElement and/or findSolution as you see fit, in order to improve the performance of the algorithms by examining fewer PartialSolution's. The improvement will be quantified by seeing if there is a decrease in the count of partial solutions in order to solve a puzzle (the count of partial solutions is returned by the getIntermediateSolutions() function of the PartialSolution class ).

Restriction: Keep using the setElement method in findSolution and do not change the contract of the setElement or findSolution methods.

Submission

Submit via Owlspace a .zip file containing all the files from the support code including those that you modified. Don't forget to add as header to the PartialSolution class, your names and ids

</a>

Web page of an Othello fanatic: [http://www.maths.nott.ac.uk/

<WBR>

othello/othello.html|http://www.maths.nott.ac.uk/othello/othello.html" target="_blank]

<hr>

Download and extract the attached file (=hw11_12.zip=). It contains the following.

<ol>

<li>

doc : a subdirectory containing the documentation in javadoc of all the classes and interfaces in the game framework. Open index.html to view it.

<li>

hw11_12 : a subdirectory containing the following.

<ul>

<li>

src : a subdirectory containing the source code of the framework. Among the source files is GameModel.java which is the class that encapsulates:

<ul>

<li>

the rules of a game,

<li>

the strategies to compute the next move, and

<li>

the management of players.

</ul>

An important piece of code in GameModel.java is stubbed out. You
will be required to complete it.

<li>

games.xml : the DrJava project file for the complete game framework code base.

<li>

P4M2.jar : The binary class files of the complete framework. You are allowed to reverse engineer it to study the design, but not to reverse engineer the code.

<li>

tttboard.jar : The binary class file for the Tic-Tac-Toe game board. It contains the class files for TicTacToeBoard , a class that you will be required to implement (i.e., write the code).

</ul>

</ol>

Your task for this project is to do the following.

<ol>

<li>

Fill out the stubs in the GameModel.java (in the "model" package), i.e. instantiate the IRequestor object. Lab #11 will help you get started on
this part.

</li>

<li>

Implement the Tic-Tac-Toe board model by completing the provided skeleton TicTacToeBoard.java .

<li>

Implement a random move strategy that selects a move from the set of legal (valid) moves only. Hint: take a look at RandomMoveStrategy.java and the stubbed out RandomValidMove.java file.

<li>

Implement the min-max principle.

<li>

Implement the Alpha-Beta pruning strategy.

<li>

Implement Depth-limited search strategy that works for any specified depth. GameModel.java has a method called getPlayers() . In this method, the code to add players playing the strategies described in items 3, 4, 5 in the above is commented out. These strategies must be written in such a way that when this code fragment is uncommented, the whole GameModel.java file
will compile and run properly.

</li>

<li>

Be sure to document (in javadoc style) all the code you write.

</ol>

Use the user ID of one of the team members as the package name for all of the above strategies.

For hints on implementing INextMoveStrategy ,
see the attached hints.html page.

Submission

<font color="#FF0000">

Homework #1

</font>

*

<font color="#FF0000">

1 Requirements:

</font>

*

<ul>

<li>

Do steps 1, 2, 3 of the above task list.

</li>

<li>

Submit via OWLSPACE assignment name: HW11

</li>

</ul>

<font color="#FF0000">

Homework #1

</font>

*

<font color="#FF0000">

2 Requirements:

</font>

*

<ul>

<li>

Do steps 4, 5, 6, 7 of the above task list.

</li>

<li>

Submit via OWLSPACE assignment name: HW12

</li>

</ul>

<hr>

Othello Tournament

During the week of the final, we will hold a tournament to select a new Othello
champion. Participation is totally optional.

P4M2.jar is the binary that will be used for the Othello tournament. To
run the code, enter the following command in Unix or Linux.

<font face="Courier New">

java -classpath .:P4M2.jar:tttboard.jar controller.GameApp

</font>

In Windows, the command is

<font face="Courier New">

java -classpath .;P4M2.jar;tttboard.jar controller.GameApp

</font>

We will announce the tournament rules later. *One key rule is for you
to use your user id as the package name for your best Othello next move strategy*.

<hr>

...

Tips and Traps

In no particular order...

<ul>

<li>

Be sure to properly initialize _val in MinAcc and MaxAcc. What do you want
to happen the very first time that updateBest() is called?

</li>

<li>

When creating an (x,y) Point from a (row, col), which is the row and which
is the col?

</li>

<li>

Be very conscious of what player to use when. The supplied "player" is
not necessarily the one you want! Who knows the proper player for the moment?

</li>

<li>

To calculate a random number between 0 (inclusive) and N (non-inclusive),
use (int)(N*Math.random()).

</li>

<li>

Be sure to redraw the whole board, not just the one token that was placed.
This does not affect Tic-Tac-Toe, but does affect Othello.

</li>

<li>

Should the game halt before or after the view is notified of a win/lose/draw?

</li>

<li>

You should add skip control to your IRequestor. TurnControl can be set
so that setProceed() will skip the next player. Who can figure out whether
or not a player is to be skipped? Which player needs to tested for skipping?

</li>

<li>

How can you calculate (no if's please!) the value with which to update
the accumulator, when you only know which player won and not which player
you are? For instance, suppose player 0 won, but all you know is that you
are "modelPlayer". How can you calculate the proper value {-1, +1} to update
the accumulator with? Consider this: if modelPlayer {{0 then value }} +1, but
if modelPlayer {{ 1 then value }} -1. Can you create a single formula will
properly calculate the value given the modelPlayer and the fact that player 0 has won?

</li>

</ul>

</div>

</body>

</html>

• hw11_12.zip: Files needed to do the homework

...

.