# Chess: 8 queens solution-- using a stack

Email
 Submitted on: 1/2/2015 12:55:00 AM By: Bobby Foerster (from psc cd) Level: Intermediate User Rating: By 4 Users Compatibility: C++ (general), Microsoft Visual C++, UNIX C++ Views: 6386

Goal Write a stack-based program that solves a variation of the classic “Eight Queens” problem. Background In chess, the Queen is the most powerful piece in terms of attacking and defending. A Queen can move as far as she can in a straight line forward and backward, side to side, or diagonally, only being stopped by the edges of the board and other pieces in her path. Thus, Queens typically attack many squares on a chessboard, and often this ability is used to attack several enemy pieces simultaneously, or protect several of her own pieces, or both. This gives rise to an interesting chess puzzle: can eight Queens be placed on a chessboard so that no two Queens attack each other? Details The traditional technique for solving Eight Queens is to use a backtracking algorithm, in the form of recursion. The main concern with this approach is that there are 4,426,165,368 different ways to place eight Queens on a chessboard; this is far too many positions to process. Thus, heuristics have been developed that reduce the number of positions to try. The first is to note that only one Queen can be placed in any column, since two Queens in the same column attack each other. By only considering boards with one Queen per column, the number of positions is reduced to 16,777,216, a reduction of 99.6%. By making the same observation for columns, the number is further reduced to 40,320 positions – certainly few enough to be examined. Further heuristics can even reduce this number. Our approach will have two twists: first, we will use a nonrecursive algorithm; second, we will be given the position of one of the Queens, and we must place seven more on the board so that none attack the others.

### INCLUDE files:

Can't Copy and Paste this?
 ```//************************************** //INCLUDE files for :Chess: 8 queens solution-- using a stack //************************************** #include ```

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come out every day, so no prevention program can catch 100% of them. For your own safety, please:
2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.

If you don't have a virus scanner, you can get one at many places on the net including:McAfee.com

Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

What do you think of this code (in the Intermediate category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)