n-queens problem

[chewykb24]

hey yall! Im stuck, and im looking for some ideas. I want to solve the n-queen problem using a breadth first search. Plan to call the breadth search from my main function, and i have a check function which will verify if a queen can be placed in that position. I understand how a breadth search works, but as far as exploring multiple states at the same depth, im really not sure how to implement that. To me its like i would have to store each state seperately and then go depth by depth and evaluate each one, but storing that many states is impossible. Any ideas would be happily received ... or possibly an algorithm ;).

[hamsterman]

You will have to store many states. That's how this search works. Note that a state does not have to be an array of 64 booleans. It could be a permutation of 8 integers from 0 to 7, or, more conveniently, 8+8+15+15 booleans showing what columns, rows and diagonals are already filled. Also, many possible moves are equivalent (such as placing the first queen on a1 or on a8 - you'll get the same result rotated 90 degrees). And when you place a queen, there are much fewer choices for the next one. Note that you don't need to store previous states, as they will never be the same as your current ones. So in the end, you really won't have an impossible number of states at any time.

[matthewmpp]

I have thought about working on this problem. I was thinking about creating a 64 square 2 dimensional array to hold the board information. I was going to use a 1 to represent the first queen, and 2's to represent the squares that queen can take. Next, I would use a 3 to represent the next queen and 4's to represent the squares that queen can take. So odd numbers will be queen locations and even numbers will be squares that can be taken. As for placing the queen's I would place the first queen in the corner and work my way out from the corner placing each queen the way a knight moves from the last queen. This should be the most efficient placement of the queens.