Thursday, April 14, 2011

Backtracking - my usual state of mind

This semester we learnt a charming little algorithm for solving problems known as backtracking. The method is simply to keep taking a choice at every level and "backtracking" or abandoning that level if you know that's not going to give you the solution.

The typical example where you try to place 8 queens on a 8x8 board such that they do not attack each other.

So you'll place the queen on first row, first column. The second will be second row, first column. Not possible as they have the same column, so backtrack.  Then, second row,second column. Diagonal attack. Backtrack.

You get the idea. A simple case of combinations.

No, I will not sound like the Miss Minchin from The Little Princess and carry on my academia. What I wanted to connect it with is my brain!

I just realised my entire thought process is a simple case of back-tracking. Of course in life, I can't simply take yes/no choices. I have a "we'll see" and a "maybe" and so on and so forth. But just imagine, for a time being you'd boil everything down to yes or no.

My answer "state", that is the wanted level is "Am happy". And I begin with a state "taking a break". "B" stands for backtrack.



Ha ha! Am pleased how this turned out. I've resized the image the best I can. Do left-click on it. And you can't use "greedy" here because the best solution at each step won't exactly lead to an answer. I shall now go on a self-imposed hiatus. Wish me luck guys for my exams.

5 comments:

  1. lol....too much of daa isn't good!! The proof is right above :P
    Anyway, nice work...the image is great:)

    ReplyDelete
  2. I am guessing your exams are soon. so, all the very best. anyway, how come you assumed you cant loop around state "distracted" to reach the desired "happy" state? and you know what- stuff taught in class can connote so many things only to and extract a blog post only from aliens like you! love you, the adorable story teller of 12 A!

    ReplyDelete
  3. Lol Nisha! Thanks a lot. And this is nothing. You read the Physics post on the belt? I honestly thought of all those things while putting putting my belt to hang.

    ReplyDelete
  4. Oh my goodness.I try not to think of what I learn whenever I can get away with it.You are pretty awesome! :D

    ReplyDelete
  5. Hee hee :-) thanks! I have exams going on. So somehow need to make it slightly imaginative :-P

    ReplyDelete