Название (оригинал): Chess: 8 queens solution– using a stack
Write a stack-based program that solves a variation of the classic “Eight Queens” problem.
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?
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.
Написать стек на основе программы, которая решает вариация классической