title: Algorithm for recursively solving the grid
body: <p>I need some help to find an algorithm that will solve the following problem.</p>
  <p>Given the 2d board and target values for rows/columns, the sum of rows/columns should be equal to these target values. It can be achieved by setting a board value to 0.</p>
  <p>In my case I have the following board:</p>
  <pre class="lang-py prettyprint-override"><code>board = [
      [5,9,4,6,1],
      [6,2,3,6,7],
      [3,4,8,4,4],
      [2,2,6,4,6],
      [7,3,1,6,5]
  ]
  </code></pre>
  <p>With the following values for rows <code>[24,13,15,8,12]</code>, and the following values for columns <code>[8,11,13,18,22]</code>.</p>
  <p>As a result, the board should look like this:</p>
  <pre class="lang-py prettyprint-override"><code>board = [
      [5,9,4,6,0],
      [0,0,0,6,7],
      [3,0,8,0,4],
      [0,2,0,0,6],
      [0,0,1,6,5]
  ]
  </code></pre>
  <p>For now, my code looks like this:</p>
  <pre class="lang-py prettyprint-override"><code># chooses a next cell 
  def choose_cell(x,y,visited):
      for i in range(x,board_len):
          for j in range(y, board_len):
              if visited[i][j] == 0 and is_cell_valid(i,j):# if the cell is not visited and is valid =&gt; return i,j
                  return i,j
  
      for i in range(0,board_len):
          for j in range(0, board_len):
              if visited[i][j] == 0 and is_cell_valid(i,j):
                  return i,j
      return -1,-1
  
  # checks if x,y are not out of board range
  def is_cell_valid(x_coord, y_coord):
      if (x_coord &lt; 0 or y_coord &lt; 0) or (x_coord &gt;= board_len or y_coord &gt;= board_len):
          return False
      return True
  
  def solve_board(x, y, visited):
      # if the sum of the row/column equals target row/column value =&gt; returns True
      if row_sum() == row_goal and col_sum() == col_goal:
          return True
  
      if x == -1:# if -1 is returned it means that the algorithm reached the end of a board
          return False
  
      x,y=choose_cell(x,y, visited)
  
      # mark the current board element as visited
      visited[x][y] = 1
  
      # save current board element for future use, put 0 in the board instead
      temp = board[x][y]
      board[x][y] = 0
  
      # that's where my mind goes blank
      if solve_board(x,y,visited) == False:
          board[x][y] = temp    
      if solve_board(x,y,visited):
          return True
      
      return False
  </code></pre>
  <p>I tried to implement the following here:</p>
  <ol>
  <li>Select a cell.</li>
  <li>Set the value to zero.</li>
  <li>Go recursively and try to solve the board.
  <ul>
  <li>If the board is not solved, then backtrack and set the board element to the previous value. Go recursively and try to solve the board for that value.</li>
  <li>If the board is solved, return True.</li>
  </ul>
  </li>
  </ol>