0

I'm having trouble doing backtracking and not sure if what I'm doing is backtracking exactly.

I have n amount of integers for my example it will be [5,6,7,8].

From those integers I need to find if a prime sequence exists and if it does display it.

The prime sequence for this example is 7,6,5,8 since 7+6=13 6+5=11 5+8=13

To get the answer I can go through each n and then try to see if its a prime sequence.

Starting at 5:

  • 5,6[7,8]
  • 5,6,7[8]

Since 7+8 isn't prime. Go onto next integer.

Since 5+7 isn't prime. Go onto next integer.

  • 5,8,[6,7]

Since 8+6 or 8+7 isn't prime. You're done with 5.

Starting at 6:

  • 6,5[7,8]
  • 6,5,8[7]

Since 7+8 isn't prime. Go onto next integer.

  • 6,7[5,8]

Since 7+5 or 7+8 isn't prime. Go onto next integer.

Since 6+8 isn't prime. You're done with 6.

Starting at 7:

  • 7,6[5,8]
  • 7,6,5[8]
  • 7,6,5,8

End since you found the prime sequence.

So how can I do this problem with backtracking?

Claud
  • 1,065
  • 3
  • 26
  • 38
  • I'm having a bit of trouble telling what your actual question is. Would you care to clarify that, please? – bitmask Apr 11 '12 at 01:17
  • How can I do this problem with recursive backtracking? And what is backtracking exactly in this problem? – Claud Apr 11 '12 at 01:21
  • one way to optimize the algorithm is to ignore cases where it goes odd, odd (except 1, 1) or even, even as that always has an even sum and the only even prime number is 2. – twain249 Apr 11 '12 at 01:24
  • @Claud25: Okay, I tried to explain the issue and give you the core of the idea of the way backtracking can be used to approach this issue. I noted (see answer below) that this is not how you want to implement this in C++, because it will create a big overhead copying instances. It's the logical algorithm, that would be hidden behind implementation specifics for a given language (well, except maybe Haskell). – bitmask Apr 11 '12 at 01:32
  • I've done the program without backtracking I believe.. I don't know if you could further help me but any help is appreciated. – Claud Apr 11 '12 at 03:38

2 Answers2

3

The idea of backtracking in this context is basically this: Let me find a continuation of a subsequence (or a prefix) of the total thing that works. If I'm successful I'll return that continuation to my caller. If I'm out of luck, I'll ask my caller to try a different prefix.

More precisely:

// call initially as Backtrack(epsilon, all numbers)
Backtrack(Sequence fixedPrefix, Set unbound) {
  if (unbound is empty) {
    return check(fixedPrefix);
  }
  for all (element in unbound) {
    if (Backtrack(concat(fixedPrefix,element), setminus(unbound,element))
      return true;
  }
  return false;
}

Note that this algorithm will only tell you whether a sequence exists (and its straightforward implementation in C++ would be horribly slow) but not what that sequence is, but that's trivial to modify.

Anyway the "back" in backtracking happens at the very last line where the recursive call is out of luck: this will prompt the calling instance to try another prefix, so the control flow is a bit reversed.

bitmask
  • 32,434
  • 14
  • 99
  • 159
  • I'm still trying to understand. I know this might seem easy but I can't get a grip. If my fixedPrefix = [5] and my unbound = [6,7,8]. It checks all elements in unbound. It then takes 6 and checks to see if 5+6 is a prime? then if it is fixedPrefix becomes [5,6] and unbound becomes [7,8]? – Claud Apr 11 '12 at 01:45
  • @Claud25: No, that would be a possible optimisation. Right now this only checks the entire sequence, once the last level of the recursion is reached. You *could* already discard prefixes that will under no circumstances result in a valid sequence, but I didn't include this in this answer, to make the core idea more clear. – bitmask Apr 11 '12 at 08:09
1

Your function (pseudo-code or not) does not do anything productive. I am actually unsure of what it is supposed to do. ie. u = 0; immediately followed by if(u == 4); and your isPrime function is always passed (Integers[0]+integers[0]).

I believe that what you are referring to as backtracking is more appropriately referred to as a recursive function (a function that can call itself). Backtracking is a poor (vague) name for a particular behavior which a recursive function can exhibit.

If you want a recursive function as such, you need to scrap this and start over. Write out what the function should do in plain english (or other language). Then code to that once you know what you need to pass to it, the difference between failure and success, and what to return upon failure or success (how the vector needs to be modified upon a failure).

Super Hint: for small selections of integers, such as you present, try out next_permutation() in the stl < algorithm > to quickly go through the possible arrangements of ints in your vector.

dB8
  • 176
  • 5
  • Obviously my pseudo-code is crap but I did do the problem in English on paper and in my example. I just want to know how I can do what I've done on paper with backtracking. So backtracking is just a recursive function but stops if its a dead end? – Claud Apr 11 '12 at 02:00
  • In sloppy english: Is vector[n] + vector[n+1] prime? If so, try vector[n+1] + vector[n+2] by calling the function again by passing it the vector and n+1. If so and n+1 is the last value of the vector, return true. If not, have the function swap some values in the vector and return false. – dB8 Apr 11 '12 at 02:09
  • Side note: If you are using any complex type (like ) in a recursive function and you can allow it to be altered, please pass by reference. ie. `bool Backtrack( & myVec, int n){ }` – dB8 Apr 11 '12 at 02:24