This is all in aid of the conclusion others have reached: it's just a big problem. I suspect you won't get much help on this problem - you can't keep a list of visited states (it would take exponential memory), and keeping a list of visited states for the first few levels won't expand the depth to which you can search by that much. Sometimes a solution is to keep track of nodes you've already tried, to reduce redundant search. If it works for a problem of size N, does it work for one of size N+1? Taking a few seconds to solve one of size N suggests that you can forget getting it to solve N+10 (I say, based on experience of a similar problem): not just because it's an exponential problem, but because you may get thrashing as the system tries to get enough memory. I'd conclude then that the problem is that a very large search problem can take a very long time. If make move doesn't do anything, your program won't end, whatever the size of the problem. It is possible that you have an error in some of the functions you didn't show (make move, undo move). This algorithm can't possibly get you stuck in a loop when it recurses, it goes deeper into the search space (that is, it makes a move). So is your algorithm wrong? Here it is, reduced for simplicity: solve (board state) isįor all possible moves from this board state Since every move in peg solitaire removes a peg, you can't possibly be looping back to a previous state: say, as in simple path planning, where a robot could be moving back and forth between two squares forever.
Solvable boards and various unsolvable boards with less pegs seem to consistently terminate within 10 seconds with the correct result. It seems that for random boards with around 25 pegs or more, the program simply won't terminate. My undo method pops the last move off of the array and reverts the board to its previous layout (before the popped move was made). If it can, it makes the move, adds the move to an array of moves, and returns true. It finds the peg at those coords and checks if it can move it in the requested direction. My makeMove function takes in a row, column and direction (i, j and k). I am confident that my isSolved() method correctly determines whether the board is solved. The board is a standard Peg Solitaire board. My recursive method looks like this: public static void solve()
It also seems to correctly determine when a board is not solvable, but only when the number of pegs isn't too high. It seems that my code correctly solves the board for all solvable boards. Matos uses a tree to represent the pegs instead of a graph and gives computation type for implementing this algorithm with different representations of Peg Solitaire. I think I have managed to get a very close to correct solution. Matos goes into detail about using the Depth-First Search to solve the Peg Solitaire problem. The algorithm needs to use the "backtracking" approach to solve the board. I am currently programming a recursive algorithm to solve a game of Peg Solitaire.
0 kommentar(er)
