N Queen problem is one of the common interview questions which is asked in many popular companies. This problem is solved using backtracking.
Problem Statement:
We are given N x N chessboard and N queens. The queens should be placed in such a way that no two queens should lie in the same column, the same row and the same diagonal.
Algorithm:
1. Start from leftmost part ; 2. If got the solution return true; 3. Check for the queen to be placed in the current column. If placed in the current column then check recursively for the solution and mark row of the current column with "Q". 4. If at any point during recursion solution comes out to be wrong then backtrack and unmark the marked places. 5. Return false if no solution is found else print the solution. |
Solution:
No comments:
Post a Comment