title: Optimizing my solution for 1D peg solitaire
body: <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>