RE: trees?

  • From: "DaShiell, Jude T. CIV NAVAIR 1490, 1, 26" <jude.dashiell@xxxxxxxx>
  • To: <programmingblind@xxxxxxxxxxxxx>
  • Date: Thu, 21 Oct 2010 08:28:10 -0400

What I'm about to write will sound a bit loopy, use of string to attempt
to position pieces on the board and tag each string for its intended
destination may help.  The next thing to do is get with that algorithm
and do each example with its own piece of string and tag.  Let's say n=3
for a simplistic example and the root cell is (1,1) if a queen lands in
cell (1,1) (2,2) and (3,3) are blocked off since they're diagonal to
(1,1).  The cells (1,2) and (1,3) are also blocked since they're in the
same row as (1,1).  The cells in (2,1) and (3,1) are likewise blocked
since they're in the same column as (1,1).  So on this (3,3) board, when
cell (1,1) gets a queen, Only one of two other cells remain open, your
choice is between (2,3) or (3,2).  Or, a root with top left corner
occupied with a (3 by 3) dimension cannot have any left places filled,
the center place cannot be filled and bottom right cannot be filled and
nothing else in top can be filled.  Reason piece is in top left and in
the case of a three by three board, center is adjacent to top left.


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

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

__________
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