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.

Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140
behindthefall
  • 1,485
  • 1
  • 17
  • 18

3 Answers3

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;-).

Alex Martelli
  • 854,459
  • 170
  • 1,222
  • 1,395
  • 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 Nov 16 '09 at 00:58
  • @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;-). – Alex Martelli Nov 16 '09 at 01:33
  • 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 Nov 16 '09 at 01:44
  • @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! – Alex Martelli Nov 16 '09 at 01:56
  • Will the compiler recognize that '_' is thrown away and not actually assigning it (saving performance)? – Viktor Mellgren Jul 03 '12 at 08:15
  • @Vixen no; `_` is a valid variable name which you can use, so it will be treated like any other variable. – congusbongus Jun 05 '14 at 07:12
  • The approach using `key=` may not be the best when the supplied function is expensive to evaluate; I hope it is not the case with `len`. – musiphil Jan 22 '15 at 19:20
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.

mikej
  • 65,295
  • 17
  • 152
  • 131
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.

Stephan202
  • 59,965
  • 13
  • 127
  • 133
  • 1
    Ah, very useful. Of course, doctests run in "interactive" mode: and tromp all over _ when you're trying to use it for i18n... – Auspex Oct 07 '14 at 22:34