The 8 queens problem is a very popular puzzle especially for a Computer Science engineer. From the point of view of algorithms, there can be many approaches towards its solution. The problem statement and various solution approaches are mentioned below.
Problem: Arrange 8 queen pieces in the standard chess board so that none of the queens can take any other queens, i.e, there is no conflict in their positions.
Solution:
Approach 1: The common and straightforward solutions for the beginners is the brute force technique. Take all the arrangements of 8 pieces that can be possible and discard those that are in conflicts. It is not at all a suggested approach as its exponential if the problem is generalized to n-queens on an nxn board problem.
Approach-2: Backtracking is a common AI approach of solving problems. In this problem, we start arranging the queens column wise such that the current queens position is not in conflict with any of the previous ones. If there is a conflict in the column, we try to place it in the next available(conflict-free) column. If we run out of columns, we backtrack to the last stable arrangement and continue process from there and so on. This is actually accomplished through recursive backtracking technique.
Approach-3: Permutation Method. First a solution is found out for 8 rooks on a chess board which has only 8!=40320 possibilities. Then take each permutation and replace the pieces by queens and discard those arrangement where the queen is attacked diagonal-wise.
All solutions mentioned above produce guaranteed results. There are other heuristic based approaches which may get stuck midway.
Reference:
No comments:
Post a Comment