N queens using backtracking

N queens problem using backtracking

1. Presented by : G.SRILEKHA B16CS045 Counsellor : B.SRINIVAS sir N-Queens problem

2. contents Problem statement History Backtracking Data flow diagram Algorithm Output Advantages over other methods Conclusion

3. Problem Statement The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. That means , no two queens are placed in same row or in same column or diagonal to each other.

4. History Chess composer Max Bezzel  published the eight queens puzzle in 1848.Franz Nauck  published the first solutions in 1850.Nauck also extended the puzzle to the  n  queens problem, with  n  queens on a chessboard of  n  ×  n  squares. Since then, many mathematicians, including Carl Friedrich Gauss, have worked on both the eight queens puzzle and its generalized  n -queens version. In 1874,  S.Gunther  proposed a method using determinants to find solutions.J.W.L . Glaisher  refined Gunther's approach.

5. BACKTRACKING Backtracking is finding the solution of a problem whereby the solution depends on the previous steps taken. Thus, the general steps of backtracking are: start with a sub-solution check if this sub-solution will lead to the solution or not If not, then come back and change the sub-solution and continue again

6. start t P lace a Queen and check for next queen Is possible or not Backtrack and again check other column stop N o Yes FLOW CHART

7. ALGORITHM Place the queens column wise, start from the left most column If all queens are placed. return true and print the solution. Else Try all the rows in the current column. Check if queen can be placed here safely if yes mark the current cell in solution matrix as 1 and try to solve the rest of the problem recursively. If placing the queen in above step leads to the solution return true. If placing the queen in above step does not lead to the solution , BACKTRACK, mark the current cell in solution matrix as 0 and return false. If all the rows are tried and nothing worked, return false and print NO SOLUTION.

8. Output ( if n=4)

9. If we continue the process , we get another solution as : First Solution

10. TIME TAKEN FOR EACH INTEGER N OF A QUEEN

11. Advantages over other methods   The major advantage of the backtracking algorithm is the abillity to find and count all the possible solutions rather than just one while offering decent speed. In fact this is the reason it is so widely used. Also one can easily produce a parallel version of the backtracking algorithm increasing speed several times just by starting multiple threads with different starting positions of the first queens.  

12. Conclusion 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. 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.

13. THANK YOU !!