N queen problem

This is the presentation on N queen problem

1. WELCOME TO THE PRESENTATION

2. TOPIC : N-QUEEN problem using backtracking

3. THE QUEEN OF A CHESSBOARD

4. PROBLEM INVENTOR : MAX BEZZEL The puzzle was originally proposed in 1848 by the chess player Max Bezzel and over the years many mathematicians, including Gauss, have worked on this puzzle and its generalized n-queens problem.

5. SOLUTION INVENTOR : FRANZ NAUCK The first solution for 8 queens were provided by Franz Nauck in 1850 . Nauck also extended the puzzle to n-queens problem (on an n by n – a chessboard of arbitrary size ).

6. The N-Queen Problem: The N-Queens problem originates from a question relating to Chess , The n-Queens problem. Chess is played on an n × n grid, with each piece taking up one cell. A queen is a piece in chess that, in any given move, can move any distance vertically, horizontally, or diagonally. However, the queen cannot move more than one direction per turn. It can only move one direction per turn.

7. EXAMPLE WITH EXPLANATION USING BACKTRACKING (MATRIX FORM) : Q X X X Q X X X X 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 X X There exists no solution if we place the 1 st queen in the 1 st position Q

8. 1 2 3 4 1 2 3 4 Q 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 If we place the 1 st queen in the 2 nd position then the solution is 2 4 1 3 By using the same process for 4 queen we get another solution that is 3 1 4 2 Q Q Q Q Q Q Q Q Q X X X X X X X X X X X X X X X X X X X X

9. EXAMPLE WITH EXPLANATION USING BACKTRACKING (STATE SPACE TREE) : 1 1 2 4 Q 1 3 2 4 3 1 4 2 2 3 Q 2 X X X X X X 3 4 1 TO BE CONTINUED

10. 3 1 2 Q 2 3 4 1 3 2 3 2 3 2 Q 3 3 Q 4 X X X X X X X X X X 4 1 1 3 4 2 4 2 The solution for 4 queen problem are : 2 4 1 3 3 1 4 2 &

11.  T(N) = O(N 2 ) + N*T(N-1) If we add all this up and define the run time as T(N). Then T(N) = O(N 2 ) + N*T(N-1). If you draw a recursion tree using this recurrence, the final term will be something like n 3 + n!O (1). By the definition of Big O, this can be reduced to O(n!) running time. 1 1 2 4 3 2 4 3 1 4 2 2 3 3 4 1 3 4 1 3 2 3 2 3 2 3 1 3 4 2 2 Q 3 Q 2 Q 1 Q 4 X X X X X X X X X X X X X X Q Time complexity of N_Queen : X 2 X

12. THANK YOU ANY QUESTIONS ??