OddThinking

Hmm. Maybe we (and I include myself) make too much about the significance of backtracking.

Consider this. In the game of solitaire battleships you have at your disposal a number of techniques to make additional marks on the page. For instance you can mark rows or columns of ocean by looking for the 0-counts. Or you can mark ocean squares around known ship squares.

In either case you are embarking on a more-or-less mechanical search through some subset of the solution space. Additionally, your selection of techniques (ie 0-count rows, 0-count columns, adjacent oceans to ships, and others) is more-or-less iterative: you keep trying different techniques until you stop making progress.

Now obviously there is a certain amount of skill and logic required to come up with these techniques in the first place. This is not a mechanical search but the result of deep thinking about the rules and their implications.

The point is that once you have a complete set of general techniques to apply to specific problems, you have moved across into the realm of mechanical application of those rules through iteration. But this is the reason why we object to backtracking!

So why should backtracking be treated differently from any other solution techniques? Should I consider it cheating to use the 0-count rows technique because it is also a mechanical search (admittedly across a much smaller set). Is there a qualitative difference here, or is it merely quantitative?

The reason backtracking is anathema is that it trades intelligence for very large amounts of memory. Most strategies use very little memory (let’s call them “registers”) or no extra memory at all.

Real solutions are supposed to be intelligent. Backtracking is not just quantitatively worse but enormously so.

Thought experiment: many strategies involve analyzing several squares at once, looking for logical contradictions. This is very small scale backtracking. Good, or Bad?

So why should backtracking be treated differently from any other solution techniques?

Backtracking differs not in that it involves mechanical iteration, but in that it speculates. Rule-based solvers don’t – they make deductions. Their assertions are never retracted once made.

With rule-based solvers, the confidence in a particular set of solutions for each part of the puzzle gradually increases; with backtracking, all claims remain speculation and subject to annulment up until the very final guess that suddenly proves them all correct.

This is very small scale backtracking.

No, it’s not. No attempted solution for a particular square is based on a speculative but yet unproven solution for another square. Your definition of backtracking encompasses every algorithm that involves checking attempted moves for validity, so under this definition the term ceases to provide any useful distinction and hence is no longer interesting.

How frustrating. You guys are making me think! I keep changing my mind after reading the next comment.

Yes, Alastair, the result of the ingenuity (“skill and logic”) is a set of mechanical rules that search through the problem space. That could almost be used as a definition of programming!

The reason I don’t bother to implement backtracking for puzzles is that the level of ingenuity is low, and therefore boring. I have no objection to backtracking being used for real-world problems; I just choose not to do it for fun.

I agree that if you squint hard, the individual rules could be seen as a guess (or “small scale backtracking”, to use Andrew’s term). However, there is a qualitative difference, not just a quantitative one. So, I agree with Aristotle that squinting this hard makes the distinction “no longer interesting”.

I think Andrew touched on that difference by talking about memory. Similarly, I think Aristotle touched on the difference by saying “all claims remain speculation”.

I think the key qualitative difference is the recursion involved in backtracking.

That recursion is what consumes the memory Andrew was talking about, and is what keeps the claims all subject to speculation Aristotle was talking about.

Recursion eh?

Hmm, but surely any recursive algorithm can be re-written as an iterative one? So do you object to puzzle solutions that require iteration as well?

I am obviously playing devils advocate here, but I still don’t see a clear reason why the use of backtracking should be frowned upon.

My own preference is certainly to not use backtracking when puzzle solving. It’s the last technique I resort to, and when I solve a puzzle without it, it’s much more satisfying. So why is this the case? Is it simple laziness — meaning that backtracking requires more effort than other techniques — or something else?

As another thing to consider, I would say that while backtracking is in general a “bad” technique, some forms of backtracking are worse than others. The completely random guess is obviously inferior to the guess which would yield the most results with the minimum of effort.

So even though some puzzles require backtracking, they can be salvaged by requiring intelligent guessing. Choosing a location for a guess can be an interesting problem in itself: you want to guess such that you either confirm or contradict your guess as quickly as possible. Surely doing this intelligently at least partially redeems backtracking?

I was going to bring up the same objection about the equivalence of recursion and iteration.

The actual difference between rule-based solvers and backtracking is exactly the one I pointed out: speculation. Backtracking is nothing but an orderly way to generate all configurations of values for the given set of constraints, then throw away all the invalid ones so the correct one(s) is(/are) left. The purpose of the tracking back is to cull large numbers of possible but invalid configurations without attempting them. But that is not ingenuity or solving; that is simple optimisation.

The premise of backtracking is “guess the right solution.” Speculation. Guessing systematically is necessary to make the premise computationally tractable, but isn’t qualitatively different from guessing randomly.

A rule-based solver does not guess.

You can combine solvers with a backtracker in order to increase the efficiency of its systematic guessing, and in fact this is often necessary to solve practical problems (like realworld applications of the traveling salesman). But the ingenuity then lies in your formulation and choice of rule-based pickers, not in the boring and braindead backtracking itself.

Noone is disputing that backtracking is useful in practice, but it’s just not interesting when you are trying to solve a game in the general case, rather than simply finding the solution to a particular game of that game. We know we can solve traveling salesman problems with backtracking. That is what we do when we have to do it, actually. (Check out branch-and-bound for an interesting and clever way to make it fast.) But that doesn’t tell us anything interesting about the mathematics of the traveling salesman class of problems.

Without ever having done it before, you can find the intersection point of two given line segments on a plane by guessing, too. But you don’t learn anything interesting about simple or linear algebra in that way. Using backtracking to solve a game in the general case is like answering the question “how does one find the intersection point of any two given line segments” with “by guessing correctly.”

Backtracking is useful. So is guessing. In fact, they are the same.

Guessing is not interesting. Neither is backtracking. Again, they are the same.

Drats. So much for my clarifying comment!

Yes, iteration is as powerful as recursion. I didn’t mean to suggest otherwise.

Let me try again.

With backtracking you preserve your state, make a guess, and follow the consequences, looking for contradictions. If you find a solution, great! If you find a contradiction, revert back to the preserved state. However, often you get neither. You get stuck again and you have to make another guess! So you save your state, and add an additional assumption. This act of recursion – making multiple consecutive guesses – is the qualitative difference I was referring to.

Alastair writes:

when I solve a puzzle without it, it’s much more satisfying. So why is this the case?

In real life, what is satisfying is seeing the answer you needed. Backtracking is great! In puzzle-solving, what is satisfying is seeing the fruits of your intellect working to obtain that answer. Backtracking doesn’t require intellect – except by the person who first invented it.

Surely doing this intelligently at least partially redeems backtracking?

Sure – if you can come up with ingenious optimisations. Even coming up with the perfect metric to optimise your A* or Brand-and-Bound searches counts.

Aristotle writes:

A rule-based solver does not guess.

Backtracking is useful. So is guessing. In fact, they are the same.

First, I will explain some infrastructure, and go off on a tangent. Then, I will argue that the argument of backtracking=guessing is not that simple, by explaining the counter-argument. Then I will dismiss the counter-argument and show I actually agree with you.

Hopefully, I can manage at least a modicum of clarity.

Infrastructure

Whether we are talking Hitori, Sudoku, Nonograms or Solitaire Battleships, the same principle applies: whenever a square changes its state, it has a number of neighbours that need to be informed, so that they can apply their rules. A rules-engine is responsible for managing these trigger-events and informing the neighbours.

Off on a Tangent
One of the major implementation differences I have tried between the different puzzle implementations in the way the rules-engine is triggered to check its rules.

In practice, I have tried:

• recursion (having one square directly call the trigger function on its neighbours)
• a queue (having one square push a request onto a queue, and an active rules-engine object iterating over the requests and sequentially calling the corresponding trigger function)
• a prioritised, consolidating queue (ensuring that the no item appears twice in the queue and pushing the most promising requests to the front)
• brute force iteration (simply iterating repeatedly over every square, triggering it whether it needs to or not, and repeating until the hurly-burly’s done.)

None of these techniques affected the final solution, but they did affect the number of unnecessary checks, the ease of debugging and the path of partial solutions visited on the way to the final one.

Back from the Tangent

When these triggers are fired, through whatever mechanism, the cell/row checks its constraints to see if it is known yet. Much of the time, it will simply return with no action – none of the new information available is sufficient to determine the correct value.

Checking = Guessing?

So, now comes the part where you need to squint, while I wave my hands.

It could be argued that the act of prodding a cell is a guess that the cell is now constrained. If the trigger returns with no change, that’s the equivalent of a guess being wrong.

If every call to the trigger function resulted in an additional constraint being added, the system would never be guessing. In practice, there are lots of these triggers resulting in nothing, so the system is guessing a lot.

Checking != Backtracking

I think that this definition of guessing “ceases to provide any useful distinction and hence is no longer interesting” to paraphrase Aristotle.

However, whether or not you define the No-Op action as a failed guess, there is no attempt to build guesses on top of other guesses. I argue above that this guess-upon-guess recursion is the cornerstone of backtracking, and therefore the implemented algorithm is not backtracking whether it is considered guessing or not.

That was clear enough.

I argue above that this guess-upon-guess recursion is the cornerstone of backtracking

Exactly. In fact, it is not merely the cornerstone, it is nearly the very definition of backtracking: “remember previous states so you can return to them.”

If you look back, you’ll see that is what I’ve been saying. What you call guess-upon-guess I termed speculation: proceeding with a configuration whose ultimate validity or correctness you can have no confidence in. I guess I didn’t explain it all as well as I would have liked because the point was obvious to me all along; I always have trouble articulating things that seem tautological to me.

[Using the term “recursion” in the way you do is wrong, though. Recursion is merely a natural way to implement backtracking but not inherent to it. Of course, if you implement backtracking iteratively, you need a stack of some sort, so I understand why you want to call it recursion. Then again recursion does not conceptually have anything to do with a stack, even if all practical implementations require one.]

I came across this interesting thread today and believe I can contribute from my own point of view. My name’s Moshe Rubin, the author of the Fathom It! software mentioned above. Fathom It! comes with a built-in, rule-based Solitaire Battleship solver. As the help file explains, the solver works by iterating over a large set of strategies used by humans to solve such puzzles.

Julian noted above that (checking != guessing) and (checking != backtracking), something I totally agree with. Although many of the strategies used by Fathom It! do not require any checking, some do. These latter rules use the indirect proof method, e.g., assuming a square is water leads to a contradiction, therefore the square is a ship segment. I would classify this as ‘checking’, not ‘guessing’. Yes, the solver momentarily ‘guesses’ or assumes the square is water, but very quickly contradicts the assumption. Once the assertion is concluded it is never undone — the indirect rule has proven conclusively the identity of the square.

I am definitely averse to solving any puzzle, including Solitaire Battleships’ using guessing. It is trivial to write a brute force solver to solve any Battleship puzzle. Unfotunately, there is no intellectual ‘gotcha’ in such an approach. Like solving a good chess problem, like cryptanalyzing a difficult cipher, the payback is honing your skills for the next puzzle. I posted similar sentiments regarding solving FreeCell puzzles. I guess this is what spurred me to write a Battleship solver — could I understand the puzzle genre well enough to mimic the way a human would solve such a puzzle?

I think the criterion of a solver boils down to: does it emulate the way a human would solve the problem? If not, it may give the solution, but it can never teach a human how to be a better solver.