We must be able to specify the possible steps (or moves) that can be made at a given state of the game. In the Solitaire puzzle, for example, a step consists of a move of a piece on the board, according to the game's rules. We know that backtracking applies to problems that can be solved by performing a sequence of steps. the current disposition of the pieces on the board. In our example, the Backtrack class is realized by the Solitaire class, which represents the game board and keeps track of the game state, i.e. Virtual void saveStep( const Step *pc_step, Virtual void undoStep( const Step *pc_step) = 0 Virtual void doStep( const Step *pc_step) = 0 Virtual bool nextStep(Step *p_step) const = 0 To use this class, you have to derive your own class from it and implement the following abstract methods: It was written mainly for teaching purposes in order to take the backtracking logic out of the details of a particular problem. The Backtrack class is an extremely general implementation of the DFS (Depth First Search) backtracking algorithm. The source code comprises of the template class Stack, a simple MFC based typed stack. It also provides an object oriented vestment to backtracking, in the form of a reusable class holding all the backtracking logic. The main purpose of this program is to illustrate the concepts of recursive function, inherently recursive problem and backtracking. The program, in fact, implements a simple backtracking algorithm to search for a solution starting from the current disposition of the pieces on the board. the program can solve the puzzle in your place - or at least it tries to.This program lets you play Solitaire puzzle (also known as Peg Solitaire Puzzle) with two big advantages over a real gaming table:
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |