![]() ![]() 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): The program, in fact, implements a simple backtracking algorithm to search for a solution starting from the current disposition. 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 This program lets you play Solitaire puzzle (also known as Peg Solitaire Puzzle) with two big advantages over a real gaming table: the program can solve the puzzle in your place - or at least it tries to. 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. So for a board such as board = there are two available moves. 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. Peg solitaire (or Solo Noble) is a board game for one player involving movement of pegs on a board with holes. 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. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |