73

Peter Norvig has an essay describing a program to solve sudoku puzzles, even the hardest ones, by combining deterministic logical operations and smart traversal of the possible solutions. The latter is done recursively; here's that function (source):

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]
            )

(I've added some spaces, CRs, and tabs for the sake of my eyes; apologies to Dr. Norvig.)

Right below the comment there's a line starting with "_,s". That seems to be the unpacked tuple (len(values[s]),s) with the minimal value of s. Is Dr. Norvig using "_" as a variable name just to indicate it's a "don't care" result, or is something else going on? Are there times when "_" is recommended as a variable name? In interactive mode, "_" holds the answer of the previous operation; is there a similar function in non-interactive code?

Update

Thanks for the good answers. I guess The Answer goes to Alex Martelli for "value added"; he points out that the "_, vbl_of_interest" idiom is often a side effect of the DSU idiom, which itself has been made largely unnecessary.

Improve this question
3
  • Another very popular solution nowadays is to get rid of the _ and just put [1] after the method call to project out the wished results. Commented May 20, 2014 at 8:25
  • Looks like Norvig has updated his code from '_,s' to 'n,s' Commented Jun 20, 2020 at 19:24
  • Inspired by this question, I created a youtube tutorial on unused variables in list comps youtube.com/watch?v=cZb5aFcpsAs Commented Jan 7, 2021 at 3:17

3 Answers 3

Reset to default
76

Yep, _ is a traditional name for "don't care" (which unfortunately clashes with its use in I18N, but that's a separate issue;-). BTW, in today's Python, instead of:

_, s = min(
    (len(values[s]), s)
    for s in squares
    if len(values[s]) > 1
)

you might code

s = min(
    (s for s in squares if len(values[s]) > 1),
    key=lambda s: len(values[s]),
)

(not sure what release of Python Peter was writing for, but the idiom he's using is an example of "decorate-sort-undecorate" [[DSU]] except with min instead of sort, and in today's Python the key= optional parameter is generally the best way to do DSU;-).

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Hi, Alex. I was wondering about that, but I hadn't put it into the right concept --- and might not have, without your comment. BTW, my sudoku solver I wrote 4 years ago did a lot of DSU-ing, so you are pointing out places where I ought to update the coding. (Not to mention that I'm still trying to understand how the thing works!!) Typically, my code sets up its own explicit stack, rather than going recursive.
@behindthefall, controlling your own stack is just fine, though recursion's simpler -- there are specific techniques for recursion removal (not really germane to this question, but, do ask another)!. The one major case where manual DSU is still needed in today's Python, in my experience, is priority queues (heapq's function don't accept key= -- neither do bisect's, but that's not quite as common a use case for me as priority queues;-).
I'm trying to put recursion IN so that I can remove it when I wish --- my head hasn't learned how to do stuff with recursion that it wouldn't rather do with a loop. There's a load of code in my sudoku solver that this "simple" recursive def makes all go away! Dr. Norvig chose to use string ops rather than set ops in his solver; ironically, I used string ops to solve a few tiling puzzles before I tackled sudoku, so I used lists 'n' sets for sudoku just for the experience.
@behindthefall, yes, starting with recursion is generally best (simplest). Not sure what to suggest to help "getting" recursion, maybe a language-agnostic question would elicit responses from other people more experienced than me in such "teaching" issues!
Will the compiler recognize that '_' is thrown away and not actually assigning it (saving performance)?
|
13

Your interpretation is correct. Outside of the special meaning in interactive mode _ is just used as a "don't care" variable name, especially in unpacking.

Improve this answer

Comments

9

You are correct. In non-interactive mode _ has no special meaning. Indeed, Norvig just wants to convey that he doesn't care about the value of that variable.

Offtopic: That article by Norvig is very nice. A recommended read.

Improve this answer

1 Comment

Ah, very useful. Of course, doctests run in "interactive" mode: and tromp all over _ when you're trying to use it for i18n...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.