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.
#PEG SOLITAIRE ASP PLANNING SOLUTION CODE#
It seems that my code correctly solves the board for all solvable boards. I think I have managed to get a very close to correct solution. 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)
