In this project, N-queens algorithm is implemented graphically. N queens must be placed on an N×N chessboard such that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.
Backtracking technique is used to place queens in each row at right place. Backtracking constructs candidate solutions one component at a time and evaluates the partially constructed solutions. This approach makes it possible to solve some large instances of difficult combinatorial problems, though, in the worst case, we still face the same curse of exponential explosion encountered in exhaustive search.
The primary objective of this project is to graphically show the concept of backtracking with the help of the N-queen puzzle as an example.
Transformations in the project:
• Scaling: When the Queen moves from one cell to another it is in the shape of a small square and when it reaches any appropriate cell ,it scales up to a larger sphere.
• Translation: The Queen moves in horizontal direction, from left to right until it reaches an appropriate cell.
This project uses OpenGL software interface. Simple techniques like rotation, transformation, motion, lighting, etc have been used.
OpenGL is a software interface to graphics hardware. This interface consists of about 150 distinct commands that are used to specify the objects and operations needed to produce interactive applications.