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