8 queen problem

8 queen problem

1. 8 Queen Problems Nagajothi N 1M.sc.,IT Department of Information Technology VVV College for women

2. Backtracking Backtracking can be defined as general algorithmic technique that considers searching every possible combination inorder to solve a computation problem

3. Crosswords Verbal arithmetic Sudoku Peg solitaire Backtracking can be used to solve puzzles or problems includes

4. States: Any arrangement of 0 to 8 queens on the bored Initial state 0 queens on the bored Successor functions Add a queen in any square Goal test 8 queens on the bored non attacked   Formulation

5. The 8 queen problems The eight queen puzzle is the problems of placing eight chess queen on 8x8 chess bored so that no two queens attack each other. A solution requires that no two queens share the same row, column or diagonal. The eight queen puzzle is an example of the more general n-queen problems of placing n queen on nxn chess bored, where solution exist for all natural numbers n with the exception of 1,2 and 3 . The solution possibilities are discovered only up to 23 queen.

6. 2x2 queen There is no solution for the 2-Queens  and the 3-Queens problem

7. Using Backtracking to Solve N Queens

8. Place the first queen in the left upper corner of the table. 2. Save the attack positions. Move to the next queen(which can only placed to the next line ). Search for a valid queen ,if there is one go to step 8. There is not a valid position for the queen delete it. Move to the previous queen. Go to the first valid position. Place it to the first valid position. Save the attacked positions. If the queen processed is the last step otherwise go to step 3 . Steps for backtracking

9. 8x8 is possible solution For 8-queens,generally 92 solutions are possible excluding symmetry, only 12 unique solution exist

10. T hankyou