N Queens Problem For Beginners

If you are NOT aware of backtracking and basics of recursion then this write up is for YOU!!!

Problem Statement:

We have a chess board of size 8x8 matrix.

We have to place 8 queens in the board such that no queens attack each other.

(Queen can move horizontally, vertically and diagonally in any direction)

Queen placements in chess board

Algorithm:

We can approach the solution by placing Queen one by one in the best possible location.

For simplicity let us discuss about the placing queens in 4x4 matrix.

There are only 3 scenarios possible

Scenario 1: We are starting to solve the problem and we are free to place the queen anywhere in board. We will start with top-left position.

a — We see that the position (0,0) is safe as there are no other queens in the board.

b — Place the queen in (0,0) index

Scenario 1

Scenario 2: Placing the queen in next column (ROW, COLUMN) (Instead of column you can choose to iterate over row also.)

Scenario 2

a — We have to check if the position is safe. If the position is not safe keep incrementing the row value to traverse vertically and check for safe position

b — Place the queen in its first safe position. In our use case the first safe position is (1,2). Refer to pic below

c — Increment the column after placing the queen in safe position and follow Scenario 2.

Scenario 3: If there are no safe positions for the queen

a — Subtract the column value by 1 and follow Scenario 2

b — While following Scenario 2 there will already be a queen placed in that row. We now need to place the queen in next safe position.

(The above mentioned point is called backtracking where we are maintaining the previous result and trying to correct previous result to check if we can attain our final outcome)

Observations before starting to code:

If you observe the scenarios you can guess on what way we can approach to write code for this. Below are all the points which can be derived from the algorithm

1. In Scenario 2 it is mentioned that “keep incrementing the row value to traverse horizontally and check for safe position” → This implies that we have to maintain a loop to increment ROW values.
2. In Scenario 2 it is also mentioned that “Increment the column after placing the queen in safe position and follow Scenario 2.” → This implies that we have need one more loop to increment COLUMN values.
3. It is also mentioned that “trying to correct previous result” → This implies that we need to store the previous result value in some form so that we can go back and revisit the decision.

Coding Approach:

Let us first break the problem in to smaller unit of work.

1. First piece of logic is to write a method which will have logic to check if the given position is safe or not. (Check if the queen is with in borders and no queen can attack the new queen)
2. Second piece of logic is to write a method which takes care of maintaining the loop to traverse the matrix horizontally (You can even choose to traverse vertically).
3. The last piece is to have logic to execute in recursion with backtracking.

Let Us Start Coding:

JAVA:

1. First piece of logic to validate if position is safe

public boolean isSafePosition(int[][] matrix, int row, int column) {
       
       // Check for safety in that column
       // We can skip this because we will not have any values in the column initially.
       for(int i=0 ; i < column; i++) {
              if(matrix[row][i] == 'Q') //Column traversal
                        return false;
       }
       // Check for safety in that row
       for(int i=row ; i > 0; i--) {
              if(matrix[i][row] == 'Q') //Row traversal
                        return false;
       }
       // Check for safety in left to top diagonal
       // We are checking only left diagonal because we haven't placed any queen on the right side yet.
for(int i=row, j=column ; i > 0 & j > 0; i--, j--) {
              if(matrix[i][j] == 'Q') //Left top diagonal traversal
                        return false;
       }
       // Check for safety in left to down diagonal
       // We are checking only left diagonal because we haven't placed any queen on the right side yet.
       for(int i=row, j=column ; i > 0 & j < N; i--, j++) {
              if(matrix[i][j] == 'Q') //Left down diagonal traversal
                        return false;
       }
       
       return true;
}

2. Second piece of logic to traverse matrix (Chess board)

public boolean NQueen(int[][] matrix, int row) {
       if(row >= N) return true;
       for(int i=0; i< N; i++) {
             if(isSafe(matrix, row, i) {
                    matrix[row][col] = 'Q';
                    if(NQueen(matrix, row+1, i)) return true;
                    matrix[row][col] = 'O';
            }
       return false;
}

In the above use case back tracking happens when ‘FALSE’ is returned. When FALSE is returned we reset the matrix value from Q to O and then look for safe position.

3. Execute the program

public static void main(String args[]) {
       // Declare the matrix size
       int[][] matrix = new int[4][4];
       NQueen(matrix, 0);
       // Iterate matrix and print the solution
}

Thanks for reading!!! Please leave your comments.