This project consists of writing three programs, one in C++, one in Java, and on

Question

This project consists of writing three programs, one in C++, one in Java, and one in Python. All programs will implement solutions of a puzzle using recursive search. The puzzle is known by several names, one of which is Hi Q. The puzzle consists of a game board with a set of holes and a set of pegs placed in the holes. There are several variations in the shape of the board. For this problem, we will use the triangular version. The board is illustrated below: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 The shaded circles represent holes with pegs and the unshaded circle is a hole without a peg. Moves are made by jumping pegs over other pegs. Using the hole numbering scheme illustrated above,, we can describe moves as triples of numbers (from, over, into) so that (0, 2, 5) means remove the peg from hole, jump over hole 2 and into hole 5. The peg that was jumped over, in hole 2, is removed. The starting configuration of the puzzle has one empty hole, all the other holes have pegs. The from, over and into holes must be next to each other in a straight line, horizontally or diagonally. In the starting configuration diagrammed above, the legal moves are: (0, 2, 5) (14, 9, 5) (3, 4, 5) (12, 8, 5) There are various ways to represent this puzzle in a program. One simple way is to just use a one dimensional array, and list all possible moves as a list of (from, over, into) triples. For a possible move o be legal, the from and over holes must contain pegs, and the into hole must be empty. Moves are made until no more moves are possible. The goal of the puzzle is to leave the fewest number of pegs when the moves run out. The best case is to be left with only one peg. Your programs should allow the user to specify which hole to leave empty at the start, and the maximum number of pegs that can be left at the end to be an acceptable solution. then find and print a a solution that leaves that number of pegs. After printing a solution, allow the user the option of asking for a better solution. If the use asks for a better solution, only print a solution if it contains less pegs left than the last solution, or if it has only one peg left. Solutions can be printed as a list of from, over and into hole numbers.

Explanation / Answer

Move.java

public class Move {

private Position start;

private Position jump;

private Position end;

public Move(Position start, Position jump, Position end) {

this.start = start;

this.jump = jump;

this.end = end;

}

public Position getStart() { return start; }

public Position getJump() { return jump; }

public Position getEnd() { return end; }

public String toString() {

StringBuffer sb = new StringBuffer();

sb.append("{"+start);

sb.append(","+jump);

sb.append(","+end+ "}");

return sb.toString();

}

public List<GameBoard> possibleBoards() {

List<GameBoard> boards = new ArrayList<GameBoard>();

for (int i = 0; i < 5; ++i)

for (int j = 0; j <= i; ++j) {

Position start = new Position(i,j);

List<Move> possibleMoves = Moves.getMoves(start);

for (Move move : possibleMoves) {

if (validMove(move))

boards.add(jump(move));

}

           }

   return boards;

}

}

GameTree.java

import java.util.List;

import java.util.ArrayList;

import board.*;

public class GameTree {

GameTree level;

GameBoard gb;

List<GameTree> children = new ArrayList<GameTree>();

public GameTree(GameBoard gb) {

this.gb = gb;

}

public void addChild(GameTree child) {

children.add(child);

}

public GameBoard getGameBoard() { return gb; }

public boolean hasChildren() {

return children.size() > 0;

}

public GameTree getFirstChild() {

return children.get(0);

}

public void removeFirstChild() {

children.remove(0);

}

public int numChildren() {

return children.size();

}

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.