<p>This algorithm for doing the solitaire is covered in this research paper: <a href="https://arxiv.org/pdf/math/0006067.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/math/0006067.pdf</a>.</p>
<p>It claims that a linear time algorithm exists.</p>
<hr />
<p>A valid solution looks like this:</p>
<blockquote>
<pre class="lang-py prettyprint-override"><code>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)
</code></pre>
</blockquote>
<hr />
<p>To solve A, you can use regex to check for the string. However, there are multiple cases of it due to the middle section.</p>
<p>First case: <code>11(01)*00(10)*11</code><br />
Second case: <code>11(01)*(00)(11)+(10)*11</code><br />
Third case: <code>11(01)*(11)+(00)(10)*11</code><br />
Fourth case: <code>11(01)*(11)*(1011)(10)*11</code><br />
Fifth case: <code>11(01)*1101(11)*(10)*11</code></p>
<hr />
<p>To solve B and C is a simpler regex match:</p>
<p>Solution for B: <code>11(01)*(11)*01</code><br />
Solution for C: <code>10(11)*(10)*11</code></p>
<hr />
<p>If you match (you will need to convert it to a string though, such as <code>''.join([str(i) for i in mylist])</code> for example) <code>1</code>, <code>011</code>, <code>110</code>, or any of the patterns above, then it will be solvable.</p>
Optimizing my solution for 1D peg solitaire
<p>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 <code>[1, 1, 0, 1, 1, 1]</code> where 1s represent pegs and 0s represent holes for <code>n = 6</code></p>
<p>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 <code>[0, 0, 0, 1, 0, 0]</code> for <code>n = 6</code></p>
<p>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.</p>
<p>So for a board such as <code>board = [0, 1, 1, 0, 1, 1, 0]</code> there are two available moves.</p>
<ol>
<li>move <code>board[1]</code> to <code>board[3]</code> and set <code>board[2] = 0</code></li>
<li>move <code>board[5]</code> to <code>board[3]</code> and set <code>board[4] = 0</code></li>
<li>move <code>board[2]</code> to <code>board[0]</code> and set <code>board[1] = 0</code></li>
<li>move <code>board[4]</code> to <code>board[6]</code> and set <code>board[5] = 0</code></li>
</ol>
<p>The goal of the algorithm I am trying to make is to take an input of n where n &gt; 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.</p>
<p>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 &gt; 20. So I was wondering if there are some optimizations I could do or different solution approaches.</p>
<p>Here is my code:</p>
<pre><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 &lt; len(board)-2:
            if board[i] and board[i+1] and not board[i+2]:
                moves.append((i, 'right'))
        if i &gt; 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)))
</code></pre>
<p>Optimizations I have come up with so far:</p>
<ol>
<li>A board containing <code>[1, 0, 0, ..., 0, 1]</code> is unsolvable. So when we find this patters we skip</li>
<li>Same thing for a board containing <code>[0, 0, .. 0, 1, 0, 0, ..,0]</code></li>
<li>We only need to check half of the board, as the solutions of the other half would be symmetrical.</li>
</ol>
<p>But despite these the code is still very slow.</p>