we could have also printed the positions using two for loops rather than using this method. then how does this method help in solving the above problem ??
Advantage of using this method?
@Krish-Banerjee-2770813363035183,
The worst case ābrute forceā solution for the N-queens puzzle has an O(n^n) time complexity. This means it will look through every position on an NxN board, N times, for N queens. It is by far the slowest and most impractical method. If you refactor and prevent it from checking queens occupying the same row as each other, it will still be brute force, but it has a time complexity of O(n!).
Backtracking is a recursive method which starts a queen at an edge and, ideally, saves the possible attack positions. Then another queen is placed at a safe positionā¦repeat. However, if it is found that N number of queens cannot be placed on that board, it will backtrack and try another safe position. This is over 100 times as fast as brute force and has a time complexity of O(2^n). Also, this can be further optimized as well so yes we prefer backtracking over brute force and hence avoid using 2 for loops.
1 Like
I hope Iāve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
1 Like