BEST代写-线上编程学术专家

Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

C++代写 | CS 280 Programming Project 1

C++代写 | CS 280 Programming Project 1

这个作业是使用C++递归搜索实现难题HiQ

CS 280 Programming Project 1
This project consists of writing two programs, one in C++ and one in Java. Both
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:
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 diagonaly. In the starting configuration
diagramed 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 te 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.
0
1 2
3 4 5
6 7 8 9
10 11 12 13 14
Recursive Search:
The technique of recursive search can be desribed in pseudocode as a recursive
function:
findSolutions()
if(current state is a goal) // base case
output a solution
ask the user if they want to look for more solutions
if(no) return
for all possible legal moves m in the current state
make move m
findSolutions() // recursive call
undo move m
The word “state” refers to the state of the puzzle. In terms of your program, this
means the values of all the class data members that represent the puzzle. If you
represent the puzzle as an array, the state includes that array. You may also want
to keep track of some other information. For example, it would probably be a
good idea to have a data member that keeps track of how many pegs are left. this
data member is also part of the state. It is important to remember that making a
move, or undoing a move means updating all data members that have changed
as a result of the move. You also need to keep track of how many pegs were left
in the last solution, so if the user asks for a better solution you know how low a
peg count you need to be at a goal.
For some types of puzzles, the solution is the configuration of the puzzle when a
goal is achieved. In othe puzzles (like this one), the solution is a sequence of
moves that gets from the start configuration to the goal configuration. So you
must keep track not only of the configuration of the puzzle, but the sequence of
moves that got you from the start configuration to the current configuration.
Note that if you think of the sequence of moves as a stack, then if when you make
move m you also push move m, and when you undo move m you pop the stack,
the stack will always contain the sequence of moves that lead from the start
configuration to the current configuration.
This problem exhibits a type of symmetry known as a duality, a sort of mirror
image problem. I leave it to you to find this. Here’s a hint. If I give you a solution
that starts with hole x empty and ends with one peg in hole y, how can you use
that solution to find a solution that starts with hole y empty and ends with one
peg in hole x?
Extra Credit:
Create a graphical animation that displays solutions to the puzzle. I will post a zip
file that contains a Java program that animates a different puzzle. The program
implements a graphical animation for a sliding piece puzzle, but it contains all the
elements you need to create a similar animation for the Hi Q puzzle. The nicest
solution would display the program in a JFrame with a JPanel containing the puzzle
animation and with other components on the JFrame (such as JButtons or
JTextFields) to interact with the user, but it will be sufficient to let the user
interact with the program through the console and just display the animated
solution graphically.

bestdaixie