# Taking A Crack At The Traveling Salesman Problem

The human mind is a path-planning wizard. Think back to pre-lockdown days when we all ran multiple errands back to back across town. There was always a mental dance in the back of your head to make sense of how you planned the day. It might go something like “first to the bank, then to drop off the dry-cleaning. Since the post office is on the way to the grocery store, I’ll pop by and send that box that’s been sitting in the trunk for a week.”

This sort of mental gymnastics doesn’t come naturally to machines — it’s actually a famous problem in computer science known as the traveling salesman problem. While it is classified in the industry as an NP-hard problem in combinatorial optimization, a more succinct and understandable definition would be: given a list of destinations, what’s the best round-trip route that visits every location?

This summer brought news that the 44-year old record for solving the problem has been broken. Let’s take a look at why this is a hard problem, and how the research team from the University of Washington took a different approach to achieve the speed up.

# Arduino And Wire Detects Metal

Our old math teacher famously said, “You have to take what you know and use it find what you don’t know.” The same holds true for a lot of microcontroller designs including [rgco’s] clever metal detector that uses very little other than an Arduino. The principle of operation is simple. An Arduino can measure time, a coil and a resistor will create a delay proportional to the circuit values, and metal around the coil will change the coil’s inductance. As the inductance changes, so does the delay and, thus, the Arduino can sense metal, as you can see in the video below.

The simple principle is also simple in practice. Besides the Arduino and the coil, there’s a single resistor. You want a small coil since larger coils won’t detect smaller objects. If you don’t want to wind your own coil, [rgco] suggests using a roll of hookup wire as long as the resistance is under 10 ohms.

# Learn IC Decapping

Decapsulating ICs used to be an exotic technique. (I should know, I did that professionally for one of the big IC vendors back in the 1980s.) These days, more and more people are learning to take apart ICs for a variety of reasons. If you are interested in doing it yourself, [Juan Carlos Jimenez] has a post you should read about using acid to remove epoxy from ICs.

[Juan Carlos] used several different techniques with varying degrees of success. Keep in mind, that using nitric acid is generally pretty nasty. You need safety equipment and be sure to plan for bad things to happen. Have eyewash ready because once you splash acid in your eye, it is too late to get that together.