Re: trees?

  • From: Dave <davidct1209@xxxxxxxxx>
  • To: programmingblind@xxxxxxxxxxxxx
  • Date: Thu, 21 Oct 2010 23:12:25 -0700

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
>> //www.freelists.org/list/programmingblind
>>
>> __________
>> View the list's information and change your settings at
>> //www.freelists.org/list/programmingblind
>>
>> __________
>> View the list's information and change your settings at
>> //www.freelists.org/list/programmingblind
>>
>
> __________
> View the list's information and change your settings at
> //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
> //www.freelists.org/list/programmingblind
>
> __________
> View the list's information and change your settings at
> //www.freelists.org/list/programmingblind
>
>
__________
View the list's information and change your settings at 
//www.freelists.org/list/programmingblind

Other related posts: