First I will explain the rules of peg solitaire (for 1 dimension): you initially start with a 1 dimensional board of length n. n-1 elements are pegs (filled) and 1 element is a hole (empty). So a starting position can be [1, 1, 0, 1, 1, 1] where 1s represent pegs and 0s represent holes for n = 6

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 valid solution can be [0, 0, 0, 1, 0, 0] for n = 6

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.

So for a board such as board = [0, 1, 1, 0, 1, 1, 0] there are two available moves.

1. move board[1] to board[3] and set board[2] = 0
2. move board[5] to board[3] and set board[4] = 0
3. move board[2] to board[0] and set board[1] = 0
4. move board[4] to board[6] and set board[5] = 0

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.

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. So I was wondering if there are some optimizations I could do or different solution approaches.

Here is my code:

import re

def generateBoard(n):
    return [1]*n

def solve(board):
    if checkBoard(board):
        return True
    elif checkUnsolvable(board):
        return False

    moves = []
    for i in range(len(board)):
        if i < len(board)-2:
            if board[i] and board[i 1] and not board[i 2]:
                moves.append((i, 'right'))
        if i > 1:
            if board[i] and board[i-1] and not board[i-2]:
                moves.append((i, 'left'))
    
    for move in moves:
        newBoard = makeMove(board, move)
        if solve(newBoard):
            return True
        continue

    return False


def makeMove(board, move):
    index, direction = move
    b = [element for element in board]
    if direction == 'right':
        b[index] = 0
        b[index 1] = 0
        b[index 2] = 1
    elif direction == 'left':
        b[index] = 0
        b[index-1] = 0
        b[index-2] = 1
    return b

def checkBoard(board):
    if sum(board) == 1:
        return True
    return False

def checkUnsolvable(board):
    expression1 = '1000 1' #RE for a proven to be unsolvable board
    expression2 = '00100'  #RE for a proven to be unsolvable board
    string = ''.join([str(element) for element in board])
    if re.search(expression1, string) or re.search(expression2, string):
        return True
    return False

def countSolutions(board):
    indices = []
    for i in range(len(board)):
        b = [element for element in board]
        b[i] = 0
        if solve(b):
            indices.append(i 1)
    return indices


n = int(input())
print(countSolutions(generateBoard(n)))

Optimizations I have come up with so far:

1. A board containing [1, 0, 0, ..., 0, 1] is unsolvable. So when we find this patters we skip
2. Same thing for a board containing [0, 0, .. 0, 1, 0, 0, ..,0]
3. We only need to check half of the board, as the solutions of the other half would be symmetrical.

But despite these the code is still very slow.

CodePudding user response：

This algorithm for doing the solitaire is covered in this research paper: https://arxiv.org/pdf/math/0006067.pdf.

It claims that a linear time algorithm exists.

A valid solution looks like this:

L = 1
 or 011
 or 110
 or 11 (01)* [ 00 | 00(11)  | (11) 00 | (11)*1011 | 1101(11)* ] (10)*11  # (A)
 or 11 (01)* (11)* 01  # (B)
 or 10 (11)* (10)* 11  # (C)

To solve A, you can use regex to check for the string. However, there are multiple cases of it due to the middle section.

First case: 11(01)*00(10)*11
Second case: 11(01)*(00)(11) (10)*11
Third case: 11(01)*(11) (00)(10)*11
Fourth case: 11(01)*(11)*(1011)(10)*11
Fifth case: 11(01)*1101(11)*(10)*11

To solve B and C is a simpler regex match:

Solution for B: 11(01)*(11)*01
Solution for C: 10(11)*(10)*11

If you match (you will need to convert it to a string though, such as ''.join([str(i) for i in mylist]) for example) 1, 011, 110, or any of the patterns above, then it will be solvable.