My function returns wrong values when called. First, iteration returns correct value but then if I call a new function. Why is it returning non-empty lists?
I ran the below code in my shell. The second last call should return an empty list but it returns the value return in the call before that.
>>> from solvers.algorithms.dancing_links import solve
>>> solve({}, {})
[]
>>> solve(ctor, rtoc)
['B', 'D', 'F']
>>> solve(ctor, rtoc)
['B', 'D', 'F']
>>> solve({}, {})
['B', 'D', 'F']
This is my python code.
# Solves the Sudoku using dancing links algorithm using implementation from:
# https://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html
def solve(columns_to_rows, rows_to_columns, solution=[]):
"""
This function solves the exact cover problem, i.e., given a matrix A in which each element is 0 or 1.
Is there a subset of rows which have exactly one 1 in each column?
The exact cover problem can also be stated as following,
"Given a set X and a set of subsets of X called Y, is there a subset of Y such that all of its elements
are disjoint and union of its elements is X."
:param columns_to_rows: It is a dictionary where value of key `i` is the set of columns in which ith row is 1.
:param rows_to_columns: It is a dictionary where value of key `i` is the set of rows in which ith column is 1.
:param solution: Currently selected rows
:return:
"""
if not columns_to_rows:
return list(solution)
else:
# Column with minimum 1's in it.
selected_column = min(columns_to_rows, key=lambda col: columns_to_rows[col])
# For each row which has a 1 in the `selected_column`.
for selected_row in columns_to_rows[selected_column]:
solution.append(selected_row)
# Select and remove all columns which have 1's in the `selected_row`
# Also remove all the rows which have 1's in the same column as the `selected_row`
removed_columns = select_and_remove(columns_to_rows, rows_to_columns, selected_row)
tmp = solve(columns_to_rows, rows_to_columns, solution)
if tmp is not None:
return tmp
deselect_and_insert(columns_to_rows, rows_to_columns, selected_row, removed_columns)
solution.pop()
Edit 1: I added a print statement to print the "solution" variable and I found this.
>>> from solvers.algorithms.dancing_links import solve>>> solve({}, {})
[]
[]
>>> solve({}, {})
[]
[]
>>> solve(ctor, rtoc)
[]
['A']
['B']
['B', 'D']
['B', 'D', 'F']
['B', 'D', 'F']
>>> solve({}, {})
['B', 'D', 'F']
['B', 'D', 'F']
>>>
So the first time I call the function it returns empty list and solution is also empty. Then when I call the function second time with actual parameters it works as expected and goes into a recursive call. But the third time the solution variable is already set to the previous value but it should be empty. Why is it happening? And how to fix it?
