Recursion help - Peter Norvig's Sudoku exercise

Question

Hi I am currently going through Peter Norvig's sudoku solution (http://norvig.com/sudoku.html).

However, I have a bit of confusion with the block code below:

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
    return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
    dplaces = [s for s in u if d in values[s]]
    if len(dplaces) == 0:
        return False ## Contradiction: no place for this value
    elif len(dplaces) == 1:
        # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

The function assign receive an input of a dictionary values and will return values as well if there is no contradiction. However, in the assign function, I did not see any update on the dictionary values. My understanding is that dict values is updated with the eliminate function (and after running the code, I believe this is the case). However, this is done outside of the assign function and should not affect the values in the assign function, as it is not updated directly in the function.

Maybe you guys can give me a shed of light?

Answer 1

Python dicts are mutable, meaning that their value can be changed.

This example is showing an anti-pattern: You shouldn't both mutate an argument and return it. An example is all the methods that change a list (append, pop, etc.) don't return the original list.

The eliminate function gets the same dict as in the assign function, and any changes in the assign function are reflected in the elimate function.

Here is an example:

def update(dict_, key, value):
    dict_[key] = value

d = {
    1: 2,
    3: 4
}
update(d, 1, 100)
update(d, 3, 100)

print(d[1] + d[3])  # 200