N Queen Problem

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

1. N-Queen Problem

2. Presented By
1.Piyush Nitnaware
2.Divyanshu Bisen
3.Snehal Mandpe
4.Shreyas Khadke

3. 1. 2. 3. 4. 5.
TABLE OF CONTENTS.
INTRODUCTION EXAMPLE APPROACHES ALGORITHM
AND
ADVANTAGES
CONCLUSION

4. INTRODUCTION
N-Queens dates back to the 19
th
century
(Studied by Gauss).
Classical combinatorial problem, widely
used as a benchmark because of its simple
and regular structure.
Problem involves placing N queens on an N
x N chessboard such that no queen can
attack any other.
.Benchnark code versions include finding
the first solution and finding all solutions.

5. 4 Queen
Problem
Example
4 – Queens ’ problem is
to place 4 – queens on
a 4 x 4 chessboard in
such a manner that no
queens attack each
other by being in the
same row, column, or
diagonal.

9. APPROACHES
1. Brute Force 4. Divide And Conquer
Approach
5. Graph Theory
Concepts

3. Permutation
Generation
2. Backtracking
6. Mathematical
Solutions

10. ALGORITHM
Time Complexity : O(N²)
Auxiliary Space : O(N)

11. Flow Chart

12. ADVANTAGE
OVER OTHER METHODS.
The advantage of the backtracking algorithm is
the ability to find and count all the possible
solutions rather than just one while offering
decent speed. The backtracking algorithm
increasing speed several times just by starting
multiple threads with different starting
positions of the first queens.

13. N-Queen Problem
CONCLUSION
1.In N-Queen, as N value increases the time of processing also
takes more time. This happens when we try to display all the
possible solutions.
2.Of course, we could make it much faster if we wanted to only find
one solution instead of all of them: not more than a few
milliseconds for board sizes up to 50.

14. DO YOU HAVE ANY QUESTIONS?
THANK YOU!