Re: trees?

  • From: Alex Hall <mehgcap@xxxxxxxxx>
  • To: programmingblind@xxxxxxxxxxxxx
  • Date: Wed, 20 Oct 2010 18:03:23 -0400

That is what the professor said. However, I fail to see how the
algorithm moves backwards, and other code-specific concepts, and the
professor only explains in terms of a tree... I will have to meet with
her Friday if Friday's class does not clear anything up.

On 10/20/10, Hamid Hamraz <hhamraz@xxxxxxxxx> wrote:
> 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
>
>


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

Other related posts:

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