CODEWITHSUNDEEP
pythonnumpyrecursionbacktrackingn-queens
Quantum James
Quantum James

Reputation: 15

Keep track of how many times a recursive function has been called in Python

I have a piece of Python code that implements a recursive backtracking algorithm for solving the famous N-Queens problem in chess.

def Backtrack(board, col):

  if col >= N:
    return True

  for i in range(N):
      if (ld[i - col + N - 1] != 1 and rd[i + col] != 1) and cl[i] != 1:
          board[i][col] = 1
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 1
          if Backtrack(board, col + 1):
              return True
          board[i][col] = 0 # Backtrack 
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 0

  return False

where

ld = np.zeros(2*N - 1, dtype=int)
rd = np.zeros(2*N - 1, dtype=int)
cl = np.zeros(N, dtype=int)
board = np.zeros((N, N), dtype=int)

The Problem:

I want to keep a track of how many times the recursive backtracking algorithm is called.

My Attempt:

I added a counter variable to the code such that

def Backtrack(board, col, counter):

  counter += 1
  print('here', counter)

  if col >= N:
    return True

  for i in range(N):
      if (ld[i - col + N - 1] != 1 and rd[i + col] != 1) and cl[i] != 1:
          board[i][col] = 1
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 1
          if Backtrack(board, col + 1, counter):
              return True
          board[i][col] = 0 # Backtrack 
          ld[i - col + N - 1] = rd[i + col] = cl[i] = 0

  return False

however for N = 4 the output is

here 1
here 2
here 3
here 3
here 4
here 2
here 3
here 4
here 5

which shows that my attempt is incorrect. The function is called 9 times but at the end the counter variable is 5.

Upvotes: 0

Views: 744

Answers (2)

matszwecja
matszwecja

Reputation: 7970

Dirty hack: Use the fact that default arguments in Python are shared between function calls:

def Backtrack(board, col, counter = [0]):

  counter[0]+=1
  print('here', counter[0])

Proper solution: Contain your method in a class:

class Board():
    counter = 0

    def Backtrack(self, board, col):

        self.counter+=1
        print('here', self.counter)

later called like so:

Board().Backtrack(board, 0)

Upvotes: 0

Reti43
Reti43

Reputation: 9796

Integers are immutable, so when you do counter += 1, you create a new number, say from 1 to 2, and 2 is now bound to the name counter. So when you're at depth 2 and call the function twice, both calls will increment 2 to their own 3. In python you don't pass by variable, but by name, so that counter isn't referring to the same thing throughout all the calls.

What you want is either a mutable or global variable. For example

# or a class implementation equivalent
counter = 0
def backtrack(board, col):
    global counter
    counter += 1
    # the rest

But that way you'd need to reset counter to 0 every time you want to restart the algorithm. Therefore, I think it's better to do

def backtrack(board, col, counter=None):
    if not counter:
        counter = [0]
    counter[0] += 1
    # the rest of your function

Be very careful of doing backtrack(board, col, counter=[0]), because counter will be initialised to the list only once. After you've solved, for say N=4, it will have the value 9 and if you call the function again, it will keep incrementing from there.

Upvotes: 1

Related Questions