Hacker News Reader

Comment by nitrix | Hacker News Reader

Important distinction for the author: backtracking is the search mechanism that you're able to use when your logic comprise only predicates.

"Avoiding a configuration like 1,1,1" isn't enabled by backtracking. Rather, it's a constraint placed on the search space (domain), for which, the generator wont need generating solutions that needlessly gets tested.

Your son would probably really enjoy Prolog (and Logic Programming in general) where these concepts are much more developed.

Check out the channel "The Power of Prolog" on YouTube to get your mind blown: https://www.youtube.com/channel/UCFFeNyzCEQDS4KCecugmotg/vid...

View on HN

Backtracking is not only a subject of logical programming. This definition [1] is quite general, so a loop with a single predicate can be called backtracking too.

Though I agree that the word "backtracking" is mostly used in a logical programming, and Prolog is a famous example of its implementation and usage.

[1] https://en.wikipedia.org/wiki/Backtracking

Of course backtracking isn't only a subject of logical programming, what made you think that when reading my reply?

The use of "when your logic" doesn't limit you to programming languages or imply that one is involved.

I'm not sure why you feel the need to unnecessarily correct me on that.

Also, of course the definition is quite general and, of course, Prolog is famous for excelling at it. Those are precisely the reasons why I mentioned all of the things that I did, in the way that I did.

I really don't understand why you think it's necessary to put emphasis on that a second time.

Avoiding 1,1,1, in a code like this

   for x1 in range(1, 10):
        for x2 in range(1, 10):
            if x2 in [x1]:
                continue
            for x3 in range(1, 10):
                if x3 in [x1, x2]:
                    continue

looks like backtracking to me. Specifically, the "continue" statement is that "jump back" that prunes invalid search sub-tree. Though, the constrains are expressed as predicates here.

But even in a code where constrains are built into the loop, it also can be called backtracking, since we have our target predicate "is_valid(square)". The search tree is trivial in this case, though. It's just a root and leaves.

In other words, I didn't quite understand the distinction that you were talking about.

Reply on news.ycombinator.com