Table of contents:



Write Vector and Matrix classes consistent with Figure 2-28.

Figure 2-28. UML class diagram of the classes for Exercise 2.30. Since a particular Vector is not associated with a particular Matrix, nor vice versa, there is no arrow connecting the classes.

(This item is displayed on page 63 in the print version)


Implement the game of Reversi (Figure 2-29).

Figure 2-29. The game of Reversi is sold commercially as Othello.

(This item is displayed on pages 63 - 64 in the print version)


Players: 2, black and white.

Object: To have the most pieces of your color on the board at the end of the game.

Board: The board is an 8 x 8 square grid. The initial setup is shown below.

Play: On a turn, a player places one of her pieces on an empty board square. Every line (horizontal, vertical, or diagonal) of the opponent's pieces which is bounded on one end by the just-played piece and on the other end by another friendly piece is captured; all of the captured pieces change color. For example, in the diagram below, a white piece played on the square marked "a" would cause the two black stones marked "b" to become white.

A player must capture if possible. If no capturing move is available, the player must pass, giving the opponent another turn.

Game End: The game is over when neither player has a legal move, usually because the board is full.


Implement the game of Go-Moku (Figure 2-30).

Figure 2-30. The ancient Asian game of Go-Moku.


Players: 2, black and white.

Object: To be the first to get five pieces in a row horizontally, vertically, or diagonally.

Board: The board is a square grid of 19 x 19 lines, initially empty. Pieces are played at the intersections of the lines, rather than in the squares.

Play: On a turn, a player places one of her pieces at any empty intersection.


Implement the game of Mancala (Figure 2-31). (Hint: Use a one-dimensional array of ints to represent the board. Number the pits counterclockwise. When sowing pebbles, if you are currently at pit i, the next pit is at position (i + 1) % 14, although your program must remember to skip this pit if it is the opponent's mancala.)

Figure 2-31. The traditional African game of Mancala.


Players: 2

Object: To have the most pebbles in your mancala (goal) at the end of the game.

Board: The Mancala board consists of 14 pits, each holding a number of pebbles. The starting position is shown below.

Play: On your turn, pick up all of the pebbles in any nonempty pit on your side of the board. Proceeding counterclockwise, sow one pebble in each pit until you run out. When sowing pebbles, include your own mancala, but skip your opponent's. An example of a first move is shown below.

Free Move: If the last pebble you sow lands in your own Mancala, you get to move again.

Capture: If the last pebble you sow lands in a previously empty pit on your side of the board, you move that pebble, as well as any pebbles in the pit directly across the board, into your mancala.

Game End: The game ends when, after either player's move, one player has no pebbles left in any of the six pits on her side of the board. The other player moves all of the pebbles left on his side of the board to his mancala.


The Mancala rules in Figure 2-31 are the Egyptian rules. The Ethiopian rules make two changes: players may choose to sow pebbles either clockwise or counterclockwise around the board, and a move may not start from a pit containing only one pebble.The game ends when one player has no legal move. Modify the program from Project 2.33 to use the Ethiopian rules. (Hint: Remember that the % operator does not behave as modulo when the first operand is negative. This will be a problem if you evaluate (pit - 1) % 14 when pit is 0. You can get around this by first adding 14 to ensure that the first operand to % is positive.)

Part I: Object-Oriented Programming




Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting


Part IV: Trees and Sets



Part V: Advanced Topics

Advanced Linear Structures


Advanced Trees


Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading


Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net