8 -Queen_Puzzle_Problem_Presentation.ppt

This presentation explains the 8 puzzle problem.

1. 8-Queens Puzzle

2. Basic Rules
The board: a matrix of size N X N.
In standard chess: N = 8.

3. Basic Rules
The queen - moves horizontally, vertically, or
diagonally.

4. The queen - moves horizontally, vertically, or
diagonally.
Can attack any piece on its way.
Basic Rules

5. The queen - moves horizontally, vertically, or
diagonally.
Can attack any piece on its way.
Basic Rules

6. Basic Rules
Two queens threaten each other if they are on
the same vertical, horizontal, or diagonal line.

7. Basic Rules
Two queens threaten each other if they are on
the same vertical, horizontal, or diagonal line.

8. 8-Queens puzzle
Place 8 queens on the board such that
no two queens are threatening each other.

9. S
tep-by-step Algorithm
1 .Initialize the board: Create an 8x8 chessboard and initialze
all positions to 0(empty).
2 .Recursive function :
Base case- If the current row is 8(all queens have been
placed), return true (solution found) .
Iterative loop –
For each column in the next row;
Check validity:
i. If the current position is safe (no queen attack),place a
queen there .
ii. Recursively call the function for the next row.
iii. If the recursive call returns true (solution found),return true.
iv. Remove the queen from the current position(backtracking).
If no valid position is found in the current row, return false(no
solution) .

10. Recu
rsive (non-OOP) solution

11. 8-Queens puzzle
Place 8 queens on the board such that
no two queens are threatening each other.

12. Place a queen at a non-threatened cell.

13. Place a queen at a non-threatened cell.

14. Place a queen at a non-threatened cell.

15. Place a queen at a non-threatened cell.

16. Place a queen at a non-threatened cell.

17. Place a queen at a non-threatened cell.

18. Place a queen at a non-threatened cell.

19. Place a queen at a non-threatened cell.

20. Backtrack.

21. Backtrack.

22. Place a queen at a non-threatened cell.

23. Place a queen at a non-threatened cell.

24. Place a queen at a non-threatened cell.
Backtrack…

25. • Each queen is an autonomous agent!
Main ideas
• Queens are added to the board from left to right.
• A queen tries to find a safe position in its column.
• If no safe position is found,
then the queen asks its neighbors to advance to
the next legal position.
(In which no two neighbors threaten each other.)
• Each queen has its own fixed column.

26. A queen places itself at a safe position in its column.

27. A queen places itself at a safe position in its column.

28. A queen places itself at a safe position in its column.

29. A queen places itself at a safe position in its column.

30. A queen places itself at a safe position in its column.

31. No safe position for queen 6 at column 6.
Asks neighbor (queen 5) to change position.

32. No safe position for queen 6 at column 6.
Asks neighbor (queen 5) to change position.

33. Queen 5 is at the last row.
Asks neighbor (queen 4) to change position.

35. A queen places itself at a safe position in its column.

36. A queen places itself at a safe position in its column.

37. A queen places itself at a safe position in its column.

38. A queen places itself at a safe position in its column.

39. No safe position for queen 8 at column 8.
Proceed the search in a similar way…