Re: trees?

  • From: "Hamid Hamraz" <hhamraz@xxxxxxxxx>
  • To: <programmingblind@xxxxxxxxxxxxx>
  • Date: Thu, 21 Oct 2010 01:12:29 +0330

Hi,
The algorithm for the 8-queen problem may do this:
First consider each node of the tree as a representation of a state of the board. For example, the root node is representing a chess board with a queen in the cell (1,1), that is the top left cell. Let's say that the algorithm is smart enough not to place the second queen in the same row. next step is to produce the first child node of the root, which represents a chess board with the first queen at (1,1), and the second one, in (2,1). That is a conflict, so the algorithm backtracks to the root and span another child of the root,which is a chess board with the second queen in (2,2). again conflict, and the algorithm should backtrack to the root. It does this until it finds a none-conflicting state for row 2. and then it moves forward to the 3rd row and so on. sometimes the algorithm may need to backtrack more than one level. please note that the algorithm is not allocating memory for the whole tree, it only needs to keep track of the current working state. If you look to what algorithm is doing as a whole, you can conceptualize a very big tree with a 8 to the power of 8 nodes, each of them representing a chess board with 1 to 8 queens placed, each in one row, conflicting or not. The mission of the algorithm is to crawl among the various nodes of the tree until it finds a leaf node without any conflict. that is the 8 queens are placed there in a none-conflicting situation. If the algorithm continues crawling it can find 92 different solutions for the problem, among the huge search space of 8 ^8 states. This may look too much information, but when you understand it then it is easy and it becomes a solid basis for similar problems, that are arising very often in computer sciences. Last but not least, I just wanted to relate the concept of the trees to a solutionof mine. The algorithm at your hand may be different. It may be more heuristical or may be sillier. But the concept of the tree, as a representation of the search space is similar. 
HTH
Hamid
----- Original Message ----- From: "Alex Hall" <mehgcap@xxxxxxxxx> 
To: <programmingblind@xxxxxxxxxxxxx>
Sent: Wednesday, October 20, 2010 6:49 PM
Subject: Re: trees?



I get the concept, but that does not help me relate what the code is
doing with the tree (where, exactly, it is in the tree, why it stops
at a certain point, where it goes back to...)

On 10/20/10, Client Services <Operations@xxxxxxxxxxxxxxx> wrote:

Don't get very caught up in the drawing.
I think you grasp the concept already.
A tree with multiple branches and sub branches.
Create your own picture in your mind.

H.R. Soltani

-----Original Message-----
From: programmingblind-bounce@xxxxxxxxxxxxx
[mailto:programmingblind-bounce@xxxxxxxxxxxxx] On Behalf Of Alex Hall
Sent: Wednesday, October 20, 2010 10:54 AM
To: programmingblind@xxxxxxxxxxxxx
Subject: Re: trees?

In this case, I am talking about a tree os possibilities, where the
root is where you start and each of the root's children can have 0 or
more subtrees of their own... You see why this is so hard to represent
in an accessible way.

On 10/20/10, Phil Vlasak <pcsgames@xxxxxxxxxxx> wrote:

Hi Alex,
In an architecture plan, a tree is a circle with a dot at the center. The 
point represents the center of the trunk, and a circle represents the
average distance the branches reach out.

----- Original Message -----
From: "Alex Hall" <mehgcap@xxxxxxxxx>
To: "programmingblind" <programmingblind@xxxxxxxxxxxxx>
Sent: Wednesday, October 20, 2010 10:32 AM
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






----------------------------------------------------------------------------
----




No virus found in this incoming message.
Checked by AVG - www.avg.com
Version: 9.0.862 / Virus Database: 271.1.1/3207 - Release Date: 10/19/10
14:34:00

__________
View the list's information and change your settings at
//www.freelists.org/list/programmingblind





--
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





--
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

Other related posts:

  1. Home
  2. programmingblind
  3. Archive
  4. 10-2010