![]() We only need to check half of the board, as the solutions of the other half would be symmetrical.īut despite these the code is still very slow.Optimizations I have come up with so far: If re.search(expression1, string) or re.search(expression2, string): Wrote the code in three different languages, Java, Python as well as in C++ - one of the requirement of project. Used Backtracking for achieving the final goal of puzzle i.e. If board and board and not board:Įxpression1 = '1000+1' #RE for a proven to be unsolvable boardĮxpression2 = '00100' #RE for a proven to be unsolvable board Peg Solitaire puzzle/game Solver AI a program which can solve the peg-Solitaire game by itself, basically designed an AI for Peg-Solitaire game. So I was wondering if there are some optimizations I could do or different solution approaches. I have created a brute force algorithm which finds all the possible moves until a valid solution is reached, but it starts taking a very long time to find a solution past n > 20. The goal of the algorithm I am trying to make is to take an input of n where n > 2 and n is an even number, then for a board of length n, find all the positions for a start state at which a hole can be placed to produce a valid solution. Everything is done except for the solve () function where the actual back tracking part is contained, this is proving conceptually really difficult for me. My program takes in a txt file that contains a starting board. So for a board such as board = there are two available moves. Im currently trying to write a program that will be able to find the solutions for the game peg solitaire using back tracking. Your available moves at any given position is to move one peg by two positions to the right or to the left if and only if there is a peg between the two position, then once you make that move, replace the middle peg with a hole. The goal of the game is to reach a board state where n-1 elements are holes and 1 element is a peg at any given position. So a starting position can be where 1s represent pegs and 0s represent holes for n = 6 n-1 elements are pegs (filled) and 1 element is a hole (empty). You initially start with a 1 dimensional board of length n. First I will explain the rules of peg solitaire (for 1 dimension):
0 Comments
Leave a Reply. |