Re: trees?

Also, in addition to my previous comments, serialization helps because
you can write something like:

1.  [ (root1, children1) ].  This is sometimes called pre order.  You
can view a tree as a list of nodes; the first item is the root of the
subtree and the rest of the nodes are its children.  Thus, you can
expand out this representation by:
[ (root1, (root2, children2), children1 - 1)...

or, you can view a list of nodes with the children first and then root
at the end:
[ (children1, root1)]
= [(children1 - 1, (children2, root2), root1]

etc...



On 10/21/10, Dave <davidct1209@xxxxxxxxx> wrote:
> The potentially difficult part of the algorithm described by others
> above is that it involves a depth first traversal of the possible
> states and also backtracking.
>
> With an 8 by 8 board, you can think of each square on the first row of
> the board each as a root to a tree.  That makes 8 trees.  Each "tree"
> then has 8 children; these children are the squares of row two.  Each
> of those children then have 8 more children each (taken from row
> three) ... and so on.
>
> The job of the algorithm then is to do a depth first search of each of
> these 8 trees and find a path in which every square on the path don't
> lie on the same diagonal, column, or row.  If you find a "conflict"
> then you know the path you're traveling down the tree is *wrong* and
> you move *up* the tree by one node and continue traversing the tree
> depth first.  Or in other words, you move back to the parent when a
> conflict occurs.
>
> Once you find that path (i.e. you reach a leaf node), then you have a
> possible placement of the 8 queens.
>
> Short of speaking to a person, you may want to review basic tree
> traversals like depth first search and ways to serialize trees.  I had
> the best luck understanding trees when I also could "flatten" them
> into a form that made them easy to write down on a single line.  So,
> make sure you really grock DFS on simple trees and then start tackling
> the specific tree representation of this problem; then, throw in
> backtracking...
>  hth.
>
> On 10/21/10, black ares <matematicianu2003@xxxxxxxxxxx> wrote:
>> I don't know, but the computer is used only where the human mind does not
>> give results on an average.
>> The n-queens problem commes from reality.
>> The real problem in chess sounds like:
>> Put 8 queens on the same collor on a chess board in a such manner that
>> they
>> can not capture each other.
>> The fun thing about this thing is that only great chess players can find
>> one
>> or two solution for this.
>> The average users/player don't succeed in such chalenge.
>> More over the computer, for the n=8 case finds how many solution do you
>> thing?
>> Well it finds 92 solutions.
>> This is funy, the fact that even there are 92 solutions out there, men
>> can
>> only find one or two with out computers.
>> Another problem for backtracking is a knight movements problem.
>> It sounds like this:
>> Giving a knight in a chess board square, move that knight such as it
>> covers
>> every square of the board, but only once.
>> You will see, read 2 - 3 - 4 problems in back tracking and you quickly
>> observe that the code is the same.
>>
>> ----- Original Message -----
>> From: "Homme, James" <james.homme@xxxxxxxxxxxx>
>> To: <programmingblind@xxxxxxxxxxxxx>
>> Sent: Thursday, October 21, 2010 10:57 PM
>> Subject: RE: trees?
>>
>>
>> Hi, I have a feeling that the answer to this is Yes. Would this kind of
>> thing also work for pieces that have limited movement? For example, a
>> pawn
>> can only move forward, but it can move two spaces on its first move. But
>> a
>> special case is that it captures by moving diagonally. Is this the same
>> kind
>> of thing or different?
>>
>> Thanks.
>>
>> Jim
>>
>> Jim Homme,
>> Usability Services,
>> Phone: 412-544-1810. Skype: jim.homme
>> Internal recipients,  Read my accessibility blog. Discuss accessibility
>> here. Accessibility Wiki: Breaking news and accessibility advice
>>
>>
>> -----Original Message-----
>> From: programmingblind-bounce@xxxxxxxxxxxxx
>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of black ares
>> Sent: Thursday, October 21, 2010 2:14 PM
>> To: programmingblind@xxxxxxxxxxxxx
>> Subject: Re: trees?
>>
>> this is yet another individual representing the class of stupid
>> professors.
>> Please, for the N-queens problem
>> read about backtracking and you will get the point.
>> If you read about recursive back tracking you will even get the point
>> regarding the tree representation of this problem.
>> How ever, the backtracking programing algorithm
>> is a static one, by static I mean, that
>> it has a fixed form where you only change data and a little operation and
>> from a problem you get another.
>> For example if you have a solution for another problem in backtracking,
>> you
>> can simply change somthing little there and you will get the n-queens
>> problem.
>> The recursive backtracking is easier to understand than iterative one,
>> but
>> this is just my point of view.
>> So your problem now is not to understand what a tree is, or how this
>> problem
>> is represented on a tree,
>> now your problem is to learn about back tracking and how to solve that
>> problems.
>> Sighted professors often tend to graphicaly represent all the things even
>> they didn't need to!
>> And also often the graphical representation is most disturbing than
>> explaining.
>> When you will realy need a tree like a abstract data structure, you will
>> understand it very well.
>>
>>
>> ----- Original Message -----
>> From: "Ken Perry" <whistler@xxxxxxxxxxxxx>
>> To: <programmingblind@xxxxxxxxxxxxx>
>> Sent: Wednesday, October 20, 2010 7:46 PM
>> Subject: RE: trees?
>>
>>
>>> You know how I did it in my software engineering class before I did the
>>> file
>>> and outline?  I wrote an asm black white tree and followed it in a
>>> debugger.
>>> Hmm is that a little nuts?
>>>
>>> Ken
>>>
>>> -----Original Message-----
>>> From: programmingblind-bounce@xxxxxxxxxxxxx
>>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Sina Bahram
>>> Sent: Wednesday, October 20, 2010 11:42 AM
>>> To: programmingblind@xxxxxxxxxxxxx
>>> Subject: RE: trees?
>>>
>>> I think that you should sit down with either her or someone  else who
>>> fully
>>> understands the concept, and concentrate on
>>> understanding how trees work, rather than being hung up on the
>>> representation.
>>>
>>> I'll volunteer to offer some info over skype or phone, and there should
>>> be
>>> some good websites on this, but concepts like this need
>>> to be explained in person/voice, not just by reading about them,
>>> although
>>> you can get a lot that way too.
>>>
>>> Take care,
>>> Sina
>>>
>>> -----Original Message-----
>>> From: programmingblind-bounce@xxxxxxxxxxxxx
>>> [mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Alex Hall
>>> Sent: Wednesday, October 20, 2010 10:33 AM
>>> To: programmingblind
>>> Subject: trees?
>>>
>>> Hi all,
>>> We are doing trees in an algorithms class I am taking. The assignment
>>> coming
>>> up is the "n queens" problem, where you have an n by n
>>> board and must place n queens on the board such that no two queens share
>>> the
>>> same row, column, or diagonal line. To "help" explain
>>> this, the professor is using a tree on the board. I am completely
>>> confused!
>>> She says I do not need to think of it in terms of trees,
>>> yet the only way she explains it is in tree terms, so I am not sure what
>>> she
>>> is talking about. Of course I know about trees, but
>>> when she tries to explain how the code we are looking at relates to the
>>> tree
>>> in terms of what the code is supposed to do, I haven't
>>> a clue as to what she is trying to say. Does anyone have any thoughts on
>>> how
>>> to represent trees, whether in braille or speech, or a
>>> good notation/substitute for a tree? TIA.
>>>
>>> --
>>> Have a great day,
>>> Alex (msg sent from GMail website)
>>> mehgcap@xxxxxxxxx; http://www.facebook.com/mehgcap __________ View the
>>> list's information and change your settings at
>>> http://www.freelists.org/list/programmingblind
>>>
>>> __________
>>> View the list's information and change your settings at
>>> http://www.freelists.org/list/programmingblind
>>>
>>> __________
>>> View the list's information and change your settings at
>>> http://www.freelists.org/list/programmingblind
>>>
>>
>> __________
>> View the list's information and change your settings at
>> http://www.freelists.org/list/programmingblind
>>
>>
>> This e-mail and any attachments to it are confidential and are intended
>> solely for use of the individual or entity to whom they are addressed.
>> If
>> you have received this e-mail in error, please notify the sender
>> immediately
>> and then delete it.  If you are not the intended recipient, you must not
>> keep, use, disclose, copy or distribute this e-mail without the author's
>> prior permission.  The views expressed in this e-mail message do not
>> necessarily represent the views of Highmark Inc., its subsidiaries, or
>> affiliates.
>> __________
>> View the list's information and change your settings at
>> http://www.freelists.org/list/programmingblind
>>
>> __________
>> View the list's information and change your settings at
>> http://www.freelists.org/list/programmingblind
>>
>>
>
__________
View the list's information and change your settings at 
http://www.freelists.org/list/programmingblind

Other related posts: