N Queen Problem ( Backtracking)
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 8 Queen problem. Naive Algorithm: Generate all possible configurations of queens on board and print a configuration that satisfies the given constraints. Backtracking Algorithm: The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we move to previous column and find other possible position for the previously placed queen. 1) Start in the leftmost column 2) If all queens are placed i.e. fill_count = no of queens Print the board 3) Try all rows in the current column. Do following for every tr