N-Queens problem

• The N - Queens problem is to place N - queens in such a manner on an N x N chessboard that no queens attack each other by being in the same row, column, or diagonal.

• Here, we solve the problem for N = 4 Queens.

• Before solving the problem, let's know about the movement of the queen in chess.

• In the chess game, a queen can move any number of steps in any direction like vertical, horizontal, and diagonal.

• The only constraint is that it can’t change its direction while it’s moving.

• In the 4 - Queens problem we have to place 4 queens such as Q1, Q2, Q3, and Q4 on the chessboard, in such a way that no two queens attack each other.

• To solve this problem generally Backtracking algorithm or approach is used.

Backtracking -

• In backtracking, start with one possible move out of many available moves, then try to solve the problem.

• If it can solve the problem with the selected move then it will print the solution, else it will backtrack and select some other move and try to solve it.

• If none of the moves works out the claim that there is no solution for the problem.

Algorithm for N-Queens Problem using Backtracking

Step 1 - Place the queen row-wise, starting from the left-most cell.

Step 2 - If all queens are placed then return true and print the solution matrix.

Step 3 - Else try all columns in the current row.

• Condition 1 - Check if the queen can be placed safely in this column then mark the current cell [Row, Column] in the solution matrix as 1 and try to check the rest of the problem recursively by placing the queen here leads to a solution or not.

• Condition 2 - If placing the queen [Row, Column] can lead to the solution return true and print the solution for each queen's position.

• Condition 3 - If placing the queen cannot lead to the solution then unmark this [row, column] in the solution matrix as 0, BACKTRACK, and go back to condition 1 to try other rows.

Step 4 - If all the rows have been tried and nothing worked, return false to trigger backtracking.

The Working of an Algorithm to solve the 4-Queens Problem

• To solve the problem place a queen in a position and try to find out all the possibilities for any queen being under attack or not.

• Based on the findings place only one queen in each row/column.

• If we found that the queen is under attack at its chosen position, then try for the next position.

• If a queen is under attack at all the positions in a row, we backtrack and change the position of the queen placed prior to the current position.

• Repeat this process of placing a queen and backtracking until all the N queens are placed successfully.

Step 1 -

As this is the 4-Queens problem, therefore, create a $4 \times 4$ chessboard.

Step 2 -

• Place the Queen Q1 at the left-most position which means row 1 and column 1.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q1. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q1 at [1, 1] position:

Step 3 -

• The possible safe cells for Queen Q2 at row 2 are of column3 and 4 because these cells do not come under the attack from a queen Q1.
• So, here we place Q2 at the first possible safe cell which is row 2 and column 3.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q2. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q2 at [2, 3] position:

Step 4 -

• We see that no safe place is remaining for the Queen Q3 if we place Q2 at position [2, 3]
• Therefore make position [2, 3] false and backtrack.

Step 5 -

• So, we place Q2 at the second possible safe cell which is row 2 and column 4.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q2. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q2 at [2, 4] position:

Step 6 -

• The only possible safe cell for Queen Q3 is remaining in row 3 and column 2.
• Therefore, we place Q3 at the only possible safe cell which is row 3 and column 2.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q3. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q3 at [3, 2] position:

Step 7 -

• We see that no safe place is remaining for the Queen Q4 if we place Q3 at position [3, 2]
• Therefore make position [3, 2] false and backtrack.

Step 8 -

• This time we backtrack to the first queen Q1.
• Place the Queen Q1 at column 2 of row 1.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q1. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q1 at [1, 2] position:

Step 9 -

• The only possible safe cell for Queen Q2 is remaining in row 2 and column 4.
• Therefore, we place Q2 at the only possible safe cell which is row 2 and column 4.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q2. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q2 at [2, 4] position:

Step 10 -

• The only possible safe cell for Queen Q3 is remaining in row 3 and column 1.
• Therefore, we place Q3 at the only possible safe cell which is row 3 and column 1.
• Mark the cells of the chessboard with cross marks that are under attack from a queen Q3. (horizontal, vertical, and diagonal move of the queen)
• The chessboard looks as follows after placing Q3 at [3, 1] position:

Step 11 -

• The only possible safe cell for Queen Q4 is remaining in row 4 and column 3.
• Therefore, we place Q4 at the only possible safe cell which is row 4 and column 3.
• The chessboard looks as follows after placing Q3 at [4, 3] position:

Step 12 -

• Now, here we got the solution for the 4-queens problem because all 4 queens are placed exactly in each row/column individually.

All these procedures are shown sequentially in the below figure:

• This is not the only possible solution to the problem.
• If we move each queen one step forward in a clockwise manner, we get another solution.
• This is also shown sequentially in the below figure:

• In this example we placed the queens according to rows, we can do the same thing column-wise also.
• In that case, each queen will belong to a column.