Problem Statement:
8 Queen problem is a standard example in the backtracking world. Whenever you start learning the backtracking paradigm this is the first problem you may encounter. So the question is how to solve this problem. For any given problem it is very rare that we directly come to an optimal solution.
Let’s try the brute force solution.
Our goal is to keep N queens in N rows such that they are not in an attacking position. The first thought that will come to our mind is to check if a position is safe to keep the queen, place it and move to the next row.
This leads 2 scenarios
- You can put a queen in a row, awesome move to the next row
- You are not able to put a queen in a row. what to do here? Go to the previous row and change the queen’s position.
Whenever you find this type of problem where you may have to go back there is two implementation strategy 1. Stack 2. Recursion
If you can reach the last row voila, you have got a sequence!! A
Code:
