Category: Recreation

Car Talk and TSP Paths

On the suddenly hot topic of the Traveling Salesman Problem (see here and here), this week’s Car Talk puzzle is a TSP-like problem (though it is really a graph theory problem: the hamiltonian path problem to be exact).

The company that Bobo works for just finished a new product. They wanted to promote it across the country. Bobo was asked to travel by car to each of the 48 contiguous U.S. states to promote the product. He was told that he could visit each state in whatever order he chose, but the company wanted him to start in Delaware, at their headquarters.

They asked that he visit each state only once. He could not go back into a state he had already visited because this was the “Don’t Look Back” product tour. So, Bobo sat down at his desk and began to plan his trip.

He realized immediately that it was going to be one long car trip. At that moment, his boss stopped by and said, “Hey, I’m going to join you when you reach your last state. I was born there and I’ve been looking for a reason to go back and visit. You can leave your rental car there, and I’ll fly you back in my private jet.”

Since Bobo hadn’t planned his trip yet, how did his boss know which state was going to be Bobo’s last state? And, which state would that be?

That question is not hard (I won’t ruin it by giving the solution here:  call the state X);  the key is the statement about the flight back from the final state.

But it is strange that Delaware was given as the starting state.  Does it really matter?  Well, if you start in State X, you can end up in many (but not all) of the other states.  But it if you start in some other states, there is no path through all the other states without repeating a state.  I count seven starting states that preclude paths through all the other states by road without repeating a state.  Which can you find?  The following map is just for illustrative purposes:  the question refers to the “real” United States state structure (so you might need to check a more detailed map to see what states connect directly to others).

NOTE ADDED 1/17/2012.  Reddit’s lordlicorice has drawn the graph underlying the States:

 

Thanks to @wjcook for pointing out the Car Talk problem.

16 Clue Sudokus

I am sure everyone has seen Sudoku puzzles:  it was quite a fad a few years ago.  The puzzle begins with an 9×9 grid, partially filled with numbers from 1 to 9 (the “givens”).  The goal is to complete the grid so that that every row, column, and the nine 3×3 subgrids in the corners and center all contain the numbers 1 through 9 with no missing and none repeated.  There was a time in my life where I loved Sudoku puzzles.  I had to give them up when I started to dream solely in Sudoku.

The puzzles can be difficult or easy depending on straightforward it is to deduce missing values.  A grid with many  givens tends to be very easy, since there are few choices for missing values (though there can be hard problems with many givens and easy ones with few).  If too few values are filled in, however, the solution may not be unique, and it is a fundamental precept of puzzle-creators that the solution must be unique.  So, how many givens are needed to ensure uniqueness? It has been known for a long time that there exist problems with 17 givens that lead to unique solutions.

Gary McGuire, Bastian Tugemann, Gilles Civario of University College Dublin proved this result is the best possible:  there is no problem with 16 givens with a unique solution.  They do this in a very interesting way:  they did an exhaustive search.  Given the number of possible solutions, it is surprising that exhaustive search works, but they were clever in organizing the search, and had access to a ridiculous amount of computational power.  This combination let them run through all the choices.  They didn’t find a 16, therefore there is not a sixteen!

Fascinating work, and a sign of how fast computing can change how we look at research problems.  Technology Review has an article on this;  the technical report is at arXiv.

Operations Research, Sudoko, Rogo, and Puzzles

A few years back, Sudoko became a craze with seemingly everyone spending their time solving these puzzles.  The puzzle is quite simple:  take a nine by nine grid, partially filled in with numbers from one to nine, and complete it so that every row, column, and non-overlapping 3×3 square contains the numbers one through nine exactly once each.  While the grid contains numbers, there is no mathematics involved:  using the letters a-i would work as well.  But you can use mathematics (in the form of logic) to solve the puzzle.  To solve these by hand, puzzlers quickly learn logical rules, from the simple (“If only one square is open in a row, then you know what number goes there”) to advanced (say, alternate pair exclusion).  One can even use the methods of operations research (say, constraint programming or integer programming) to solve Sudoko puzzles.   It does not seem to discourage human solvers to know that these techniques can solve any Sudoko problem in milliseconds.

There is often a close relationship between puzzles and the methods of operations research, particularly networks or discrete mathematics.  Finding a path in a maze is nothing more than a shortest path problem;  “logic” puzzles (“Smith, Jones, and Robinson are (not respectively) a trucker, a fireman, and an engineer, who live in …”, followed by facts, leading to “What is the name of the engineer?”) can be handled through integer programming, and so on.  People, for some reason, like to do combinatorial search in their spare time.

Hamish Waterer, with whom I shared an office in New Zealand and who is now at Newcastle in Australia, pointed out to me a puzzle that has even closer ties to operations research: Rogo.  In Rogo, the goal is to find a loop through a grid of fixed length that contains as many reward points as possible.    So, for this example (taken from the Rogo site)

the goal in this example is to find a loop of no more than 12 steps that includes as many points as possible.   The loop must be a real loop:  it must return where it started and can’t cross itself or double back. Steps can be either horizontal or vertical:  they cannot be diagonal.  The loop cannot include any of the black squares.  Here is the solution:

Rogo was created by two faculty members (Nicola Petty and Shane Dye)  at the University of Canterbury in Christchurch, New Zealand.  Not surprisingly, Nicola and Shane teach management science there:  the problem has a very strong operations research flavor.  This is a form of the Prize Collecting Traveling Salesman problem, originally studied by my colleague Egon Balas (in the regular PCTSP, there is a penalty for distance traveled:  in Rogo, there is an upper bound).

If you want to play around with this, you can get the iPhone (touch, pad, etc.) app. Creating a solver would make a nice undergraduate project (and I suspect there are at least a few master’s theses and perhaps a doctoral dissertation on algorithmic aspects of creating and solving these).