OddThinking

Let’s divide the world of puzzles into the type that are real dilemmas versus the type people do for fun, and look at the latter for a while.

Let’s divide the fun puzzles into the type they put in newspapers each day versus the type they don’t. The distinction is important – the type they put into newspapers each day can’t be the sort of puzzle like “Estimate the number of grooves on an vinyl 33 1/3 rpm LP album.” They have to be the sort where they can generate new ones each day following the standard structure.

These newspaper style puzzles can be divided up again along a spectrum from the type that require general knowledge (like trivia quizzes) to the type that require the ability to solve logic problems. Crosswords and Target words fit somewhere in the middle.

I only attempt the trivia type puzzles occasionally. I feel little sense of failure for being ignorant of a useless fact or an unusual word, so I have limited motivation to finish a crossword.

So let’s look at the logic puzzles at the other end of the spectrum.

To open up a newspaper and to solve a puzzle in it is an achievement… in a way… I guess.

However, being a algorithm geek, I don’t think you haven’t really solved a puzzle until you constructed a repeatable process to solve the class of puzzles…

…and being a software geek, I don’t think you have really, truly beaten the puzzle until there is some software to completely automate the process finding the solution.

I have annoyed people with this approach before – it tends to kill dead any amusement from the puzzle in the future.

I was given a tiling puzzle as a gift once, and while I was grateful for the thought behind the gift, I never actually took it out of its packaging. I read the rules, and suspected that the puzzle was NP-complete [Ref]; I didn’t see any point in playing with it, if I couldn’t solve it algorithmically.

Perhaps I was too hasty – I have whiled away some time with Microsoft’s Minesweeper, in the past, but now I have learnt that Minesweeper is NP-complete. I currently find myself with no urge to play it ever again – I wonder if that feeling will pass.

A good compromise is to write some software to assist you in solving the puzzle – performing the drudgery of mundane calculations without actually stepping over the mark and simply searching through the solution space for an answer.

It has been an approach I have used in the past for puzzles like Codewords and Solitaire Battleships. [To my horror, Solitaire Battleships is probably NP-complete too. Oooops.]

Casey once made a similar point about some software he was writing to solve a puzzle. He simply refused to use “backtracking” in his algorithm.

Backtracking is a term to describe letting your computer play a trial-and-error guessing game. The computer can guess a a solution first and then check to see if the result is right. If not, it “backtracks” and guesses again. If a computer can make thousands of semi-educated guesses a minute, it may not take that long to find a solution to a particular puzzle.

If you use backtracking, then you have given up trying to skillfully pick the lock to the door that separates you from a general solution, and are instead are using the sheer weight of your computer as a battering ram.

So to summarize:

If you can automate the process without backtracking, you have solved it, and and the puzzle is probably no longer interesting.

If you can automate half of the process without backtracking, you may have a useful tool to assist you in solving some of the more challenging problems.

Alternatively, it may just be NP-complete. While it might be amusing to solve particular instances, you are never going to really beat it.