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 4 Queen problem.
 |
N-Queen Problem
Method: We can solve this problem using Backtracking.
Logic: First, we will place the first queen at the top left position. We will place queens one by one to different columns. Every time, when we place a queen, we will check if there is any queen that can attack the new queen. If it can, we need to backtrack and find another position for the new queen. If all columns checked and can't find the place for a new queen, we return false to caller method and it will change the position of queen placed before.
Recommendation: Check out this video by Tushar Roy.
Implementation: Check out my implementation in Java here.
Time Complexity: Because of multiple backtrackings, the time complexity of this algorithm will be Exponential. |
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 4 Queen problem.
No comments:
Post a Comment