I was looking at Norvig’s Sudoku solver the other day, and suddenly understood a design choice that had previously struck me as bizarre. I think it’s a neat example of how small, seemingly arbitrary things can make your programming either easier or harder, depending on whether or not you get them right.
Why?
If you check Norvig’s code, you’ll see that he tracks his partial solutions in dictionaries, usually called values, which map strings (such as A3, B3, or E2) to strings (such as 1234, 2349, or 134789). The first strings represent cell labels, and the second represent sets of possible values for each cell. The obvious question is: “Why use strings to store the sets of possible values?” Strings aren’t a natural fit for this purpose, and, indeed, they (seemingly unnecessarily) preclude the use of the solver for puzzle sizes greater than 9×9 with integer symbols.
The Answer
Without getting into speculation about Python’s internal handling of strings vs. lists, I think the answer is in the search function:
def search(values):
"Using depth-first search and propagation, try all possible values."
if values is False:
return False ## Failed earlier
if all(len(values[s]) == 1 for s in squares):
return values ## Solved!
## Chose the unfilled square s with the fewest possibilities
_,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
return some(search(assign(values.copy(), s, d))
for d in values[s])This code makes a copy of the partial solution (stored in values), and dict.copy() only makes a shallow copy. If values mapped strings to e.g., lists, this copying code would be more complex and awkward.
Strings wouldn’t have been my first choice in this case, but, upon reflection, they have much to recommend them. I suppose this is why it’s educational to read other people’s code.
Edit: I find that Norvig actually covers this point explicitly in his article, and feel rather foolish for overlooking/forgetting that fact. I suppose it’s educational to pay attention to other people’s comments, too.
