CODEWITHSUNDEEP
python
orpqK
orpqK

Reputation: 2795

Using recursive function but what is my termination?

I am trying to figure out how to terminate my recursive function. As you can see in this picture below:

enter image description here

getEmpty[9] will return:

[6,10]

But I need it to return [6,8,9,10,11]

Because I want all the empties as long as it shares an edge with a previous empty box.

How to I terminate this recursion?

Currently I have 

getEmpty(9)
        #my code here
        return empties;


empties = [6,10]

I added this:

for cell in empties:

        if(getEmpty(cell) not in empties):
            empties = empties+getEmpty(cell)

at the end, but it gives me an infinite loop that prints out:

[6,10]
[9]

non stop, how do I fix this?

Upvotes: 0

Views: 73

Answers (2)

thkang
thkang

Reputation: 11543

edit : sorry your question was very ambiguous. What you need is a simple graph traversal algorithm. here is a glimpse of it:

input : coordinate of a cell

function empty_cell_search(cell)
  for neighbor_cell in neighbors :
    if the_neighbor_cell is empty and is not already visited : 
      add the_neighbor_cell to set of visited cells
      union empty_cell_search(the_neighbor_cell) with current set of visited cells
  return the set of currently visited cells

Upvotes: 4

Groditz
Groditz

Reputation: 115

You should use this (python 3, but same idea for 2):

empty=[6,8,9,10,11]
start=9
done=[int(start)]
while True:
    complete=True
    for num0 in empty:
        for num1 in done:
            if (abs(num0-num1)==1 or abs(num1-num0)==3) and num0 not in done:
                complete=False
                done.append(num0)
    if complete=True:
         break
print(sorted(done))

Upvotes: 1

Related Questions