The classic phone book

The classic example I use to explain data structures and running orders is getting a number from a phone book. For those who have never seen a phone book, it's just a, fairly big, collection of names in alphabetical order together with the phone number of that person.

A phone book is essentially a lookup from a name (key) to a phone number (value.) A very common operation in software. In many cases, software will just linearly iterate over the records until the key is hit to return the matching value. In Linq in C#:

records.First(r => r.Name == name).Phone

This is what I would call a sub-human approach. No human has ever looked through a phone book linearly from the start until coming across the target name. Even though the computer might still be faster using this approach, the approach itself is less efficient.

The human way to find a name in a phone book relies on the fact that the names are ordered. You'd open the phone book in some location to determine whether the target name is in front or behind that location. This reduces the relevant part of the phone book and you can continue doing this until you've found the correct location of the target name. This comes down to a binary search and this would be on par with the human approach.

Using a hash table is an even better approach for this problem and allows the time needed for the lookup to be independent from the size of the phone book. It's quite rare to have an algorithm with a running time that is not related to the size of the input.

Both indexing options (binary tree or hash) are very common in databases and are also generally available in programming languages. It's just a matter of realizing that it would be beneficial to use it. Again, even iterating linearly over a dataset the size of a typical phone book can be done with a computer quite fast.

So, back to running orders. The linear iterations option is denoted O(N), meaning that the time doubles every time the phone book doubles in size. The binary search is denoted O(log N), meaning that the time increments by the same amount every time the phone book doubles in size. The hash table option is O(1), meaning that time stays the same every time the phone book doubles in size.

Quite a difference, but I mainly find it interesting that the typical human behavior gravitates to the middle option, while it's quite common to gravitate to the slower option when implemented in software. Even though an even faster option is readily available.

Of course, for very thin phone books, the difference might be neglectable and then its easy to favor the cleaner notation of a linear search. And it takes time to create the data structure, so it's only useful when used often enough.

Introduction

Recently I've been working on a little logic solver hobby project. The idea is to apply generic* solvers on various problems like Sudoku or Kakuro puzzles, or the N-Queens problem.

While being generic, these solvers do use heuristics to arrive at a solution in a timely manner. These heuristics align with the way a human would solve for example a Sudoku puzzle. And there you have it, I want to dedicate this blog to explaining how these Human Heuristics can be applied to computer programs.

While looking for example puzzles in a computer friendly format, I've come across sources where a computer program would take more than 10 minutes to solve a Sudoku or Kakuro. The algorithms there don't incorporate these Human Heuristics, making them orders of magnitude slower. For reference, the same problems can easily be solved by a computer in less than 10 milliseconds.

And that's really the reason why I want to explain the use of Human Heuristics in computer programs. Because computers are so fast, they are often fast enough even when the problem is solved in a simple way. But the human equivalent to a computer program solving a Sudoku in 10 minutes, is just checking whether the sudoku is correct after trying every number for every location and taking years to solve a single Sudoku.

I hope to inspire other programmers with the way heuristics in computer programs align with the heuristics we use as humans. So when solving a problem, stop thinking about how you would solve the problem with a computer, but instead focus on translating the way you solve the problem as a human into a computer program.

*While you could of course make a solver specifically for a 9 by 9 Sudoku, my hobby project aims at using the same solver(s) for multiple problems. So not just Sudoku puzzles of any size, but also the N-Queens problem can be solved with exactly the same solver.