In my mind, Python's most important data structures are its set, tuple, dictionary, and list. While they are no more powerful than what you can find or make in

In my mind, Python's most important data structures are its set, tuple, dictionary, and list. While they are no more powerful than what you can find or make in Java, they are extremely convenient to use. Note that Norvig solves both problems exclusively using these structures. Norvig's sudoku solver is using depth-first search and backtracking, implemented in the function "search". I'm not sure where you are getting the idea that it is simultaneously using many more boards than the search depth. Google could well be using every clever trick you can think of to implement their spelling corrector, but I think you're overestimating the value of tracking user variations over multiple searches. It's highly unlikely that someone searched for "Pauel Garahum" in the past, then corrected it to "Paul Graham". Likewise, you can search for "brootnenny spars" and it comes up with a good suggestion. More likely, they are using the search frequency as an indicator of correctness (P(c) in Norvig's article) and coming up with a better error model (P(w|c)), probably using phonetics as you proposed earlier. And once you have this, you don't really need to go through the effort of correlating search variations. It is, however, well-known that Google tracks the links that people click on and uses this information to improve search rankings. They may well be tracking whether or not the user clicks on results and using this fact to improve their estimate of the correctness of the search. ...And I'm not sure if you know this, but the reason Norvig specifically mentions Google's spelling correction is because he is Google's Director of Research. He didn't "not realize" that Google could be using search results to improve spelling correction; he intentionally left stuff out because the article is only supposed to be an introduction to spelling correction.