winzip icon

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?
Click here for a copy-and-paste friendly version of this code!
//**************************************
//INCLUDE files for :Chess: 8 queens solution-- using a stack
//**************************************
#include <iostream.h>
winzip iconDownload code

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:
  1. Re-scan downloaded files using your personal virus checker before using it.
  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


Other 1 submission(s) by this author

 


Report Bad Submission
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:

Your Vote

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

Other User Comments


 There are no comments on this submission.
 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)
 

To post feedback, first please login.